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

research-article

"Smart" design space sampling to predict Pareto-optimal solutions

Authors:

Marcela Zuluaga,

Andreas Krause,

Markus PüschelAuthors Info & Claims

LCTES '12: Proceedings of the 13th ACM SIGPLAN/SIGBED International Conference on Languages, Compilers, Tools and Theory for Embedded Systems

Pages 119 - 128

https://doi.org/10.1145/2248418.2248436

Published: 12 June 2012 Publication History

Abstract

Many high-level synthesis tools offer degrees of freedom in mapping high-level specifications to Register-Transfer Level descriptions. These choices do not affect the functional behavior but span a design space of different cost-performance tradeoffs. In this paper we present a novel machine learning-based approach that efficiently determines the Pareto-optimal designs while only sampling and synthesizing a fraction of the design space. The approach combines three key components: (1) A regression model based on Gaussian processes to predict area and throughput based on synthesis training data. (2) A "smart" sampling strategy, GP-PUCB, to iteratively refine the model by carefully selecting the next design to synthesize to maximize progress. (3) A stopping criterion based on assessing the accuracy of the model without access to complete synthesis data. We demonstrate the effectiveness of our approach using IP generators for discrete Fourier transforms and sorting networks. However, our algorithm is not specific to this application and can be applied to a wide range of Pareto front prediction problems.

References

[1]

C. Coello, G. B. Lamont, and D. Veldhuizen. Evolutionary Algorithms for Solving Multi-Objective Problems (Genetic and Evolutionary Computation). Springer-Verlag New York, Inc., Secaucus, NJ, USA, 2006.

Digital Library

[2]

L. Deng, K. Sobti, and C. Chakrabarti. Accurate Models for Estimating Area and Power of FPGA Implementations. In Proc. of International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 1417--1420, 2008.

[3]

M. Ehrgott and X. Gandibleux. A Survey and Annotated Bibliography of Multiobjective Combinatorial Optimization. OR Spektrum, (22):425--460, 2000.

[4]

M. Emmerich, K. Giannakoglou, and B. Naujoks. Single- and Multiobjective Evolutionary Optimization Assisted by Gaussian Random Field Metamodels. IEEE Transactions on Evolutionary Computation, 10(4):421--439, 2006.

Digital Library

[5]

J. Knowles. ParEGO: a Hybrid Algorithm with On-line Landscape Approximation for Expensive Multiobjective Optimization Problems. IEEE Transactions on Evolutionary Computation, 10(1):50--66, 2006.

Digital Library

[6]

S. Künzli, L. Thiele, and E. Zitzler. Modular Design Space Exploration Framework for Embedded Systems. IEE Proceedings Computers & Digital Techniques, 152(2):183--192, 2005.

[7]

P. A. Milder, M. Ahmad, J. C. Hoe, and M. Püschel. Fast and Accurate Resource Estimation of Automatically Generated Custom DFT IP Cores. In Proc. of International Symposium on Field-Programmable Gate Arrays (FPGA), pages 211--220, 2006.

Digital Library

[8]

P. A. Milder, F. Franchetti, J. C. Hoe, and M. Püschel. Formal Datapath Representation and Manipulation for Implementing DSP Transforms. In Proc. of Design Automation Conference (DAC), pages 385--390, 2008.

Digital Library

[9]

G. Palermo, C. Silvano, and V. Zaccaria. ReSPIR: A Response Surface-Based Pareto Iterative Refinement for Application-Specific Design Space Exploration. Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on, 28(12):1816--1829, dec. 2009.

Digital Library

[10]

C. Rasmussen and H. Nickisch. Gaussian Process Regression and Classification Toolbox Version 3.1 for Matlab 7.x, 2010.

[11]

C. Rasmussen and C. K. I. Williams. Gaussian Processes for Machine Learning. MIT Press, 2006.

Digital Library

[12]

B. So, M. W. Hall, and P. C. Diniz. A Compiler Approach to Fast Hardware Design Space Exploration in FPGA-Based Systems. In Proc. of Programming Language Design and Implementation (PLDI), pages 165--176, 2002.

Digital Library

[13]

