Marcus T. Schmitz
Skip Abstract Section
Abstract
We present an iterative schedule optimization for multirate system specifications, mapped onto heterogeneous distributed architectures containing dynamic voltage scalable processing elements (DVS-PEs). To achieve a high degree of energy reduction, we formulate a generalized DVS problem, taking into account the power variations among the executing tasks. An efficient heuristic is presented that identifies optimized supply voltages by not only "simply" exploiting slack time, but under the additional consideration of the power profiles. Thereby, this algorithm minimizes the energy dissipation of heterogeneous architectures, including power-managed processing elements, effectively. Further, we address the simultaneous schedule optimization toward timing behavior and DVS utilization by integrating the proposed DVS heuristic into a genetic list scheduling approach. We investigate and analyze the possible energy reduction at both steps of the co-synthesis (voltage scaling and scheduling), including the power variations effects. Extensive experiments indicate that the presented work produces solutions with high quality.
- Bambha, N., Bhattacharyya, S., Teich, J., and Zitzler, E. 2001. Hybrid global/local search strategies for dynamic voltage scaling in embedded multiprocessors. In Proceedings of the 1st International Symposium on Hardware/Software Co-Design (CODES'01), 243--248.]] Google Scholar
Digital Library
- Brandolese, C., Fornaciari, W., Salice, F., and Sciuto, D. 2000. Energy estimation for 32 bit microprocessors. In Proceedings of the 8th International Workshop Hardware/Software Co-Design (CODES'00), 24--28.]] Google ScholarDigital Library
- Burd, T. D. 2001. Energy-efficient processor system design. Ph.D. thesis, University of California at Berkeley.]]Google Scholar
- Burd, T. D. and Brodersen, R. W. 1996. Processor design for portable systems. J. VLSI Signal Processing 13, 2 (Aug.), 203--222.]]Google ScholarCross Ref
- Burd, T. D., Pering, T. A., Stratakos, A. J., and Brodersen, R. W. 2000. A dynamic voltage scaled microprocessor system. IEEE J. Solid-State Circuits 35, 11 (Nov.), 1571--1580.]]Google ScholarCross Ref
- Chretienne, P., Coffman, E. G., Lenstra, J. K., and Liu, Z. 1995. Scheduling Theory and its Applications. Wiley, New York.]]Google Scholar
- Devadas, S. and Malik, S. 1995. A survey of optimization techniques targeting low power VLSI circuits. In Proceedings of the IEEE 32nd Design Automation Conference (DAC95), 242--247.]] Google ScholarDigital Library
- Dhodhi, M. K., Ahmad, I., and Storer, R. 1995. SHEMUS: Synthesis of heterogeneous multiprocessor systems. J. Microprocessors and Microsystems 19, 6 (Aug.), 311--319.]]Google ScholarCross Ref
- Dick, R., Rhodes, D., and Wolf, W. 1998. TGFF: Task graphs for free. In Proceedings of the 5th International Workshop on Hardware/Software Co-Design (Codes/CASHE'97), 97--101.]] Google ScholarDigital Library
- Dick, R. P. and Jha, N. K. 1998. MOGAC: A multiobjective genetic algorithm for hardware-software co-synthesis of distributed embedded systems. IEEE Trans. Computer-Aided Design 17, 10 (Oct.), 920--935.]]Google ScholarDigital Library
- Eles, P., Peng, Z., Kuchcinski, K., and Doboli, A. 1997. System level hardware/software partitioning based on simulated annealing and tabu search. J. Design Automation Embedded Systems 2, 5--32.]]Google ScholarDigital Library
- Ernst, R., Henkel, J., and Brenner, T. 1993. Hardware-software co-synthesis for mirco-controllers. IEEE Design & Test of Comp. 10, 4 (Dec.), 64--75.]] Google ScholarDigital Library
- Fogarty, T. C. 1989. Varying the probability of mutation in the genetic algorithm. In Proceedings of the 3rd International Conference on Genetic Algorithms (ICGA), 104--109.]] Google ScholarDigital Library
- Fornaciari, W., Sciuto, D., and Silvano, C. 1999. Power estimation for architectural exploration of HW/SW communication on system-level buses. In Proceedings of the 7th International Workshop on Hardware/Software Co-Design (CODES'99), 152--156.]] Google ScholarDigital Library
- Garey, M. R. and Johnson, D. S. 1979. Computers and Intractability: A Guide to the theory of NP-Completeness. W.H. Freeman and Company, San Francisco, CA.]] Google ScholarDigital Library
- Goldberg, D. E. 1989. Genetic Algorithms in Search, Optimization & Machine Learning. Addison-Wesley, San Mateo, CA.]] Google ScholarDigital Library
- Grajcar, M. 1999. Genetic list scheduling algorithm for scheduling and allocation on a loosely coupled heterogeneous multiprocessor system. In Proceedings of the IEEE 36th Design Automation Conference (DAC99), 280--285.]] Google ScholarDigital Library
- Gruian, F. 2000. System-level design methods for low-energy architectures containing variable voltage processors. In Workshop on Power-Aware Computing Systems.]] Google ScholarDigital Library
- Gruian, F. and Kuchcinski, K. 2001. LEneS: task scheduling for low-energy systems using variable supply voltage processors. In Proceedings of the Asia South Pacific-Design Automation Conference (ASP-DAC'01), 449--455.]] Google ScholarDigital Library
- Gutnik, V. and Chandrakasan, A. 1997. Embedded power supply for low-power DSP. IEEE Trans. VLSI Systems 5, 4, 425--435.]] Google ScholarDigital Library
- Henkel, J., Benner, T., and Ernst, R. 1993. Hardware generation and partitioning effects in the COSYMA system. In Proceedings of the International Workshop on Hardware/Software Co-Design (Codes/CASHE'93).]]Google Scholar
- Henkel, J. and Ernst, R. 2001. An approach to automated hardware/software partitioning using a flexible granularity that is driven by high-level estimation techniques. IEEE Trans. VLSI Systems 9, 2, 273--289.]] Google ScholarDigital Library
- Hong, I., Kirovski, D., Qu, G., Potkonjak, M., and Srivastava, M. B. 1999. Power optimization of variable-voltage core-based systems. IEEE Trans. Computer-Aided Design 18, 12 (Dec.), 1702--1714.]]Google ScholarDigital Library
- Hou, J. and Wolf, W. 1996. Process partitioning for distributed embedded systems. In Proceedings of the CODES, 70--76.]] Google ScholarDigital Library
- Intel® XScaleRM. 2000. Developer's Manual. Order number 273473--001.]]Google Scholar
- Ishihara, T. and Yasuura, H. 1998. Voltage scheduling problem for dynamically variable voltage processors. In Proceedings of the International Symposium on Low Power Electronics and Design (ISLPED'98), 197--202.]] Google ScholarDigital Library
- Kalavade, A. 1995. System-level codesign of mixed hardware-software systems. Ph.D. thesis, University of California, Berkeley.]] Google ScholarDigital Library
- Kirovski, D. and Potkonjak, M. 1997. System-level synthesis of low-power hard real-time systems. In Proceedings of the IEEE 34th Design Automation Conference (DAC97), 697--702.]] Google ScholarDigital Library
- Klaiber, A. 2000. The Technology behind crusoe processors. http://www.transmeta.com.]]Google Scholar
- Lee, S. and Sakurai, T. 2000. Run-time voltage hopping for low-power real-time systems. In Proceedings of the IEEE 37th Design Automation Conference (DAC00), 806--809.]] Google ScholarDigital Library
- Li, Y.-T. S., Malik, S., and Wolfe, A. 1995. Performance estimation of embedded software with instruction cache modeling. In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design (ICCAD-95), 380--387.]] Google ScholarDigital Library
- Liu, J., Chou, P. H., Bagherzadeh, N., and Kurdahi, F. 2001. Power-aware scheduling under timing constraints for mission-critical embedded systems. In Proceedings of the IEEE 38th Design Automation Conference (DAC01), 840--845.]] Google ScholarDigital Library
- Luo, J. and Jha, N. K. 2000. Power-conscious joint scheduling of periodic task graphs and aperiodic tasks in distributed real-time embedded systems. In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design (ICCAD-00), 357--364.]] Google ScholarDigital Library
- Luo, J. and Jha, N. K. 2001. Battery-aware static scheduling for distributed real-time embedded systems. In Proceedings of the IEEE 38th Design Automation Conference (DAC01), 444--449.]] Google ScholarDigital Library
- Manzak, A. and Chakrabarti, C. 2000. Variable voltage task scheduling for minimizing energy or minimizing power. In Proceedings of the International Conference on Acoustics, Speech, and Signal Processing (ICASSP00), 3239--3242.]] Google ScholarDigital Library
- Micheli, G. D. and Gupta, R. K. 1997. Hardware/software co-design. In Proceedings of the IEEE, 349--365.]]Google Scholar
- Mobile AMD AthlonTM4. 2000. Processor model 6 CPGA data sheet. Publication no 24319 Rev E.]]Google Scholar
- Muresan, R. and Gebotys, C. H. 2001. Current consumption dynamics at instruction and program level for a VLIW DSP processor. In Proceedings of the International Symposium on System Synthesis (ISSS'01), 130--135.]] Google ScholarDigital Library
- Okuma, T., Ishihara, T., and Yasuura, H. 1999. Real-time task scheduling for a variable voltage processor. In Proceedings of the International Symposium on System Synthesis (ISSS'99), 24--29.]] Google ScholarDigital Library
- Okuma, T., Ishihara, T., and Yasuura, H. 2001. Software energy reduction techniques for variable-voltage processors. IEEE Design & Test of Comp. 18, 2 (Mar.--Apr.), 31--41.]] Google ScholarDigital Library
- Pedram, M. 1996. Power minimization in IC design: principles and applications. ACM Trans. Design Automation of Electronic Systems 1, 1 (Jan.), 3--56.]] Google ScholarDigital Library
- Pering, T., Burd, T. D., and Brodersen, R. B. 1998. The simulation and evaluation for dynamic voltage scaling algorithms. In Proceedings of the International Symposium on Low Power Electronics and Design (ISLPED'98), 76--81.]] Google ScholarDigital Library
- Prakash, S. and Parker, A. 1992. SOS: Synthesis of application-specific heterogeneous multiprocessor systems. J. Parallel & Distributed Computing, 338--351.]]Google Scholar
- Quan, G. and Hu, X. S. 2001. Energy efficient fixed-priority scheduling for real-time systems on variable voltage processors. In Proceedings of the IEEE 38th Design Automation Conference (DAC01), 828--833.]] Google ScholarDigital Library
- Quan, G. and Hu, X. S. 2002. Minimum energy fixed-priority scheduling for variable voltage processors. In Proceedings of the Design, Automation and Test in Europe Conference (DATE2002), 782--787.]] Google ScholarDigital Library
- Rogers, A. and Prügel-Bennett, A. 1999. Modelling the dynamics of a steady-state genetic algorithm. In Foundations of Genetic Algorithms (FOGA-5). 57--68.]]Google Scholar
- Schmitz, M. T. 2003. Energy minimization techniques for distributed embedded systems. Ph.D. thesis, University of Southampton.]]Google Scholar
- Schmitz, M. T. and Al-Hashimi, B. M. 2001. Considering power variations of DVS processing elements for energy minimization in distributed systems. In Proceedings of the International Symposium on System Synthesis (ISSS'01), 250--255.]] Google ScholarDigital Library
- Schmitz, M. T., Al-Hashimi, B. M., and Eles, P. 2002. Energy-efficient mapping and scheduling for DVS enabled distributed embedded systems. In Proceedings of the Design, Automation and Test in Europe Conference (DATE2002), 514--521.]] Google ScholarDigital Library
- Shin, Y. and Choi, K. 1999. Power conscious fixed priority scheduling for hard real-time systems. In Proceedings of the IEEE 36th Design Automation Conference (DAC99), 134--139.]] Google ScholarDigital Library
- Shin, Y., Choi, K., and Sakurai, T. 2000. Power optimization of real-time embedded systems on variable speed processors. In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design (ICCAD-00), 365--368.]] Google ScholarDigital Library
- Sih, G. C. and Lee, E. A. 1993. A compile-time scheduling heuristic for interconnection-constrained heterogeneous processor architectures. IEEE Trans. Parallel and Distributed Systems 4, 2 (Feb.), 175--187.]] Google ScholarDigital Library
- Simunic, T., Benini, L., Acquaviva, A., Glynn, P., and Micheli, G. D. 2001. Dynamic voltage scaling and power management for portable systems. In Proceedings of the IEEE 38th Design Automation Conference (DAC01), 524--529.]] Google ScholarDigital Library
- Teich, J., Blickle, T., and Thiele, L. 1997. An evolutionary approach to system-level synthesis. In Proceedings of the 5th International Workshop on Hardware/Software Co-Design (Codes/CASHE'97), 167--171.]] Google ScholarDigital Library
- Tiwari, V., Malik, S., and Wolfe, A. 1994. Power analysis of embedded software: A first step towards software power minimization. IEEE Trans. VLSI Systems.]] Google ScholarDigital Library
- Weiser, M., Welch, B., Demers, A., and Shenker, S. 1994. Scheduling for reduced CPU energy. In Proceedings of the USENIX Symposium on Operating Systems Design and Implementation (OSDI), 13--23.]] Google ScholarDigital Library
- WITAS. The Wallenberg Laboratory for research on information technology and autonomous system. http://www.ida.liu.se/ext/witas/.]]Google Scholar
- Wolf, W. H. 1994. Hardware/software co-design of embedded systems. In Proceedings of the IEEE, 967--989.]]Google ScholarCross Ref
- Wolf, W. H. 1997. An architectural co-synthesis algorithm for distributed, embedded computing systems. IEEE Trans. VLSI Systems 5, 2 (June), 218--229.]] Google ScholarDigital Library
- Wu, M. and Gajski, D. 1990. Hypertool: A programming aid for message-passing systems. IEEE Trans. Parallel and Distributed Systems 1, 3 (July), 330--343.]] Google ScholarDigital Library
- Xie, Y. and Wolf, W. 2001. Allocation and scheduling of conditional task graph in hardware/software co-synthesis. In Proceedings of the Design, Automation and Test in Europe Conference (DATE2001), 620--625.]] Google ScholarDigital Library
- Zhang, Y., Hu, X., and Chen, D. Z. 2002. Task scheduling and voltage selection for energy minimization. In Proceedings of the IEEE 39th Design Automation Conference (DAC02), 183--188.]] Google ScholarDigital Library
Index Terms
- Iterative schedule optimization for voltage scalable distributed embedded systems
Recommendations
Voltage setup problem for embedded systems with multiple voltages
We formulate the following voltage setup problem: how many levels and at which values should voltages be implemented on the system to achieve the maximum energy saving by dynamic voltage scaling (DVS)? This problem challenges whether DVS technique's ...
Analysis of energy reduction on dynamic voltage scaling-enabled systems
Dynamic voltage scaling (DVS) is a technique that varies the supply voltage and clock frequency, based on the computation load, to provide the desired performance with the minimal amount of energy consumption. It has been demonstrated as one of the most ...
Procrastination determination for periodic real-time tasks in leakage-aware dynamic voltage scaling systems
ICCAD '07: Proceedings of the 2007 IEEE/ACM international conference on Computer-aided designMany computing systems have adopted the dynamic voltage scaling (DVS) technique to reduce energy consumption by slowing down operation speed. However, the longer a job executes, the more energy in leakage current the processor consumes for the job. To ...
Comments