More Web Proxy on the site http://driver.im/

Article

Hybrid global/local search strategies for dynamic voltage scaling in embedded multiprocessors

Authors:

Neal K. Bambha,

Shuvra S. Bhattacharyya,

Eckart ZitzlerAuthors Info & Claims

CODES '01: Proceedings of the ninth international symposium on Hardware/software codesign

Pages 243 - 248

https://doi.org/10.1145/371636.371744

Published: 25 April 2001 Publication History

Abstract

In this paper, we explore a hybrid global/local search optimization framework for dynamic voltage scaling in embedded multiprocessor systems. The problem is to find, for a multiprocessor system in which the processors are capable of dynamically varying their core voltages, the optimum voltage levels for all the tasks in order to minimize the average power consumption under a given performance constraint. An effective local search approach for static voltage scaling based on the concept of a period graph has been demonstrated in [1]. To make use of it in an optimization problem, the period graph must be integrated into a global search algorithm. Simulated heating, a general optimization framework developed in [19], is an efficient method for precisely this purpose of integrating local search into global search algorithms. However, little is known about the management of computational (compile-time) resources between global search and local search in hybrid algorithms, such as those coordinated by simulated heating. In this paper, we explore various hybrid search management strategies for power optimization under the framework of simulated heating. We demonstrate that careful search management leads to significant power consumption improvement over add-hoc global search / local search integration, and explore alternative approaches to performing hybrid search management for dynamic voltage scaling.

References

[1]

N. K. Bambha and S. S. Bhattacharyya. A joint power/performance optimization technique for multiprocessur systems using a period graph construct. In Proceedings of the International Symposium on systems Synthesis, pages 91-97, September 2000.]]

Digital Library

[2]

T. Burd and R. Broderson, "Design Issues for Dynamic Voltage Scaling", In Proceedings of 2000 International Symposium on Low Power Electronics and Design, pages 76-81, July 2000.]]

Digital Library

[3]

A. P. Chandrakasan, S. Sheng, and R. W. Brodersen. Low-power CMOS digital design. 1EEE Journal of Solid State Circuits, 27(4):473-484, 1992.]]

[4]

J. M. Chang and M. Pedram, "Register allocation and binding for low power," Design Automation Conf., June, 1995.]]

Digital Library

[5]

A. Dasdan and 1L K. Gupta. Faster maximum and minimum mean cycle algorithms for system-performance analysis. IEEE Transactions on Computer-Aided Design of Integrated Circuits and @stems, 17(10):889-899, October 1998.]]

Digital Library

[6]

A. Dasgupta and R. Karri, "Simultaneous scheduling and binding for power minimization during microarehiteeture synthesis," in Proceedings of the International Symposium on Low Power Design, April 1995.]]

Digital Library

[7]

D. E. Goldberg and S. Voessner. Optimizing global-local search hybrids. In Proceedings of the Genetic and Evolutionary Computation Conference, pages 220-228, 1999.]]

[8]

L. Goodby, A. Orailoglu, and P. M. Chau, "Mieroarchitectural synthesis of performance-constrained low-power VLSI designs," in Proceedings of the International Conference on Computer Design, Oct. 1994.]]

Digital Library

[9]

H. Ishibuchi and T. Murata. Multi-objective genetic local search algorithm. In Proceedings of the IEEE Conference on Evolutionary Computation, pages 119-124, 1996.]]

[10]

A. Kahn, C. McCreary, J. Thompson, and M. McArdle, "A Comparison of Multiprocessor Scheduling Heuristics", in Proceedings of 1994 International Conference on Parallel Processing vol. II, pages 243-250, 1994.]]

Digital Library

[11]

E. A. Lee and S. Ha. Scheduling strategies for multipreoessor real time DSP. In Proceedings of the Global Telecommunications Conference, November 1989.]]

[12]

Y. S. Li and S. Malik. Performance analysis of embedded software using implicit path enumeration. In Proceedings of the Design Automation Conference, 1995.]]