N. Srinivas, A. Krause, S. Kakade, and M. Seeger. Gaussian Process Optimization in the Bandit Setting: No Regret and Experimental Design. In Proc. of International Conference on Machine Learning (ICML), 2010.

[14]

L. Yan, T. Srikanthan, and N. Gang. Area and Delay Estimation for FPGA Implementation of Coarse-Grained Reconfigurable Architectures. In Proc. of Languages, Compilers, and Tools for Embedded Systems, pages 182--188, 2006.

Digital Library

[15]

Q. Zhang, W. Liu, E. Tsang, and B. Virginas. Expensive Multiobjective Optimization by MOEA/D with Gaussian Process Model. IEEE Transactions on Evolutionary Computation, 14(3):456--474, 2010.

Digital Library

[16]

E. Zitzler, D. Brockhoff, and L. Thiele. The Hypervolume Indicator Revisited: on the Design of Pareto-compliant Indicators via Weighted Integration. In Proc. of the 4th International Conference on Evolutionary Multi-criterion Optimization (EMO), pages 862--876, 2007.

Digital Library

[17]

E. Zitzler and S. Künzli. Indicator-based Selection in Multiobjective Search. In Proc. of the 8th International Conference on Parallel Problem Solving from Nature, pages 832--842, 2004.

[18]

E. Zitzler, M. Laumanns, and L. Thiele. SPEA2: Improving the Strength Pareto Evolutionary Algorithm for Multiobjective Optimization. In Evolutionary Methods for Design, Optimisation, and Control, pages 95--100, 2002.

[19]

M. Zuluaga, P. Milder, and M. Püschel. Computer Generation of Streaming Sorating Nnetworks. In Proceedings of the 45th Annual ACM/IEEE Conference on Design Automation (DAC), 2012.

Digital Library

Cited By

Taghipour PGranger EBlaquière Y(2024)Hybrid Graph Representation and Learning Framework for High-Level Synthesis Design Space ExplorationIEEE Access10.1109/ACCESS.2024.350960612(189574-189589)Online publication date: 2024
https://doi.org/10.1109/ACCESS.2024.3509606
Kandpal J(2023)Machine Learning–Based VLSI Test and VerificationMachine Learning for VLSI Chip Design10.1002/9781119910497.ch3(33-50)Online publication date: 23-Jun-2023
https://doi.org/10.1002/9781119910497.ch3
Belwal MRamesh T(2022)N-PIR: A Neighborhood-Based Pareto Iterative Refinement Approach for High-Level SynthesisArabian Journal for Science and Engineering10.1007/s13369-022-07177-748:2(2155-2171)Online publication date: 20-Aug-2022
https://doi.org/10.1007/s13369-022-07177-7
Show More Cited By

Index Terms

"Smart" design space sampling to predict Pareto-optimal solutions

Recommendations

Learning from the Past: Efficient High-level Synthesis Design Space Exploration for FPGAs
The quest to democratize the use of Field-Programmable Gate Arrays (FPGAs) has given High-Level Synthesis (HLS) the final push to be widely accepted with FPGA vendors strongly supporting this VLSI design methodology to expand the FPGA user base. HLS takes ...
"Smart" design space sampling to predict Pareto-optimal solutions
LCTES '12

Many high-level synthesis tools offer degrees of freedom in mapping high-level specifications to Register-Transfer Level descriptions. These choices do not affect the functional behavior but span a design space of different cost-performance tradeoffs. ...
On learning-based methods for design-space exploration with high-level synthesis
DAC '13: Proceedings of the 50th Annual Design Automation Conference

This paper makes several contributions to address the challenge of supervising HLS tools for design space exploration (DSE). We present a study on the application of learning-based methods for the DSE problem, and propose a learning model for HLS that ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

LCTES '12: Proceedings of the 13th ACM SIGPLAN/SIGBED International Conference on Languages, Compilers, Tools and Theory for Embedded Systems

June 2012

153 pages

ISBN:9781450312127

DOI:10.1145/2248418

General Chair:
Reinhard Wilhelm
Saarland University Saarbrücken
,
Program Chairs:
Heiko Falk
Ulm University
,
Wang Yi
Uppsala University

