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

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: Samit Chaudhuri , Stephen A. Blythe , Robert A. Walker, A solution methodology for exact design space exploration in a three-dimensional design space, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.5 n.1, p.69-81, March 1997 [doi>10.1109/92.555988]
• 3: David Corne , Marco Dorigo , Fred Glover , Dipankar Dasgupta , Pablo Moscato , Riccardo Poli , Kenneth V. Price, New ideas in optimization, McGraw-Hill Ltd., UK, Maidenhead, 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 , R. Vemuri, Distributed design-space exploration for high-level synthesis systems, Proceedings of the 29th ACM/IEEE conference on Design automation, p.644-650, June 08-12, 1992, Anaheim, California, United States
• 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: Chunho Lee , Miodrag Potkonjak , William H. Mangione-Smith, MediaBench: a tool for evaluating and synthesizing multimedia and communicatons systems, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.330-335, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 8: Youn-Long Lin, Recent developments in high-level synthesis, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.2 n.1, p.2-21, Jan. 1997 [doi>10.1145/250243.250245]
• 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: Maurizio Palesi , Tony Givargis, Multi-objective design space exploration using genetic algorithms, Proceedings of the tenth international symposium on Hardware/software codesign, May 06-08, 2002, Estes Park, Colorado [doi>10.1145/774789.774804]
• 11: P. G. Paulin , J. P. Knight, Force-directed scheduling in automatic data path synthesis, Proceedings of the 24th ACM/IEEE conference on Design automation, p.195-202, June 28-July 01, 1987, Miami Beach, Florida, United States [doi>10.1145/37888.37918]
• 12: Thomas Stützle , Holger H. Hoos, MAX-MIN Ant system, Future Generation Computer Systems, v.16 n.9, p.889-914, June 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: Gang Wang , Wenrui Gong , Ryan Kastner, Instruction scheduling using MAX-MIN ant system optimization, Proceedings of the 15th ACM Great Lakes symposium on VLSI, April 17-19, 2005, Chicago, Illinois, USA [doi>10.1145/1057661.1057674]

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

General Terms:
Algorithms, Design, Theory

Keywords:
MAX-MIN ant system, ant colony optimization, design space exploration, instruction scheduling algorithms