Article

An integer linear programming based approach for parallelizing applications in On-chip multiprocessors

Authors:

U. SezerAuthors Info & Claims

DAC '02: Proceedings of the 39th annual Design Automation Conference

Pages 703 - 706

https://doi.org/10.1145/513918.514096

Published: 10 June 2002 Publication History

Abstract

With energy consumption becoming one of the first-class optimization parameters in computer system design, compilation techniques that consider performance and energy simultaneously are expected to play a central role. In particular, compiling a given application code under performance and energy constraints is becoming an important problem. In this paper, we focus on an on-chip multiprocessor architecture and present a parallelization strategy based on integer linear programming. Given an array-intensive application, our optimization strategy determines the number of processors to be used in executing each nest based on the objective function and additional compilation constraints provided by the user. Our initial experience with this strategy shows that it is very successful in optimizing array-intensive applications on on chip multiprocessors under energy and performance constraints.

References

[1]

System-On-A-Chip Mimics Human Vision. http://content.techweb.com/wire/story/TWB20000309S0002

[2]

R. I. Bahar and S. Manne. Power and energy reduction via pipeline balancing. In Proc. the 28th Annual International Symposium on Computer Architecture, pages 218--229, 2001.

Digital Library

[3]

A. Chandrakasan, W. J. Bowhill, and F. Fox. Design of High-Performance Microprocessor Circuits. IEEE Press, 2001.

Digital Library

[4]

Chip Multiprocessing. http://industry.java.sun.com/javanews/stories/ print/0,1797,32080,00.html

[5]

Chip Multiprocessing. ITWorld.Com, http://www.itworld.com/Comp/1092/CWSTO54343/

[6]

T. M. Conte, K.N. Menezes, S. W. Sathaye, and M. C. Toburen. System-level power consumption modeling and tradeoff analysis techniques for superscalar processor design. IEEE Transactions on VLSI Systems, vol 8, no. 2, April 2000.

Digital Library

[7]

M. Kamble and K. Ghose. Analytical energy dissipation models for low power caches. In Proc. International Symposium on Low Power Electronics and Design, August 1997.

Digital Library

[8]

V. Krishnan and J. Torrellas. A chip multiprocessor architecture with speculative multi-threading. IEEE Transactions on Computers, Special Issue on Multi-threaded Architecture, September 1999.

Digital Library

[9]

MAJC-5200. http://www.sun.com/microelectronics/MAJC/5200wp.html

[10]

D. Marculescu. Profile-driven code execution for low power dissipation. In Proc. the International Symposium on Low Power Electronics and Design, pp. 253--255, 2000.

Digital Library

[11]

MP98: a mobile processor. http://www.labs.nec.co.jp/MP98/top-e.htm.

[12]

B. A. Nayfeh, L. Hammond, and K. Olukotun. Evaluating alternatives for a multiprocessor microprocessor. In Proc. the 23rd Intl. Symp. on Computer Architecture, pp. 66--77, Philadelphia, PA, 1996.

Digital Library

[13]

hydra K. Olukotun, B. A. Nayfeh, L. Hammond, K. Wilson, and K. Chang. The case for a single chip multiprocessor. In Proc. the 7th Int'l Conference on Architectural Support for Programming Languages and Operating Systems, ACM Press, New York, 1996, pp. 2--11.

Digital Library

[14]

H. Schwab. lp_solve Mixed Integer Linear Program Solver, ftp://ftp.es.ele.tue.nl/pub/lp_solve/

[15]

N. Vijaykrishnan, M. Kandemir, M. J. Irwin, H. Y. Kim, and W. Ye. Energy-driven integrated hardware-software optimizations using SimplePower. In Proc. International Symposium on Computer Architecture, June 2000.

Digital Library

[16]

M. Wolfe. High Performance Compilers for Parallel Computing, Addison-Wesley Publishing Company, 1996.

Digital Library

[17]

S. Wilton and N. Jouppi. Cacti: An enhanced cache access and cycle time model. IEEE Journal of Solid-State Circuits, May 1996.

Cited By

Skalistis SSimalatsar A(2017)Near-optimal deployment of dataflow applications on many-core platforms with real-time guaranteesProceedings of the Conference on Design, Automation & Test in Europe10.5555/3130379.3130562(752-757)Online publication date: 27-Mar-2017
https://dl.acm.org/doi/10.5555/3130379.3130562
Langer ATotoni EPalekar UKalé L(2015)Energy-efficient computing for HPC workloads on heterogeneous manycore chipsProceedings of the Sixth International Workshop on Programming Models and Applications for Multicores and Manycores10.1145/2712386.2712396(11-19)Online publication date: 7-Feb-2015
https://dl.acm.org/doi/10.1145/2712386.2712396
Vijayalakshmi SAnpalagan AKothari DWoungang IObaidat M(2014)An analytical study of resource division and its impact on power and performance of multi-core processorsThe Journal of Supercomputing10.1007/s11227-014-1086-068:3(1265-1279)Online publication date: 1-Jun-2014
https://dl.acm.org/doi/10.1007/s11227-014-1086-0
Show More Cited By

Index Terms

An integer linear programming based approach for parallelizing applications in On-chip multiprocessors
1. Software and its engineering
  1. Software notations and tools
    1. Compilers

Recommendations

Optimizing Array-Intensive Applications for On-Chip Multiprocessors

With energy consumption becoming one of the first-class optimization parameters in computer system design, compilation techniques that consider performance and energy simultaneously are expected to play a central role. In particular, compiling a given ...
Mixed-integer quadratic programming

This paper considers mixed-integer quadratic programs in which the objective function is quadratic in the integer and in the continuous variables, and the constraints are linear in the variables of both types. The generalized Benders' decomposition is a ...
An integer programming approach for linear programs with probabilistic constraints

Linear programs with joint probabilistic constraints (PCLP) are difficult to solve because the feasible region is not convex. We consider a special case of PCLP in which only the right-hand side is random and this random vector has a finite distribution. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

DAC '02: Proceedings of the 39th annual Design Automation Conference

June 2002

956 pages

ISBN:1581134614

DOI:10.1145/513918

General Chair:
Bryan Ackland
Agere Systems, Inc., Holmdel, NJ

Copyright © 2002 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

SIGDA: ACM Special Interest Group on Design Automation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 10 June 2002

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

DAC02

Sponsor:

SIGDA

DAC02: 39th Design Automation Conference

June 10 - 14, 2002

Louisiana, New Orleans, USA

Acceptance Rates

DAC '02 Paper Acceptance Rate 147 of 491 submissions, 30%;

Overall Acceptance Rate 1,770 of 5,499 submissions, 32%

Upcoming Conference

DAC '25

Sponsor:
sigda

62nd ACM/IEEE Design Automation Conference

June 22 - 26, 2025

San Francisco , CA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

18
Total Citations
View Citations
27
Total Downloads

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

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Skalistis SSimalatsar A(2017)Near-optimal deployment of dataflow applications on many-core platforms with real-time guaranteesProceedings of the Conference on Design, Automation & Test in Europe10.5555/3130379.3130562(752-757)Online publication date: 27-Mar-2017
https://dl.acm.org/doi/10.5555/3130379.3130562
Langer ATotoni EPalekar UKalé L(2015)Energy-efficient computing for HPC workloads on heterogeneous manycore chipsProceedings of the Sixth International Workshop on Programming Models and Applications for Multicores and Manycores10.1145/2712386.2712396(11-19)Online publication date: 7-Feb-2015
https://dl.acm.org/doi/10.1145/2712386.2712396
Vijayalakshmi SAnpalagan AKothari DWoungang IObaidat M(2014)An analytical study of resource division and its impact on power and performance of multi-core processorsThe Journal of Supercomputing10.1007/s11227-014-1086-068:3(1265-1279)Online publication date: 1-Jun-2014
https://dl.acm.org/doi/10.1007/s11227-014-1086-0
Javaid HParameswaran SJavaid HParameswaran S(2013)Literature SurveyPipelined Multiprocessor System-on-Chip for Multimedia10.1007/978-3-319-01113-4_2(21-52)Online publication date: 26-Nov-2013
https://doi.org/10.1007/978-3-319-01113-4_2
Ozturk OKandemir MKrishna Narayanan S(2012)Workload Clustering for Increasing Energy Savings on Embedded MPSOCSEnergy‐Efficient Distributed Computing Systems10.1002/9781118342015.ch19(549-565)Online publication date: 30-Jul-2012
https://doi.org/10.1002/9781118342015.ch19
Cordes DMarwedel PMallik AGivargis TDonlin A(2010)Automatic parallelization of embedded software using hierarchical task graphs and integer linear programmingProceedings of the eighth IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis10.1145/1878961.1879009(267-276)Online publication date: 24-Oct-2010
https://dl.acm.org/doi/10.1145/1878961.1879009
Javaid HHe XIgnjatovic AParameswaran SGivargis TDonlin A(2010)Optimal synthesis of latency and throughput constrained pipelined MPSoCs targeting streaming applicationsProceedings of the eighth IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis10.1145/1878961.1878978(75-84)Online publication date: 24-Oct-2010
https://dl.acm.org/doi/10.1145/1878961.1878978
Javaid HIgnjatovic AParameswaran S(2010)Rapid design space exploration of application specific heterogeneous pipelined multiprocessor systemsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2010.206135329:11(1777-1789)Online publication date: 1-Nov-2010
https://dl.acm.org/doi/10.1109/TCAD.2010.2061353
Ju LHu WXiang LChen T(2010)Shared Register File Based ILP for MulticoreProceedings of the 2010 IEEE/ACM Int'l Conference on Green Computing and Communications & Int'l Conference on Cyber, Physical and Social Computing10.1109/GreenCom-CPSCom.2010.15(197-204)Online publication date: 18-Dec-2010
https://dl.acm.org/doi/10.1109/GreenCom-CPSCom.2010.15
Xian CLu YLi ZLevitan S(2007)Energy-aware scheduling for real-time multiprocessor systems with uncertain task execution timeProceedings of the 44th annual Design Automation Conference10.1145/1278480.1278648(664-669)Online publication date: 4-Jun-2007
https://dl.acm.org/doi/10.1145/1278480.1278648
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