Digital Library

[13]

D. Mareulescu, "On the Use of Mieroarchitecture-Driven Dynamic Voltage Scaling', Proceedings of ISCA 2000.]]

[14]

T. Pering, T. Burd, and R. Broderson, "The simulation and Evaluation fo Dynamic Voltage Scaling Algorithms", In Proceedings of International smposium on Low Power Electronics and Design, pages 76-81, August 1998.]]

Digital Library

[15]

A. Raghunatban and N. K. Jha, "Behavioral synthesis for low power," in Proe. Intl. Conf. Computer Design, Oct. 1994.]]

Digital Library

[16]

M. Ryan, J. Debuse, G. Smith, and I. Whittley. A hybrid genetic algorithm for the fixed channel assignment problem. In Proceedings of the Genetic and Evolutionary Computation Conference, pages 1707-1714, 1999.]]

[17]

G. C. s i r and E. A. Lee. A compilo-time scheduling heuristic for interconnection-conatrained heterogeneous processor architectures. IEEE Transactions on Parallel and Distributed Systems, 4(2): 75-87, February 1993.]]

Digital Library

[18]

D. Whitley. The GENITOR Algorithm and Selective Pressure: Why Rank-Based Allocation of Reproductive Trials is Best. In Proceedings of 3rd International Conference on Genetic Algorithms, pages 116-121. Morgan Kauffman, 1989.]]

Digital Library

[19]

E. Zitzler, J. Teich, and S. S. Bhattacharyya. Optimizing the efficiency of parameterized local search within global search: A preliminary study. In Proceedings of the Congress on Evolutionary Computation, pages 365-372, San Diego, California, July 2000.]]

Cited By

Gowtham SPoongothai M(2016)Timing based energy efficient task assignment algorithm for real time embedded systems2016 International Conference on Circuit, Power and Computing Technologies (ICCPCT)10.1109/ICCPCT.2016.7530189(1-5)Online publication date: Mar-2016
https://doi.org/10.1109/ICCPCT.2016.7530189
Basmadjian RBouvry PCosta GGyarmati LKliazovich DLafond SLefèvre LMeer HPierson JPries RTorres JTrinh TKhan S(2015)Green Data CentersLarge-Scale Distributed Systems and Energy Efficiency10.1002/9781118981122.ch6(159-196)Online publication date: 10-Apr-2015
https://doi.org/10.1002/9781118981122.ch6
Niu JLiu CGao YQiu M(2014)Energy Efficient Task Assignment with Guaranteed Probability Satisfying Timing Constraints for Embedded SystemsIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2013.25125:8(2043-2052)Online publication date: Aug-2014
https://doi.org/10.1109/TPDS.2013.251
Show More Cited By

Index Terms

Hybrid global/local search strategies for dynamic voltage scaling in embedded multiprocessors
1. Software and its engineering
  1. Software creation and management
    1. Designing software
  2. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Process management

Recommendations

The limit of dynamic voltage scaling and insomniac dynamic voltage scaling

Dynamic voltage scaling (DVS) is a popular approach for energy reduction of integrated circuits. Current processors that use DVS typically have an operating voltage range from full to half of the maximum V_dd. However, there is no fundamental reason why ...
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 ...
Intraprogram dynamic voltage scaling: Bounding opportunities with analytic modeling

Dynamic voltage scaling (DVS) has become an important dynamic power-management technique to save energy. DVS tunes the power-performance tradeoff to the needs of the application. The goal is to minimize energy consumption while meeting performance ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CODES '01: Proceedings of the ninth international symposium on Hardware/software codesign

April 2001

271 pages

ISBN:1581133642

DOI:10.1145/371636

Chairmen:
Jan Madsen
Technical Univ. of Denmark, Lyngby
,
Joerg Henkel
C&C Research Labs, Princeton, NJ
,
Xiaobo (Sharon) Hu
Univ. of Notre Dame, Notre Dame, IN

Copyright © 2001 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

