skip to main content
10.1145/1146909.1147028acmconferencesArticle/Chapter ViewAbstractPublication PagesdacConference Proceedingsconference-collections
Article

Design space exploration using time and resource duality with the ant colony optimization

Published: 24 July 2006 Publication History

Abstract

Design space exploration during high level synthesis is often conducted through ad-hoc probing of the solution space using some scheduling algorithm. This is not only time consuming but also very dependent on designer's experience. We propose a novel design exploration method that exploits the duality between the time and resource constrained scheduling problems. Our exploration automatically constructs a high quality time/area tradeoff curve in a fast, effective manner. It uses the MAX-MIN ant colony optimization to solve both the time and resource constrained scheduling problems. We switch between the time and resource constrained algorithms to quickly traverse the design space. Compared to using force directed scheduling exhaustively at every time step, our algorithm provides a significant solution quality savings (average 17.3% reduction of resource counts) with similar run time on a comprehensive benchmark suite constructed with classic and real-life samples. Our algorithms scale well over different applications and problem sizes.

References

[1]
http://express.ece.ucsb.edu/benchmark/.]]
[2]
S. Chaudhuri, S. A. Blythe, and R. A. Walker. A solution methodology for exact design space exploration in a three-dimensional design space. IEEE Trans. Very Large Scale Integr. Syst., 5(1):69--81, 1997.]]
[3]
D. Corne, M. Dorigo, and F. Glover, editors. New Ideas in Optimization. McGraw Hill, London, UK, 1999.]]
[4]
M. Dorigo, V. Maniezzo, and A. Colorni. Ant System: Optimization by a Colony of Cooperating Agents. IEEE Transactions on Systems, Man and Cybernetics, Part-B, 26(1):29--41, February 1996.]]
[5]
R. Dutta, J. Roy, and R. Vemuri. Distributed design-space exploration for high-level synthesis systems. In DAC '92, pages 644--650, Los Alamitos, CA, USA, 1992. IEEE Computer Society Press.]]
[6]
M. J. M. Heijligers, L. J. M. Cluitmans, and J. A. G. Jess. High-level synthesis scheduling and allocation using genetic algorithms. page 11, 1995.]]
[7]
C. Lee, M. Potkonjak, and W. H. Mangione-Smith. MediaBench: a Tool for Evaluating and Synthesizing Multimedia and Communicatons Systems. In Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, 1997.]]
[8]
Y.-L. Lin. Recent developments in high-level synthesis. ACM Trans. Des. Autom. Electron. Syst., 2(1):2--21, 1997.]]
[9]
J. Madsen, J. Grode, P. V. Knudsen, M. E. Petersen, and A. Haxthausen. LYCOS: the Lyngby Co-Synthesis System. Design Automation for Embedded Systems, 2(2):125--63, March 1997.]]
[10]
M. Palesi and T. Givargis. Multi-Objective Design Space Exploration Using GeneticAlgorithms. In Proceedings of the Tenth International Symposium on Hardware/SoftwareCodesign, 2002.]]
[11]
P. G. Paulin and J. P. Knight. Force-directed scheduling in automatic data path synthesis. In 24th ACM/IEEE Conference Proceedings on Design Automation Conference, 1987.]]
[12]
T. Stützle and H. H. Hoos. MAX-MIN Ant System. Future Generation Comput. Systems, 16(9):889--914, September 2000.]]
[13]
G. Wang, W. Gong, B. DeRenzi, and R. Kastner. Ant colony optimizations for resource and timing constrained instruction scheduling. IEEE Transaction on Computer-Aided Design, under review.]]
[14]
G. Wang, W. Gong, and R. Kastner. Instruction scheduling using MAX-MIN ant optimization. In 15th ACM Great Lakes Symposium on VLSI, GLSVLSI'2005, April 2005.]]

Cited By

View all
  • (2024)Enhancing FPGA CAD Flow with AI-Powered SolutionsAI-Enabled Electronic Circuit and System Design10.1007/978-3-031-71436-8_7(225-256)Online publication date: 17-Oct-2024
  • (2023)Fast and Inexpensive High-Level Synthesis Design Space Exploration: Machine Learning to the RescueIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2023.325834142:11(3939-3950)Online publication date: Nov-2023
  • (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
  • Show More Cited By

Index Terms

  1. Design space exploration using time and resource duality with the ant colony optimization

      Recommendations

      Comments

      Information & Contributors

      Information

      Published In

      cover image ACM Conferences
      DAC '06: Proceedings of the 43rd annual Design Automation Conference
      July 2006
      1166 pages
      ISBN:1595933816
      DOI:10.1145/1146909
      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: 24 July 2006

      Permissions

      Request permissions for this article.

      Check for updates

      Author Tags

      1. MAX-MIN ant system
      2. ant colony optimization
      3. design space exploration
      4. instruction scheduling algorithms

      Qualifiers

      • Article

      Conference

      DAC06
      Sponsor:
      DAC06: The 43rd Annual Design Automation Conference 2006
      July 24 - 28, 2006
      CA, San Francisco, USA

      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)5
      • Downloads (Last 6 weeks)0
      Reflects downloads up to 27 Jan 2025

      Other Metrics

      Citations

      Cited By

      View all
      • (2024)Enhancing FPGA CAD Flow with AI-Powered SolutionsAI-Enabled Electronic Circuit and System Design10.1007/978-3-031-71436-8_7(225-256)Online publication date: 17-Oct-2024
      • (2023)Fast and Inexpensive High-Level Synthesis Design Space Exploration: Machine Learning to the RescueIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2023.325834142:11(3939-3950)Online publication date: Nov-2023
      • (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
      • (2020)Development of Multiobjective High-Level Synthesis for FPGAsScientific Programming10.1155/2020/70950482020Online publication date: 1-Jan-2020
      • (2020)High-Level Synthesis Design Space Exploration: Past, Present, and FutureIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2019.294357039:10(2628-2639)Online publication date: Oct-2020
      • (2019)A Memetic Algorithm-Based Design Space Exploration for Datapath Resource Allocation During High-Level SynthesisJournal of Circuits, Systems and Computers10.1142/S021812662050001229:01(2050001)Online publication date: 15-Mar-2019
      • (2019)A novel method for high-level synthesis of datapaths in digital filters using a moth-flame optimization algorithmEvolutionary Intelligence10.1007/s12065-019-00302-wOnline publication date: 22-Oct-2019
      • (2011)Processor Accelerator Customization through Data Flow Graph ExplorationIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences10.1587/transfun.E94.A.1540E94-A:7(1540-1552)Online publication date: 2011
      • (2010)Behavioral level dual-Vth design for reduced leakage power with thermal awarenessProceedings of the Conference on Design, Automation and Test in Europe10.5555/1870926.1871229(1261-1266)Online publication date: 8-Mar-2010
      • (2010)Behavioral level dual-vth design for reduced leakage power with thermal awareness2010 Design, Automation & Test in Europe Conference & Exhibition (DATE 2010)10.1109/DATE.2010.5457000(1261-1266)Online publication date: Mar-2010
      • 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

      Figures

      Tables

      Media

      Share

      Share

      Share this Publication link

      Share on social media