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

Article

Free access

A joint power/performance optimization algorithm for multiprocessor systems using a period graph construct

Authors:

Neal K. Bambha,

Shuvra S. BhattacharyyaAuthors Info & Claims

ISSS '00: Proceedings of the 13th international symposium on System synthesis

Pages 91 - 97

Published: 20 September 2000 Publication History

Abstract

A critical challenge in synthesis techniques for iterative applications is the efficient analysis of performance in the presence of communication resource contention. To address this challenge, we introduce the concept of the period graph. The period graph is constructed from the output of a simulation of the system, with idle states included in the graph, and its maximum cycle mean is used to estimate overall system throughput. As an example of the utility of the period graph, we demonstrate its use in a joint power/performance optimization solution that uses either a nested genetic algorithm, or a simulated annealing algorithm. We analyze the fidelity of this estimator, and quantify the speedup and optimization accuracy obtained compared to simulation.

References

[1]

T. Back, U. Hammel, and H. Schwefel. "Evolutionary computation: Comments on the history and current state." IEEE Transactions on Evolutionary Computation, April, 1997.

Digital Library

[2]

Carter, Everett, Taygeta Scientific Inc. http:// www.taygeta.com/annealing/simanneal.html.

[3]

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

[4]

A. P. Chandrakasan, M. Potkonjak, R. Mehra, J. Rabaey, and R. Brodersen, "Optimizing power using transformations," IEEE Trans. Computer-Aided Design, vol. 14, no. 1, 1995.

Digital Library

[5]

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

Digital Library

[6]

A. Dasgupta and R. Karri, "Simultaneous scheduling and binding for power minimization during microarchitecture synthesis," in Proc. Intl. Symp. Low Power Design, Apr. 1995.

Digital Library

[7]

L. Goodby, A. Orailoglu, and P. M. Chau, "Microarchitectural synthesis of performance-constrained low-power VLSI designs," in Proc. Int. Conf. Computer Design, Oct. 1994.

Digital Library

[8]

C. Hwang and A.C.-H. Wu. "A predictive system shutdown method for energy saving of event-driven computation." International Conference on Computer-Aided Design, 1997.

Digital Library

[9]

E. L. Lawler. Combinatorial Optimization. Holt, Rinehart and Winston. 1976.

[10]

E. A. Lee and S. Ha. Scheduling strategies for multiprocessor real time DSP. Global Telecommunications Conference, November 1989.

[11]

P. Macken, M. Degrauwe, M. Van Paemel, and G. Oguey, "A voltage reduction technique for digital systems," in Proc. IEEE Intl. Solid-State Circuits Conf., 1990.

[12]

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

Digital Library

[13]

G. C. Sih, "Multiprocessor Scheduling to Account for Interprocessor Communication", Ph.D. thesis, Dept. of EECS, U. C. Berkeley, 1991.

Digital Library

[14]

S. Sriram, and S. S. Bhattacharyya, Embedded Multiprocessors: Scheduling and Synchronization. Marcel Dekker, Inc., 2000.

Digital Library

[15]

M. Srivastava, A. P. Chandrakasan, and R.W. Broderson. "Predictive system shutdown and other architectural techniques for energy efficient programmable computation." IEEE Transactions on VLSI Systems, 4(1): 42-55, 1996.

Digital Library

[16]

V. Tiwari, S. Malik, and A. Wolfe, "Power Analysis of Embedded Software: A First Step Towards Software Power Minimization", IEEE Trans. VLSI, December 1994.

Digital Library

[17]

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

[18]

G. C. Sih and E. A. Lee. A compile-time scheduling heuristic for interconnection-constrained heterogeneous processor architectures. IEEE Transactions on Parallel and Distributed Systems, 4(2):75-87, February 1993.

Digital Library

[19]

J. T. Buck, S. Ha, E. A. Lee, and D. G. Messerschmitt. Ptolemy: A framework for simulating and prototyping heterogeneous systems. International Journal of Computer Simulation, January 1994.

[20]

N. K. Bambha and S. S. Bhattacharyya, A Period Graph Throughput Estimator for Multiprocessor Systems, ISR technical report, University of Maryland, July 2000.

Cited By

Pelcat MMercat ADesnos KMaggiani LLiu YHeulot JNezan JHamidouche WMenard DBhattacharyya S(2018)Reproducible Evaluation of System Efficiency With a Model of ArchitectureIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2017.277482237:10(2050-2063)Online publication date: 1-Oct-2018
https://dl.acm.org/doi/10.1109/TCAD.2017.2774822
Wang YLiu HLiu DQin ZShao ZSha E(2011)Overhead-aware energy optimization for real-time streaming applications on multiprocessor System-on-ChipACM Transactions on Design Automation of Electronic Systems10.1145/1929943.192994616:2(1-32)Online publication date: 7-Apr-2011
https://dl.acm.org/doi/10.1145/1929943.1929946
Bambha NKianzad VKhandelia MBhattacharyya S(2002)Intermediate Representations for Design Automation of Multiprocessor DSP SystemsDesign Automation for Embedded Systems10.1023/A:10203072220527:4(307-323)Online publication date: 1-Nov-2002
https://dl.acm.org/doi/10.1023/A%3A1020307222052
Show More Cited By

