Instruction scheduling using MAX-MIN ant system optimization

ABSTRACT

Instruction scheduling is a fundamental step for mapping an application to a computational device. It takes a behavioral application specification and produces a schedule for the instructions onto a collection of processing units. The objective is to minimize the completion time of the given application while effectively utilizing the computational resources. The instruction scheduling problem is NP-hard, thus effective heuristic methods are necessary to provide a qualitative scheduling solution. In this paper, we present a novel instruction scheduling algorithm using MAX-MIN Ant System Optimization approach. The algorithm utilizes a unique hybrid approach by combining the ant system meta-heuristic with list scheduling, where the local and global heuristics are dynamically adjusted to the input application in an iterative manner. Compared with force-directed scheduling and a number of different list scheduling heuristics, our algorithm generates better results over all the tested benchmarks with better stability. Furthermore, by solving the test samples optimally using ILP formulation, we show that our algorithm consistently achieves a near optimal solution.

REFERENCES

• 1: National Technology Roadmap for Semiconductors. 2003.
• 2: Thomas L. Adam , K. M. Chandy , J. R. Dickson, A comparison of list schedules for parallel processing systems, Communications of the ACM, v.17 n.12, p.685-690, Dec 1974 [doi>10.1145/361604.361619]
• 3: Alex Aletà , Josep M. Codina , Jesús Sánchez , Antonio González, Graph-partitioning based instruction scheduling for clustered processors, Proceedings of the 34th annual ACM/IEEE international symposium on Microarchitecture, December 01-05, 2001, Austin, Texas
• 4: Andy Auyeung , Iker Gondra , H. K. Dai, Multi-heuristic list scheduling genetic algorithm for task scheduling, Proceedings of the 2003 ACM symposium on Applied computing, March 09-12, 2003, Melbourne, Florida [doi>10.1145/952532.952673]
• 5: David Bernstein , Michael Rodeh , Izidor Gertner, On the Complexity of Scheduling Problems for Parallel/Pipelined Machines, IEEE Transactions on Computers, v.38 n.9, p.1308-1313, September 1989 [doi>10.1109/12.29469]
• 6: 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.
• 7: Luca Maria Gambardella , Éric Taillard , Giovanni Agazzi, MACS-VRPTW: a multiple ant colony system for vehicle routing problems with time windows, New ideas in optimization, McGraw-Hill Ltd., UK, Maidenhead, UK, 1999
• 8: Martin Grajcar, Genetic list scheduling algorithm for scheduling and allocation on a loosely coupled heterogeneous multiprocessor system, Proceedings of the 36th ACM/IEEE conference on Design automation, p.280-285, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309931]
• 9: R. Kolisch and S. Hartmann. Project Scheduling: Recent models, algorithms and applications, chapter Heuristic Algorithms for Solving the Resource-Constrained Project Scheduling problem: Classification and Computational Analysis. Kluwer Academic Publishers, 1999.
• 10: S. Ogrenci Memik , E. Bozorgzadeh , R. Kastner , M. Sarrafzadeh, A super-scheduler for embedded reconfigurable systems, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
• 11: Giovanni De Micheli, Synthesis and Optimization of Digital Circuits, McGraw-Hill Higher Education, 1994
• 12: M. Narasimhan , J. Ramanujam, A fast approach to computing exact solutions to the resource-constrained scheduling problem, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.6 n.4, p.490-500, October 2001 [doi>10.1145/502175.502178]
• 13: R. S. Parpinelli, H. S. Lopes, and A. A. Freitas. Data mining with an ant colony optimization algorithm. IEEE Transaction on Evolutionary Computation, 6(4):321--332, August 2002.
• 14: 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]
• 15: Gara Pruesse , Frank Ruskey, Generating Linear Extensions Fast, SIAM Journal on Computing, v.23 n.2, p.373-386, April 1994 [doi>10.1137/S0097539791202647]
• 16: Thomas Stützle , Holger H. Hoos, MAX-MIN Ant system, Future Generation Computer Systems, v.16 n.9, p.889-914, June 2000
• 17: Haluk Topcuouglu , Salim Hariri , Min-you Wu, Performance-Effective and Low-Complexity Task Scheduling for Heterogeneous Computing, IEEE Transactions on Parallel and Distributed Systems, v.13 n.3, p.260-274, March 2002 [doi>10.1109/71.993206]
• 18: G. Wang, W. Gong, and R. Kastner. A New Approach for Task Level Computational Resource Bi-partitioning. 15th International Conference on Parallel and Distributed Computing and Systems, PDCS'2003, 1(1):439--444, November 2003.

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, force-directed scheduling, instruction scheduling, list scheduling