ACM SIGPLAN Notices Volume 47, Issue 5
LCTES '12
MAY 2012
152 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/2345141
Issue’s Table of Contents

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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 June 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

LCTES '12

Sponsor:

LCTES '12: SIGPLAN/SIGBED Conference on Languages, Compilers and Tools for Embedded Systems 2012

June 12 - 13, 2012

Beijing, China

Acceptance Rates

Overall Acceptance Rate 116 of 438 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

29
Total Citations
View Citations
478
Total Downloads

Downloads (Last 12 months)11
Downloads (Last 6 weeks)3

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Taghipour PGranger EBlaquière Y(2024)Hybrid Graph Representation and Learning Framework for High-Level Synthesis Design Space ExplorationIEEE Access10.1109/ACCESS.2024.350960612(189574-189589)Online publication date: 2024
https://doi.org/10.1109/ACCESS.2024.3509606
Kandpal J(2023)Machine Learning–Based VLSI Test and VerificationMachine Learning for VLSI Chip Design10.1002/9781119910497.ch3(33-50)Online publication date: 23-Jun-2023
https://doi.org/10.1002/9781119910497.ch3
Belwal MRamesh T(2022)N-PIR: A Neighborhood-Based Pareto Iterative Refinement Approach for High-Level SynthesisArabian Journal for Science and Engineering10.1007/s13369-022-07177-748:2(2155-2171)Online publication date: 20-Aug-2022
https://doi.org/10.1007/s13369-022-07177-7
Reyes Fernandez de Bulnes DMaldonado YTrujillo L(2020)Development of Multiobjective High-Level Synthesis for FPGAsScientific Programming10.1155/2020/70950482020Online publication date: 1-Jan-2020
https://dl.acm.org/doi/10.1155/2020/7095048
Xie ZFang GHuang YRen HZhang YKhailany BFang SHu JChen YBarboza E(2020)FIST: A Feature-Importance Sampling and Tree-Based Method for Automatic Design Flow Parameter Tuning2020 25th Asia and South Pacific Design Automation Conference (ASP-DAC)10.1109/ASP-DAC47756.2020.9045201(19-25)Online publication date: Jan-2020
https://doi.org/10.1109/ASP-DAC47756.2020.9045201
Smirnov FPourmohseni BGlaß MTeich J(2019)IGOR, Get Me the Optimum! Prioritizing Important Design Decisions During the DSE of Embedded SystemsACM Transactions on Embedded Computing Systems10.1145/335820418:5s(1-22)Online publication date: 8-Oct-2019
https://dl.acm.org/doi/10.1145/3358204
Ferretti LAnsaloni GPozzi L(2018)Lattice-Traversing Design Space Exploration for High Level Synthesis2018 IEEE 36th International Conference on Computer Design (ICCD)10.1109/ICCD.2018.00040(210-217)Online publication date: Oct-2018
https://doi.org/10.1109/ICCD.2018.00040
Ogilvie WPetoumenos PWang ZLeather HReddi VSmith ATang L(2017)Minimizing the cost of iterative compilation with active learningProceedings of the 2017 International Symposium on Code Generation and Optimization10.5555/3049832.3049859(245-256)Online publication date: 4-Feb-2017
https://dl.acm.org/doi/10.5555/3049832.3049859
Morse JAraiza-Illan DEder KLawry JRichards A(2017)A fuzzy approach to qualification in design exploration for autonomous robots and systems2017 IEEE International Conference on Fuzzy Systems (FUZZ-IEEE)10.1109/FUZZ-IEEE.2017.8015456(1-6)Online publication date: Jul-2017
https://doi.org/10.1109/FUZZ-IEEE.2017.8015456
Ogilvie WPetoumenos PWang ZLeather H(2017)Minimizing the cost of iterative compilation with active learning2017 IEEE/ACM International Symposium on Code Generation and Optimization (CGO)10.1109/CGO.2017.7863744(245-256)Online publication date: Feb-2017
https://doi.org/10.1109/CGO.2017.7863744
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.

Figures

Tables

Media

View Table of Conten