[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.1145/2024724.2024818acmconferencesArticle/Chapter ViewAbstractPublication PagesdacConference Proceedingsconference-collections
research-article

Supervised design space exploration by compositional approximation of Pareto sets

Published: 05 June 2011 Publication History

Abstract

Technology scaling allows the integration of billions of transistors on the same die but CAD tools struggle in keeping up with the increasing design complexity. Design productivity for multi-core SoCs increasingly depends on creating and maintaining reusable components and hierarchically combining them to form larger composite cores. Characterizing such composite cores with respect to their power/performance tradeoffs is critical for design reuse across various products and relies heavily on synthesis tools. We present CAPS, an online adaptive algorithm that efficiently explores the design space of any given core and returns an accurate characterization of its implementation tradeoffs in terms of an approximate Pareto set. It does so by supervising the order of the time-consuming logic-synthesis runs on the core's components. Our algorithm can provably achieve the desired precision on the approximation in the shortest possible time, without having any a-priori information on any component. We also show that, in practice, CAPS works even better than what is guaranteed by the theory.

References

[1]
Opencores. www.opencores.org/.
[2]
G. Ascia, V. Catania, A. G. D. Nuovo, M. Palesi, and D. Patti. Efficient design space exploration for application specific systems-on-a-chip. Journal of Systems Architecture, 53(10):733--750, Oct. 2007.
[3]
O. Azizi, A. Mahesri, J. P. Stevenson, S. J. Patel, and M. Horowitz. An integrated framework for joint design space exploration of microarchitecture and circuits. In Proc. of the Conf. on Design, Automation and Test in Europe, pages 250--255, Mar. 2010.
[4]
G. Beltrame, L. Fossati, and D. Sciuto. Decision-theoretic design space exploration of multiprocessor platforms. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, 29(7):1083--1095, July 2010.
[5]
U. Bordoloi, H. P. Huynh, S. Chakraborty, and T. Mitra. Evaluating design trade-offs in customizable processors. In Proc. of the Design Automation Conference (DAC), pages 244--249, July 2009.
[6]
S. Borkar. Design perspectives on 22nm CMOS and beyond. In Proc. of the Design Automation Conference (DAC), pages 93--94, July 2009.
[7]
A. Darabiha, J. Rose, and W. J. MacLean. Video-rate stereo depth measurement on programmable hardware. In Proc. of the IEEE Conference on Computer Vision and Pattern Recognition, pages 203--210, June 2003.
[8]
I. Diakonikolas. Approximation of Multiobjective Optimization Problems. PhD thesis, Columbia University, 2010.
[9]
I. Diakonikolas and M. Yannakakis. Succinct Approximate Convex Pareto Curves. In Proc. 19th ACM-SIAM Symposium on Discrete Algorthims (SODA), pages 74--83, Jan. 2008.
[10]
I. Diakonikolas and M. Yannakakis. Small approximate Pareto sets for bi-objective shortest paths and other problems. SIAM Journal on Computing, 39:1340--1371, 2009.
[11]
T. Eeckelaert, T. McConaghy, and G. Gielen. Efficient multiobjective synthesis of analog circuits using hierarchical pareto-optimal performance hypersurfaces. In Proc. of the Conf. on Design, Automation and Test in Europe, pages 1070--1075, Mar. 2005.
[12]
M. Ehrgott. Multicriteria optimization. Springer-Verlag, 2005.
[13]
T. Givargis, F. Vahid, and J. Henkel. System-level exploration for pareto-optimal configurations in parameterized system-on-a-chip. IEEE Trans. on Very Large Scale Integration Systems, 10(4):416--422, Aug. 2002.
[14]
M. Horowitz, E. Alon, D. Patil, S. Naffziger, R. Kumar, and K. Bernstein. Scaling, power, and the future of CMOS. In IEEE International Electron Devices Meeting, pages 9--15, Dec. 2005.
[15]
ITRS. The International Technology Roadmap for Semiconductors. Available at http://public.itrs.net.
[16]
H.-Y. Liu, I. Diakonikolas, M. Petracca, and L. P. Carloni. An optimal online algorithm for compositional approximation of pareto sets. Technical Report CUCS-014-11, Dept. of Computer Science, Columbia University, 2011.
[17]
G. Palermo, C. Silvano, and V. Zaccaria. Respir: A response surface-based pareto iterative refinement for application-specific design space exploration. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, 28(12):1816--1829, Dec. 2009.
[18]
C. Papadimitriou and M. Yannakakis. On the Approximability of Trade-offs and Optimal Access of Web Sources. In Proc. 41st IEEE Symp. on Foundations of Computer Science (FOCS), pages 86--92, Nov. 2000.
[19]
B. C. Schafer and K. Wakabayashi. Design space exploration acceleration through operation clustering. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, 29(1):153--157, Jan. 2010.
[20]
A. Singhee and P. Castalino. Pareto sampling: choosing the right weights by derivative pursuit. In Proc. of the Design Automation Conference (DAC), pages 913--916, July 2010.
[21]
S. Tiwary, P. Tiwary, and R. Rutenbar. Generation of yield-aware pareto surfaces for hierarchical circuit design space exploration. In Proc. of the Design Automation Conference (DAC), pages 31--36, July 2006.
[22]
S. Vassilvitskii and M. Yannakakis. Efficiently computing succinct trade-off curves. Theoretical Computer Science, 348(2--3):334--356, 2005.

Cited By

View all
  • (2023)PTPT: Physical Design Tool Parameter Tuning via Multi-Objective Bayesian OptimizationIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2022.316785842:1(178-189)Online publication date: Jan-2023
  • (2022)Learning from the Past: Efficient High-level Synthesis Design Space Exploration for FPGAsACM Transactions on Design Automation of Electronic Systems10.1145/349553127:4(1-23)Online publication date: 12-Feb-2022
  • (2022)Performance Evaluation of Algorithms for Optimizing Processor Simulator Parameters2022 IEEE 16th International Conference on Solid-State & Integrated Circuit Technology (ICSICT)10.1109/ICSICT55466.2022.9963250(1-3)Online publication date: 25-Oct-2022
  • Show More Cited By

Index Terms

  1. Supervised design space exploration by compositional approximation of Pareto sets

    Recommendations

    Comments

    Please enable JavaScript to view thecomments powered by Disqus.

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    DAC '11: Proceedings of the 48th Design Automation Conference
    June 2011
    1055 pages
    ISBN:9781450306362
    DOI:10.1145/2024724
    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: 05 June 2011

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. design reuse
    2. system-level design
    3. system-on-chip

    Qualifiers

    • Research-article

    Conference

    DAC '11
    Sponsor:

    Acceptance Rates

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

    Upcoming Conference

    DAC '25
    62nd ACM/IEEE Design Automation Conference
    June 22 - 26, 2025
    San Francisco , CA , USA

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)9
    • Downloads (Last 6 weeks)4
    Reflects downloads up to 21 Dec 2024

    Other Metrics

    Citations

    Cited By

    View all
    • (2023)PTPT: Physical Design Tool Parameter Tuning via Multi-Objective Bayesian OptimizationIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2022.316785842:1(178-189)Online publication date: Jan-2023
    • (2022)Learning from the Past: Efficient High-level Synthesis Design Space Exploration for FPGAsACM Transactions on Design Automation of Electronic Systems10.1145/349553127:4(1-23)Online publication date: 12-Feb-2022
    • (2022)Performance Evaluation of Algorithms for Optimizing Processor Simulator Parameters2022 IEEE 16th International Conference on Solid-State & Integrated Circuit Technology (ICSICT)10.1109/ICSICT55466.2022.9963250(1-3)Online publication date: 25-Oct-2022
    • (2020)Exact Design Space Exploration Based on Consistent ApproximationsElectronics10.3390/electronics90710579:7(1057)Online publication date: 27-Jun-2020
    • (2018)Design Automation for Smart Building SystemsProceedings of the IEEE10.1109/JPROC.2018.2856932106:9(1680-1699)Online publication date: Sep-2018
    • (2017)COSMOSACM Transactions on Embedded Computing Systems10.1145/312656616:5s(1-22)Online publication date: 27-Sep-2017
    • (2017)Value driven tradespace exploration: A new approach to optimize reliability specification and allocation2017 Annual Reliability and Maintainability Symposium (RAMS)10.1109/RAM.2017.7889655(1-7)Online publication date: 2017
    • (2016)Selecting Heterogeneous Cores for DiversityACM Transactions on Architecture and Code Optimization10.1145/301416513:4(1-25)Online publication date: 16-Dec-2016
    • (2015)Four Metrics to Evaluate Heterogeneous MulticoresACM Transactions on Architecture and Code Optimization10.1145/282995012:4(1-25)Online publication date: 16-Nov-2015
    • (2012)Compositional system-level design exploration with planning of high-level synthesisProceedings of the Conference on Design, Automation and Test in Europe10.5555/2492708.2492870(641-646)Online publication date: 12-Mar-2012
    • Show More Cited By

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Media

    Figures

    Other

    Tables

    Share

    Share

    Share this Publication link

    Share on social media