Title :
Scalable high quality hierarchical scheduling
Author :
Wei Tang ; Brewer, F.
Author_Institution :
Dept. of Electr. & Computering Eng., Univ. of California, Santa Barbara, Santa Barbara, CA, USA
fDate :
May 31 2013-June 1 2013
Abstract :
List scheduling is well known for its implementation simplicity and O(N2) scalability, but not for result quality. The Ant-Colony scheduling algorithm, imitating the cooperative behaviors of ants, does generate high quality results, but like any stochastic search, has potentially long run times to assure high result quality. This paper presents a hierarchical scheduling algorithm using the ideas of ant colony, whose run time complexity is at the same scale as ordinary list scheduling, while generating results as good as the classic ant-colony scheduling algorithm. In practice, this implies a very substantial run-time improvement, enabling scheduling exploration of much larger problems while avoiding the pitfalls of over-constraint and lower quality results that hierarchical solutions are generally known for.
Keywords :
ant colony optimisation; microprocessor chips; processor scheduling; ant colony scheduling algorithm; list scheduling; run time complexity; scalable high quality hierarchical scheduling; scheduling exploration; Algorithm design and analysis; Benchmark testing; Clustering algorithms; Complexity theory; Schedules; Scheduling; Scheduling algorithms;
Conference_Titel :
Electronic System Level Synthesis Conference (ESLsyn), 2013
Conference_Location :
Austin, TX
Print_ISBN :
978-1-4673-6414-0