Abstract
Dynamic Voltage Scaling (DVS) is one of the techniques used to obtain energy-saving in real-time DSP systems. In many DSP systems, some tasks contain conditional instructions that have different execution times for different inputs. Due to the uncertainties in execution time of these tasks, this paper models each varied execution time as a probabilistic random variable and solves the Voltage Assignment with Probability (VAP) Problem. VAP problem involves finding a voltage level to be used for each node of an date flow graph (DFG) in uniprocessor and multiprocessor DSP systems. This paper proposes two optimal algorithms, one for uniprocessor and one for multiprocessor DSP systems, to minimize the expected total energy consumption while satisfying the timing constraint with a guaranteed confidence probability. The experimental results show that our approach achieves significant energy saving than previous work. For example, our algorithm for multiprocessor achieves an average improvement of 56.1% on total energy-saving with 0.80 probability satisfying timing constraint.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
I. Foster, Designing and Building Parallel Program: Concepts and Tools for Parallel Software Engineering, Addison-Wesley, Reading, MA, 1994.
B. P. Lester, The Art of Parallel Programming, Prentice Hall, Englewood Cliffs, NJ, 1993.
M. E. Wolfe, High Performance Compilers for Parallel Computing, Addison-Wesley, Redwood City, CA, 1996.
P. G. Paulin and J. P. Knight, “Force-directed Scheduling for the Behavioral Synthesis of Asic’s,” IEEE Trans. Comput.-aided Des. Integr. Circuits Syst., vol. 8, 1989, pp. 661–679.
L.-F. Chao and E. H.-M. Sha, “Static Scheduling for Synthesis of DSP Algorithms on Various Models,” J. VLSI Signal Process. Syst., vol. 10, 1995, pp. 207–223.
L.-F. Chao and E. H.-M. Sha, “Scheduling Data-flow Graphs via Retiming and Unfolding,” IEEE Trans. Parallel Distrib. Syst., vol. 8, 1997, pp. 1259–1267.
S. Tongsima, E. H.-M. Sha, C. Chantrapornchai, D. Surma, and N. Passose, “Probabilistic Loop Scheduling for Applications with Uncertain Execution Time,” IEEE Trans. Comput., vol. 49, 2000, pp. 65–80.
T. Zhou, X. Hu, and E. H.-M. Sha, “Estimating Probabilistic Timing Performance for Real-time Embedded Systems,” IEEE Trans. Very Large Scale Integr. (VLSI) Syst., vol. 9, no. 6, 2001, pp. 833–844.
Shaoxiong Hua, Gang Qu, and Shuvra S. Bhattacharyya, “Exploring the Probabilistic Design Space of Multimedia Systems,” in IEEE International Workshop on Rapid System Prototyping 2003, pp. 233–240.
Shaoxiong Hua, Gang Qu, and Shuvra S. Bhattacharyya, “Energy Reduction Techniques for Multimedia Applications with Tolerance to Deadline Misses,” in ACM/IEEE Design Automation Conference (DAC), 2003, pp. 131–136.
Shaoxiong Hua and Gang Qu, “Approaching the Maximum Energy Saving on Embedded Systems with Multiple Voltages,” in International Conference on Computer Aid Design (ICCAD), 2003, pp. 26–29.
T. Tia, Z. Deng, M. Shankar, M. Storch, J. Sun, L. Wu, and J. Liu, “Probabilistic Performance Guarantee for Real-time Tasks with Varying Computation Times,” in Proceedings of Real-time Technology and Applications Symposium, 1995, pp. 164–173.
J. Bolot and A. Vega-Garcia, “Control Mechanisms for Packet Audio in the Internet,” in Proc. IEEE Infocom, 1996.
C.-Y. Wang and K. K. Parhi, “High-level Synthesis Using Concurrent Transformations, Scheduling, and Allocation,” IEEE Trans. Comput.-aided Des. Integr. Circuits Syst., vol. 14, 1995, pp. 274–295.
K. Ito, L. Lucke, and K. Parhi, “Ilp-based Cost-optimal DSP Synthesis with Module Selection and Data Format Conversion,” IEEE Trans. VLSI Syst., vol. 6, 1998, pp. 582–594.
K. Ito and K. Parhi, “Register Minimization in Cost-optimal Synthesis of DSP Architecture,” in Proc. IEEE VLSI Signal Processing Workshop, 1995.
Z. Shao, Q. Zhuge, C. Xue, and E. H.-M. Sha, “Efficient Assignment and Scheduling for Heterogeneous DSP Systems,” IEEE Trans. Parallel Distrib. Syst., vol. 16, 2005, pp. 516–525.
M. Qiu, M. Liu, C. Xue, Z. Shao, Q. Zhuge, and E. H.-M. Sha, “Optimal Assignment with Guaranteed Confidence Probability for Trees on Heterogeneous DSP Systems,” in Proceedings of the 17th IASTED International Conference on Parallel and Distributed Computing Systems (PDCS 2005), Phoenix, Arizona, 2005, pp. 14–16.
A. Kalavade and P. Moghe, “A Tool for Performance Estimation of Networked Embedded End-systems,” in Proc.-Des. Autom. Conf., 1998, pp. 257–262.
Y. Chen, Z. Shao, Q. Zhuge, C. Xue, B. Xiao, and E. H.-M. Sha, “Minimizing Energy Via Loop Scheduling and Dvs for Multi-core Embedded Systems,” in Proceedings the 11th International Conference on Parallel and Distributed Systems (ICPADS’05) Volume II, The IEEE/IFIP International Workshop on Parallel and Distributed EMbedded Systems (PDES 2005), Fukuoka, Japan, 20–22, 2005, pp. 2–6.
D. Shin, J. Kim, and S. Lee, “Low-energy Intra-task Voltage Scheduling Using Static Timing Analysis,” in DAC, 2001, pp. 438–443.
Y. Zhang, X. Hu, and D. Z. Chen, “Task Scheduling and Voltage Selection for Energy Minimization,” in DAC, 2002, pp. 183–188.
H. Saputra, M. Kandemir, N. Vijaykrishnan, M. J. Irwin, J. S. Hu, C-H. Hsu, and U. Kremer, “Energy-conscious Compilation Based on Voltage Scaling,” in LCTES’02, 2002.
T. Ishihara and H. Yasuura, “Voltage Scheduling Problem for Dynamically Variable Voltage Processor,” in ISLPED, 1998, pp. 197–202.
Acknowledgement
This work is partially supported by TI University Program, NSF EIA-0103709, Texas ARP 009741-0028-2001, NSF CCR-0309461, NSF IIS-0513669, and Microsoft, USA.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Qiu, M., Jia, Z., Xue, C. et al. Voltage Assignment with Guaranteed Probability Satisfying Timing Constraint for Real-time Multiproceesor DSP. J VLSI Sign Process Syst Sign Image Video Technol 46, 55–73 (2007). https://doi.org/10.1007/s11265-006-0002-0
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11265-006-0002-0