skip to main content
article

Exploring time/resource trade-offs by solving dual scheduling problems with the ant colony optimization

Published: 01 September 2007 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 of time- and resource-constrained scheduling problems. Our exploration automatically constructs a time/area tradeoff curve in a fast, effective manner. It is a general approach and can be combined with any high-quality scheduling algorithm. In our work, we use the max-min ant colony optimization technique to solve both time- and resource-constrained scheduling problems. Our algorithm provides significant solution-quality savings (average 17.3% reduction of resource counts) with similar runtime compared to using force-directed scheduling exhaustively at every time step. It also scales well across a comprehensive benchmark suite constructed with classic and real-life samples.

References

[1]
Aigner, G., Diwan, A., Heine, D. L., Moore, M. S. L. D. L., Murphy, B. R., and Sapuntzakis, C. 2000. The Basic SUIF Programming Guide. Computer Systems Laboratory, Stanford University Stanford, CA.
[2]
Chaudhuri, S., Blythe, S. A., and Walker, R. A. 1997. 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.
[3]
Corne, D., Dorigo, M., and Glover, F., eds. 1999. New Ideas in Optimization. McGraw Hill, London.
[4]
Dick, R. P. and Jha, N. K. 1997. MOGAC: A multiobjective genetic algorithm for the co-synthesis of hardware-software embedded systems. In Proceedings of the IEEE/ACM Conference on Computer Aided Design, 522--529.
[5]
Dorigo, M., Maniezzo, V., and Colorni, A. 1996. Ant system: Optimization by a colony of cooperating agents. IEEE Trans. Syst. Man Cybern. Part-B 26, 1 (Feb.), 29--41.
[6]
Dutta, R., Roy, J., and Vemuri, R. 1992. Distributed design-space exploration for high-level synthesis systems. In Proceedings of the Design and Automation Conference (DAC). IEEE Computer Society Press, Los Alamitos, CA, 644--650.
[7]
ExpressDFG. 2006. ExpressDFG benchmark website. http://express.ece.ucsb.edu/benchmark/.
[8]
Gutjahr, W. J. 2002. ACO algorithms with guaranteed convergence to the optimal solution. Inf. Process. Lett. 82, 3, 145--153.
[9]
Heijligers, M. J. M., Cluitmans, L. J. M., and Jess, J. A. G. 1995. High-Level synthesis scheduling and allocation using genetic algorithms. In Proceedings of the EDA Technofair Design Automation Conference/Asia and South Pacific Design Automation Conference (Makuhari, Massa, Chiba, Japan). Article 11.
[10]
Lee, C., Potkonjak, M., and Mangione-Smith, W. H. 1997. MediaBench: A tool for evaluating and synthesizing multimedia and communicatons systems. In Proceedings of the 30th Annual ACM/IEEE International Symposium on Microarchitecture.
[11]
Lin, Y.-L. 1997. Recent developments in high-level synthesis. ACM Trans. Des. Autom. Electron. Syst. 2, 1, 2--21.
[12]
Madsen, J., Grode, J., Knudsen, P. V., Petersen, M. E., and Haxthausen, A. 1997. LYCOS: The Lyngby co-synthesis system. Des. Autom. Embedded Syst. 2, 2 (Mar.), 125--63.
[13]
McFarland, M., Parker, A. C., and Camposano, R. 1990. The high-level synthesis of digital systems. In Proc. IEEE. 78, 301--318.
[14]
Palesi, M. and Givargis, T. 2002. Multi-Objective design space exploration using geneticalgorithms. In Proceedings of the 10th International Symposium on Hardware/Software Codesign.
[15]
Paulin, P. G. and Knight, J. P. 1987. Force-Directed scheduling in automatic data path synthesis. In Proceedings of the 24th ACM/IEEE Conference on Design Automation Conference.
[16]
Smith, M. D. and Holloway, G. 2002. An Introduction to Machine SUIF and Its Portable Libraries for Analysis and Optimization. Division of Engineering and Applied Sciences, Harvard University.
[17]
Stützle, T. and Hoos, H. H. 2000. Max-Min ant system. Future Gen. Comput. Syst. 16, 9 (Sept.), 889--914.
[18]
Wang, G., Gong, W., DeRenzi, B., and Kastner, R. Ant colony optimizations for resource and timing constrained operation scheduling. IEEE Trans. Comput.-Aided Des (to appear).
[19]
Wang, G., Gong, W., and Kastner, R. 2003. A new approach for task level computational resourcebi-partitioning. In Proceedings of the 15th International Conference on Parallel and Distributed Computingand Systems 1, 1 (Nov.), 439--444.
[20]
Wang, G., Gong, W., and Kastner, R. 2004. System level partitioning for programmable platforms using the antcolony optimization. In Proceedings of the 13th International Workshop on Logic and Synthesis (IWLS).
[21]
Wang, G., Gong, W., and Kastner, R. 2005. Instruction scheduling using Max-Min ant optimization. In 15th ACM Great Lakes Symposium on VLSI (GLSVLSI).
[22]
Wilken, K., Liu, J., and Heffernan, M. 2000. Optimal instruction scheduling using integer programming. In Proceedings of the ACM SIGPLAN Conference on Programming Language design and Implementation.

