Article

Effective graph theoretic techniques for the generalized low power binding problem

Authors:

Azadeh Davoodi,

Ankur SrivastavaAuthors Info & Claims

ISLPED '03: Proceedings of the 2003 international symposium on Low power electronics and design

Pages 152 - 157

https://doi.org/10.1145/871506.871544

Published: 25 August 2003 Publication History

Get Access

Abstract

This paper proposes two very fast graph theoretic heuristics for the low power binding problem given fixed number of resources and multiple architectures for the resources. First the generalized low power binding problem is formulated as an Integer Linear Programming(ILP) problem which happens to be an NP-complete task to solve. Then two polynomial-time heuristics are proposed that provide a speedup of up to 13.7 with an extremely low penalty for power when compared to the optimal ILP solution for our selected benchmarks.

References

[1]

A. Raghunathan and N. Jha. "An ILP Formulation for Low Power Based on Minimizing Switched Capacitance During Datapath Allocation ". In Procs of IEEE Symposium on Circuits and Systems 1995.

Crossref

Google Scholar

[2]

A. Srivastava. "Predictability:Definition, Analysis and Optimization ". In Procs of International Conference on Computer Aided Design Nov 2002.

Digital Library

Google Scholar

[3]

C. Lee, M. Potkonjak and W.H. Mangione-Smith. "MediaBench:A Tool for Evaluating and Synthesizing Multimedia and Communications Systems ". In International Symposium on Microarchitecture 1997.

Digital Library

Google Scholar

[4]

J.M.Chang and M.Pedram."Low Power Register Allocation and Binding ". In Proc. Design Automation Conference pages 29--35, June 1995.

Digital Library

Google Scholar

[5]

L. Kruse, E. Schmidt, G. Jochens, A. Stammerman, A. Schulz, E. Maciiand W. Nebel. "Estimation of Lower and Upper Bounds on the Power Consumption from Scheduled Data Flow Graphs ". In IEEE Trans. on VLSI Systems pages 3--14, Feb 2001.

Digital Library

Google Scholar

[6]

S. Ogrenci-Memik, E. Bozorgzadeh, R. Kastner and M. Sarrafzadeh. "A Super Scheduler for Embedded Reconfigurable Systems ". In Procs of International Conference on Computer Aided Design pages 391--394, Nov 2001.

Digital Library

Google Scholar

Cited By

View all

Chabini NWolf W(2007)Register binding guided by the size of variables2007 25th International Conference on Computer Design10.1109/ICCD.2007.4601957(587-594)Online publication date: Oct-2007
https://doi.org/10.1109/ICCD.2007.4601957
Ni MMemik SHassoun S(2006)Thermal-induced leakage power optimization by redundant resource allocationProceedings of the 2006 IEEE/ACM international conference on Computer-aided design10.1145/1233501.1233560(297-302)Online publication date: 5-Nov-2006
https://dl.acm.org/doi/10.1145/1233501.1233560
Ni MMemik S(2006)Thermal-Induced Leakage Power Optimization by Redundant Resource Allocation2006 IEEE/ACM International Conference on Computer Aided Design10.1109/ICCAD.2006.320049(297-302)Online publication date: Nov-2006
https://doi.org/10.1109/ICCAD.2006.320049
Show More Cited By

Index Terms

Effective graph theoretic techniques for the generalized low power binding problem
1. Hardware
  1. Electronic design automation
    1. High-level and register-transfer level synthesis
      1. Datapath optimization
    2. Logic synthesis
      1. Circuit optimization

Recommendations

Effective techniques for the generalized low-power binding problem

This article proposes two very fast graph theoretic heuristics for the low power binding problem given fixed number of resources and multiple architectures for the resources. First, the generalized low power binding problem is formulated as an Integer ...
Scheduling and resource binding for low power
ISSS '95: Proceedings of the 8th international symposium on System synthesis

Abstract: Decisions taken at the earliest steps of the design process may have a significant impact on the characteristics of the final implementation. This paper illustrates how power consumption issues can be tackled during the scheduling and resource-...
Power optimization with power islands synthesis

With the migration to Deep Sub-Micron process technologies, the power consumption of a circuit has come to the forefront of concerns, and as a result, the power has become a critical design parameter. This paper presents a novel high-level synthesis ...

Comments

Information & Contributors

Information

Published In

ISLPED '03: Proceedings of the 2003 international symposium on Low power electronics and design

August 2003

502 pages

ISBN:158113682X

DOI:10.1145/871506

General Chairs:
Ingrid Verbauwhede
University of California, Los Angeles, CA
,
Hyung Roh
Samsung Electronics

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 August 2003

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

ISLPED03

Sponsor:

ISLPED03: International Symposium on Low Power Electronics and Design

August 25 - 27, 2003

Seoul, Korea

Acceptance Rates

ISLPED '03 Paper Acceptance Rate 90 of 221 submissions, 41%;

Overall Acceptance Rate 398 of 1,159 submissions, 34%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
255
Total Downloads

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

Reflects downloads up to 15 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Chabini NWolf W(2007)Register binding guided by the size of variables2007 25th International Conference on Computer Design10.1109/ICCD.2007.4601957(587-594)Online publication date: Oct-2007
https://doi.org/10.1109/ICCD.2007.4601957
Ni MMemik SHassoun S(2006)Thermal-induced leakage power optimization by redundant resource allocationProceedings of the 2006 IEEE/ACM international conference on Computer-aided design10.1145/1233501.1233560(297-302)Online publication date: 5-Nov-2006
https://dl.acm.org/doi/10.1145/1233501.1233560
Ni MMemik S(2006)Thermal-Induced Leakage Power Optimization by Redundant Resource Allocation2006 IEEE/ACM International Conference on Computer Aided Design10.1109/ICCAD.2006.320049(297-302)Online publication date: Nov-2006
https://doi.org/10.1109/ICCAD.2006.320049
Mukherjee RMemik SMemik GRoy KTiwari V(2005)Peak temperature control and leakage reduction during binding in high level synthesisProceedings of the 2005 international symposium on Low power electronics and design10.1145/1077603.1077663(251-256)Online publication date: 8-Aug-2005
https://dl.acm.org/doi/10.1145/1077603.1077663

View Options

Get Access

Login options

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

Cited By

Index Terms

Recommendations

Effective techniques for the generalized low-power binding problem

Scheduling and resource binding for low power

Power optimization with power islands synthesis

Comments

Published In

Sponsors

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Conference

Acceptance Rates

Other Metrics

Article Metrics

Other Metrics

Cited By

Login options

Full Access

PDF

eReader

Abstract

References

Cited By

Index Terms

Recommendations

Effective techniques for the generalized low-power binding problem

Scheduling and resource binding for low power

Power optimization with power islands synthesis

Comments

Information

Published In

Sponsors

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Conference

Acceptance Rates

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Get Access

Login options

Full Access

View options

PDF

eReader

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations