Exploring time/resource trade-offs by solving dual scheduling problems 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 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: 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: Robert P. Dick , Niraj K. Jha, MOGAC: a multiobjective genetic algorithm for the co-synthesis of hardware-software embedded systems, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.522-529, November 09-13, 1997, San Jose, California, United States
• 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: 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
• 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: M. J. M. Heijligers , L. J. M. Cluitmans , J. A. G. Jess, High-level synthesis scheduling and allocation using genetic algorithms, Proceedings of the 1995 conference on Asia Pacific design automation (CD-ROM), p.11-es, August 29-September 01, 1995, Makuhari, Massa, Chiba, Japan [doi>10.1145/224818.224842]
• 10: 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
• 11: 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]
• 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: 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]
• 15: 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]
• 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: Thomas Stützle , Holger H. Hoos, MAX-MIN Ant system, Future Generation Computer Systems, v.16 n.9, p.889-914, June 2000
• 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: 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]
• 22: Kent Wilken , Jack Liu , Mark Heffernan, Optimal instruction scheduling using integer programming, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.121-133, June 18-21, 2000, Vancouver, British Columbia, Canada

INDEX TERMS

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

General Terms:
Algorithms, Design, Theory

Keywords:
Design space exploration, ant colony optimization, instruction scheduling, max-min ant system