skip to main content
10.1145/1057661.1057674acmconferencesArticle/Chapter ViewAbstractPublication PagesglsvlsiConference Proceedingsconference-collections
Article

Instruction scheduling using MAX-MIN ant system optimization

Published: 17 April 2005 Publication History

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]
T. L. Adam, K. M. Chandy, and J. R. Dickson. A comparison of list schedules for parallel processing systems. Commun. ACM, 17(12):685--690, 1974.
[3]
A. Aletà, J. M. Codina, J. Sánchez, and A. González. Graph-Partitioning based Instruction Scheduling for Clustered Processors. In Proceedings of the 34th Annual ACM/IEEE International Symposium on Microarchitecture, 2001.
[4]
A. Auyeung, I. Gondra, and H. K. Dai. Advances in Soft Computing: Intelligent Systems Design and Applications, chapter Integrating random ordering into multi-heuristic list scheduling genetic algorithm. Springer-Verlag, 2003.
[5]
D. Bernstein, M. Rodeh, and I. Gertner. On the Complexity of Scheduling Problems for Parallel/Pipelined Machines. IEEE Transactions on Computers, 38(9):1308--13, September 1989.
[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]
L. M. Gambardella, E. D. Taillard, and G. Agazzi. New Ideas in Optimization, chapter A multiple ant colony system for vehicle routing problems with time windows. McGraw Hill, 1999.
[8]
M. Grajcar. Genetic List Scheduling Algorithm for Scheduling and Allocation on a Loosely Coupled Heterogeneous Multiprocessor System. In Proceedings of the 36th ACM/IEEE Conference on Design Automation Conference, 1999.
[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. O. Memik, E. Bozorgzadeh, R. Kastner, and M. Sarrafzadeh. A super-scheduler for embedded reconfigurable systems. In IEEE/ACM International Conference on Computer-Aided Design, 2001.
[11]
G. D. Micheli. Synthesis and Optimization of Digital Circuits. McGraw-Hill, 1994.
[12]
M. Narasimhan and J. Ramanujam. A fast approach to computing exact solutions to the resource-constrained scheduling problem. ACM Trans. Des. Autom. Electron. Syst., 6(4):490--500, 2001.
[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 and J. P. Knight. Force-directed scheduling in automatic data path synthesis. In 24th ACM/IEEE Conference Proceedings on Design Automation Conference, 1987.
[15]
G. Pruesse and F. Ruskey. Generating linear extensions fast. SIAM J. Comput., 23(2):373--386, 1994.
[16]
T. Stützle and H. H. Hoos. MAX-MIN Ant System. Future Generation Comput. Systems, 16(9):889--914, September 2000.
[17]
H. Topcuoglu, S. Hariri, and M.-Y. Wu. Performance-effective and low-complexity task scheduling for heterogeneous computing. IEEE Transaction on Parallel and Distributed Systems, 13(3):260--274, March 2002.
[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.

Cited By

View all
  • (2022) GCD 2 : A Globally Optimizing Compiler for Mapping DNNs to Mobile DSPs 2022 55th IEEE/ACM International Symposium on Microarchitecture (MICRO)10.1109/MICRO56248.2022.00044(512-529)Online publication date: Oct-2022
  • (2017)A Hybrid Algorithm Based on Particle Swarm Optimization and Ant Colony Optimization AlgorithmSmart Computing and Communication10.1007/978-3-319-52015-5_3(22-31)Online publication date: 13-Jan-2017
  • (2012)Scheduling in high level synthesis using discrete evolutionary programming2012 Third International Conference on Computing, Communication and Networking Technologies (ICCCNT'12)10.1109/ICCCNT.2012.6396007(1-7)Online publication date: Jul-2012
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
GLSVLSI '05: Proceedings of the 15th ACM Great Lakes symposium on VLSI
April 2005
518 pages
ISBN:1595930574
DOI:10.1145/1057661
  • General Chair:
  • John Lach,
  • Program Chairs:
  • Gang Qu,
  • Yehea Ismail
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: 17 April 2005

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. MAX-MIN ant system
  2. force-directed scheduling
  3. instruction scheduling
  4. list scheduling

Qualifiers

  • Article

Conference

GLSVLSI05
Sponsor:
GLSVLSI05: Great Lakes Symposium on VLSI 2005
April 17 - 19, 2005
Illinois, Chicago, USA

Acceptance Rates

Overall Acceptance Rate 312 of 1,156 submissions, 27%

Upcoming Conference

GLSVLSI '25
Great Lakes Symposium on VLSI 2025
June 30 - July 2, 2025
New Orleans , LA , 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
  • (2022) GCD 2 : A Globally Optimizing Compiler for Mapping DNNs to Mobile DSPs 2022 55th IEEE/ACM International Symposium on Microarchitecture (MICRO)10.1109/MICRO56248.2022.00044(512-529)Online publication date: Oct-2022
  • (2017)A Hybrid Algorithm Based on Particle Swarm Optimization and Ant Colony Optimization AlgorithmSmart Computing and Communication10.1007/978-3-319-52015-5_3(22-31)Online publication date: 13-Jan-2017
  • (2012)Scheduling in high level synthesis using discrete evolutionary programming2012 Third International Conference on Computing, Communication and Networking Technologies (ICCCNT'12)10.1109/ICCCNT.2012.6396007(1-7)Online publication date: Jul-2012
  • (2008)Particle swarm optimization for constrained instruction schedulingVLSI Design10.1155/2008/9306102008:4(1-7)Online publication date: 1-Feb-2008
  • (2008)Mobility prediction based on an ant systemComputer Communications10.1016/j.comcom.2008.04.00931:14(3090-3097)Online publication date: 1-Sep-2008
  • (2007)Exploring time/resource trade-offs by solving dual scheduling problems with the ant colony optimizationACM Transactions on Design Automation of Electronic Systems10.1145/1278349.127835912:4(46-es)Online publication date: 1-Sep-2007
  • (2006)Design space exploration using time and resource duality with the ant colony optimizationProceedings of the 43rd annual Design Automation Conference10.1145/1146909.1147028(451-454)Online publication date: 24-Jul-2006
  • (2006)Design space exploration using time and resource duality with the ant colony optimization2006 43rd ACM/IEEE Design Automation Conference10.1109/DAC.2006.229234(451-454)Online publication date: 2006
  • (2005)Overview of metaheuristics methods in compilationProceedings of the 4th Mexican international conference on Advances in Artificial Intelligence10.1007/11579427_49(483-493)Online publication date: 14-Nov-2005

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