IFIP WG 10.5: IFIP WG 10.5
IEEE-ComSoc: Communications Society
SIGDA: ACM Special Interest Group on Design Automation
SIGSOFT: ACM Special Interest Group on Software Engineering

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 April 2001

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

CODES01

Sponsor:

IFIP WG 10.5
IEEE-ComSoc
SIGDA
SIGSOFT

CODES01: 9th International Symposium on Hardware/Software Codesign

Copenhagen, Denmark

Acceptance Rates

CODES '01 Paper Acceptance Rate 43 of 83 submissions, 52%;

Overall Acceptance Rate 280 of 864 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

24
Total Citations
View Citations
330
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 19 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Gowtham SPoongothai M(2016)Timing based energy efficient task assignment algorithm for real time embedded systems2016 International Conference on Circuit, Power and Computing Technologies (ICCPCT)10.1109/ICCPCT.2016.7530189(1-5)Online publication date: Mar-2016
https://doi.org/10.1109/ICCPCT.2016.7530189
Basmadjian RBouvry PCosta GGyarmati LKliazovich DLafond SLefèvre LMeer HPierson JPries RTorres JTrinh TKhan S(2015)Green Data CentersLarge-Scale Distributed Systems and Energy Efficiency10.1002/9781118981122.ch6(159-196)Online publication date: 10-Apr-2015
https://doi.org/10.1002/9781118981122.ch6
Niu JLiu CGao YQiu M(2014)Energy Efficient Task Assignment with Guaranteed Probability Satisfying Timing Constraints for Embedded SystemsIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2013.25125:8(2043-2052)Online publication date: Aug-2014
https://doi.org/10.1109/TPDS.2013.251
Yuan ZZhang YXue C(2011)Sleep-aware mode assignment in wireless embedded systemsJournal of Parallel and Distributed Computing10.1016/j.jpdc.2010.11.00671:7(1002-1010)Online publication date: 1-Jul-2011
https://dl.acm.org/doi/10.1016/j.jpdc.2010.11.006
Lee HKim B(2010)Coscheduling of processor voltage and control task period for energy-efficient control systemsACM Transactions on Embedded Computing Systems10.1145/1698772.16987739:3(1-24)Online publication date: 5-Mar-2010
https://dl.acm.org/doi/10.1145/1698772.1698773
Goh LVeeravalli BViswanathan S(2007)An energy-aware gradient-based scheduling heuristic for heterogeneous multiprocessor embedded systemsProceedings of the 14th international conference on High performance computing10.5555/1782174.1782213(331-341)Online publication date: 18-Dec-2007
https://dl.acm.org/doi/10.5555/1782174.1782213
Gorjiara BBagherzadeh NChou P(2007)Ultra-fast and efficient algorithm for energy optimization by gradient-based stochastic voltage and task schedulingACM Transactions on Design Automation of Electronic Systems10.1145/1278349.127835212:4(39-es)Online publication date: 1-Sep-2007
https://dl.acm.org/doi/10.1145/1278349.1278352
Srinivasan KChatha K(2007)Integer linear programming and heuristic techniques for system-level low power scheduling on multiprocessor architectures under throughput constraintsIntegration, the VLSI Journal10.1016/j.vlsi.2006.01.00140:3(326-354)Online publication date: 1-Apr-2007
https://dl.acm.org/doi/10.1016/j.vlsi.2006.01.001
Goh LVeeravalli BViswanathan S(2007)An Energy-Aware Gradient-Based Scheduling Heuristic for Heterogeneous Multiprocessor Embedded SystemsHigh Performance Computing – HiPC 200710.1007/978-3-540-77220-0_32(331-341)Online publication date: 2007
https://doi.org/10.1007/978-3-540-77220-0_32
Künzli SThiele LZitzler E(2005)Modular design space exploration framework for embedded systemsIEE Proceedings - Computers and Digital Techniques10.1049/ip-cdt:20045081152:2(183)Online publication date: 2005
https://doi.org/10.1049/ip-cdt:20045081
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents