skip to main content
10.1145/1450135.1450176acmconferencesArticle/Chapter ViewAbstractPublication PagesesweekConference Proceedingsconference-collections
research-article

SPaC: a symbolic pareto calculator

Published: 19 October 2008 Publication History

Abstract

The compositional computation of Pareto points in multi-dimensional optimization problems is an important means to efficiently explore the optimization space. This paper presents a symbolic Pareto calculator, SPaC, for the algebraic computation of multidimensional trade-offs. SPaC uses BDDs as a representation for solution sets and operations on them. The tool can be used in multi-criteria optimization and design-space exploration of embedded systems. The paper describes the design and implementation of Pareto algebra operations, and it shows that BDDs can be used effectively in Pareto optimization.

References

[1]
P.A. Abdulla et al. Regular model checking made simple and efficient. In CONCUR '02, p. 116--130. Springer, 2002.
[2]
M. Akbar et al. Solving the multidimensional multiplechoice knapsack problem by constructing convex hulls. Computers and Operations Research, 33(5):1259--1273, 2006.
[3]
R. Berghammer, B. Leoniuk, U. Milanese. Implementation of relational algebra using binary decision diagrams. ReIMICS '01, p. 241--257, 2002.
[4]
R.E. Bryant. Graph-based algorithms for boolean function manipulation. IEEE Trans. Comput., 35(8):677--691, 1986.
[5]
R.E. Bryant. Symbolic boolean manipulation with ordered Binary-decision diagrams. ACM Computing Surveys, 24(3):293--318, 1992.
[6]
M. Ciesielski et al. Taylor expansion diagrams: A canonical representation for verification of data flow designs. IEEE Trans. Comput., 55(9):1188--1201, 2006.
[7]
M. Geilen and T. Basten. A calculator for Pareto points. In DATE '07, p. 285--290, 2007.
[8]
M. Geilen, T. Basten, B. Theelen, R. Otten. An algebra of Pareto points. Fundamenta Informaticae, 78(1):35--74, 2007.
[9]
J.G. Henriksen et al. Mona: Monadic second-order logic in practice. In TACAS '95, p. 89--110, 1995.
[10]
R. Hoes et al. Analysing QoS trade-offs in wireless sensor networks. In MSWiM '07, p. 60--69. ACM, 2007.
[11]
J.R. Burch et al. Symbolic Model Checking: 1020 States and Beyond. In LICS '90, p. 1--33. IEEE CS, 1990.
[12]
O. Lhoták and L. Hendren. Jedd: a bdd-based relational extension of java. SIGPLAN Not., 39(6):158--169, 2004.
[13]
F. Somenzi. Cudd: Cu decision diagram package, http://vlsi.colorado.edu/~fabio/cudd.

Cited By

View all
  • (2010)Sal/SvmVirtual Machines and Intermediate Languages10.1145/1941054.1941055(1-10)Online publication date: 17-Oct-2010
  • (2010)Designing heterogeneous embedded network-on-chip platforms with users in mindIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2010.204904529:9(1301-1314)Online publication date: 1-Sep-2010
  • (2009)User-centric design space exploration for heterogeneous network-on-chip platformsProceedings of the Conference on Design, Automation and Test in Europe10.5555/1874620.1874627(15-20)Online publication date: 20-Apr-2009
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
CODES+ISSS '08: Proceedings of the 6th IEEE/ACM/IFIP international conference on Hardware/Software codesign and system synthesis
October 2008
288 pages
ISBN:9781605584706
DOI:10.1145/1450135
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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 19 October 2008

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. binay decision diagram
  2. embedded systems
  3. pareto algeba

Qualifiers

  • Research-article

Conference

ESWEEK 08
ESWEEK 08: Fourth Embedded Systems Week
October 19 - 24, 2008
GA, Atlanta, USA

Acceptance Rates

CODES+ISSS '08 Paper Acceptance Rate 44 of 143 submissions, 31%;
Overall Acceptance Rate 280 of 864 submissions, 32%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)2
  • Downloads (Last 6 weeks)0
Reflects downloads up to 18 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2010)Sal/SvmVirtual Machines and Intermediate Languages10.1145/1941054.1941055(1-10)Online publication date: 17-Oct-2010
  • (2010)Designing heterogeneous embedded network-on-chip platforms with users in mindIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2010.204904529:9(1301-1314)Online publication date: 1-Sep-2010
  • (2009)User-centric design space exploration for heterogeneous network-on-chip platformsProceedings of the Conference on Design, Automation and Test in Europe10.5555/1874620.1874627(15-20)Online publication date: 20-Apr-2009
  • (2009)User-centric design space exploration for heterogeneous Network-on-Chip platforms2009 Design, Automation & Test in Europe Conference & Exhibition10.1109/DATE.2009.5090626(15-20)Online publication date: Apr-2009

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media