A joint power/performance optimization algorithm for multiprocessor systems using a period graph construct
1. General and reference
  1. Cross-computing tools and techniques

Recommendations

Using bi-coset graphs to construct small regular and biregular graphs
Abstract
A bi-coset graph Γ ( G ; H , K ) is a bipartite graph with the two vertex sets consisting of the cosets of subgroups H , K of a group G, and the adjacency determined by non-empty intersection. Bi-coset graphs constitute a classical object of ...
Spanning Connectivity of the Power of a Graph and Hamilton-Connected Index of a Graph

Let G = ( V , E ) be a connected graph. The hamiltonian index h ( G ) (Hamilton-connected index hc ( G )) of G is the least nonnegative integer k for which the iterated line graph L ^k( G ) is hamiltonian (Hamilton-connected). In this ...
Equipartite gregarious connected (5,5)-graph systems

A (p,q)-graph is a graph with p vertices and q edges. There are only five non-isomorphic connected (5,5)-graph: bull graph H1, cricket graph H2, (3,2)-tadpole graph H3, (4,1)-tadpole graph H4, 5-cycle graph H5. Let G be a graph. For i=1,2,3,4,5, an Hi ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ISSS '00: Proceedings of the 13th international symposium on System synthesis

September 2000

240 pages

ISBN:1581132670

General Chair:
Fadi Kurdahi
University of California, Irvine, CA, USA
,
Program Chair:
Román Hermida
Complutense University, Madrid, Spain

Sponsors

IEEE: IEEE Computer Society Technical Committee on Design Automation
SIGDA: ACM Special Interest Group on Design Automation

Publisher

IEEE Computer Society

United States

Publication History

Published: 20 September 2000

Check for updates

Qualifiers

Article

Conference

ISSS00

Sponsor:

IEEE
SIGDA

ISSS00: 13th International Symposium on System Synthesis

September 20 - 22, 2000

Madrid, Spain

Acceptance Rates

Overall Acceptance Rate 38 of 71 submissions, 54%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
238
Total Downloads

Downloads (Last 12 months)42
Downloads (Last 6 weeks)12

Reflects downloads up to 19 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Pelcat MMercat ADesnos KMaggiani LLiu YHeulot JNezan JHamidouche WMenard DBhattacharyya S(2018)Reproducible Evaluation of System Efficiency With a Model of ArchitectureIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2017.277482237:10(2050-2063)Online publication date: 1-Oct-2018
https://dl.acm.org/doi/10.1109/TCAD.2017.2774822
Wang YLiu HLiu DQin ZShao ZSha E(2011)Overhead-aware energy optimization for real-time streaming applications on multiprocessor System-on-ChipACM Transactions on Design Automation of Electronic Systems10.1145/1929943.192994616:2(1-32)Online publication date: 7-Apr-2011
https://dl.acm.org/doi/10.1145/1929943.1929946
Bambha NKianzad VKhandelia MBhattacharyya S(2002)Intermediate Representations for Design Automation of Multiprocessor DSP SystemsDesign Automation for Embedded Systems10.1023/A:10203072220527:4(307-323)Online publication date: 1-Nov-2002
https://dl.acm.org/doi/10.1023/A%3A1020307222052
Kang DCrago SSuh JBodik RSreedhar V(2001)Power-Aware Design Synthesis Techniques for Distributed Real-Time SystemsProceedings of the 2001 ACM SIGPLAN workshop on Optimization of middleware and distributed systems10.1145/384198.384203(20-28)Online publication date: 1-Aug-2001
https://dl.acm.org/doi/10.1145/384198.384203
Kang DCrago SSuh JHong SPande S(2001)Power-Aware Design Synthesis Techniques for Distributed Real-Time SystemsProceedings of the ACM SIGPLAN workshop on Languages, compilers and tools for embedded systems10.1145/384197.384203(20-28)Online publication date: 1-Aug-2001
https://dl.acm.org/doi/10.1145/384197.384203
Kang DCrago SSuh J(2001)Power-Aware Design Synthesis Techniques for Distributed Real-Time SystemsACM SIGPLAN Notices10.1145/384196.38420336:8(20-28)Online publication date: 1-Aug-2001
https://dl.acm.org/doi/10.1145/384196.384203
Bambha NBhattacharyya STeich JZitzler EMadsen JHenkel JHu X(2001)Hybrid global/local search strategies for dynamic voltage scaling in embedded multiprocessorsProceedings of the ninth international symposium on Hardware/software codesign10.1145/371636.371744(243-248)Online publication date: 25-Apr-2001
https://dl.acm.org/doi/10.1145/371636.371744

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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

Media

Figures

Other

Tables

View Table of Contents