Cited By

View all
  • (2020)Development of Multiobjective High-Level Synthesis for FPGAsScientific Programming10.1155/2020/70950482020Online publication date: 1-Jan-2020
  • (2015)SPIRIT: Spectral-Aware Pareto Iterative Refinement Optimization for Supervised High-Level SynthesisIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2014.236339234:1(155-159)Online publication date: Jan-2015
  • (2013)A meta-model assisted coprocessor synthesis framework for compiler/architecture parameters customizationProceedings of the Conference on Design, Automation and Test in Europe10.5555/2485288.2485450(659-664)Online publication date: 18-Mar-2013
  • Show More Cited By

Index Terms

  1. Exploring time/resource trade-offs by solving dual scheduling problems with the ant colony optimization

      Recommendations

      Comments

      Information & Contributors

      Information

      Published In

      cover image ACM Transactions on Design Automation of Electronic Systems
      ACM Transactions on Design Automation of Electronic Systems  Volume 12, Issue 4
      September 2007
      449 pages
      ISSN:1084-4309
      EISSN:1557-7309
      DOI:10.1145/1278349
      Issue’s Table of Contents

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Journal Family

      Publication History

      Published: 01 September 2007
      Published in TODAES Volume 12, Issue 4

      Permissions

      Request permissions for this article.

      Check for updates

      Author Tags

      1. Design space exploration
      2. ant colony optimization
      3. instruction scheduling
      4. max-min ant system

      Qualifiers

      • Article

      Contributors

      Other Metrics

      Bibliometrics & Citations

      Bibliometrics

      Article Metrics

      • Downloads (Last 12 months)4
      • Downloads (Last 6 weeks)0
      Reflects downloads up to 27 Jan 2025

      Other Metrics

      Citations

      Cited By

      View all
      • (2020)Development of Multiobjective High-Level Synthesis for FPGAsScientific Programming10.1155/2020/70950482020Online publication date: 1-Jan-2020
      • (2015)SPIRIT: Spectral-Aware Pareto Iterative Refinement Optimization for Supervised High-Level SynthesisIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2014.236339234:1(155-159)Online publication date: Jan-2015
      • (2013)A meta-model assisted coprocessor synthesis framework for compiler/architecture parameters customizationProceedings of the Conference on Design, Automation and Test in Europe10.5555/2485288.2485450(659-664)Online publication date: 18-Mar-2013
      • (2013)Compiler-in-the-loop exploration during datapath synthesis for higher quality delay-area trade-offsACM Transactions on Design Automation of Electronic Systems10.1145/2390191.239020218:1(1-35)Online publication date: 16-Jan-2013
      • (2011)An iterative approach for hybria pipeline scheduling under throughput and resource constraints2011 IEEE International Conference on Computer Science and Automation Engineering10.1109/CSAE.2011.5952764(668-672)Online publication date: Jun-2011
      • (2011)A High Level Synthesis Exploration Framework with Iterative Design Space PartitioningVLSI 2010 Annual Symposium10.1007/978-94-007-1488-5_7(117-131)Online publication date: 8-Sep-2011
      • (2010)Efficient High Level Synthesis Exploration Methodology Combining Exhaustive and Gradient-Based Pruned SearchingProceedings of the 2010 IEEE Annual Symposium on VLSI10.1109/ISVLSI.2010.56(104-109)Online publication date: 5-Jul-2010
      • (2010)Designing efficient DSP datapaths through compiler-in-the-loop exploration methodologyProceedings of 2010 IEEE International Symposium on Circuits and Systems10.1109/ISCAS.2010.5537090(2598-2601)Online publication date: May-2010
      • (2010)Hardware synthesisArithmetic Optimization Techniques for Hardware and Software Design10.1017/CBO9780511712180.005(35-67)Online publication date: 3-May-2010
      • (2008)ETAHMProceedings of the 45th annual Design Automation Conference10.1145/1391469.1391667(776-779)Online publication date: 8-Jun-2008

      View Options

      Login options

      Full Access

      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