DocumentCode :
1854245
Title :
Scheduling Algorithm Based on Force Directed Clustering
Author :
Palmer, Alistair ; Sinnen, Oliver
Author_Institution :
Dept. of Electr. & Comput. Eng., Univ. of Auckland, Auckland
fYear :
2008
fDate :
1-4 Dec. 2008
Firstpage :
311
Lastpage :
318
Abstract :
This paper describes a new task scheduling algorithm based on clustering. In this new approach, clustering of the tasks is achieved by applying a force model to the task graph. From an initial configuration of the task graph, forces act upon the nodes to manoeuvre them into a low energy or equilibrium state. Clusters are created from the equilibrium state and scheduled for an unlimited number of processors. This algorithm is compared in an extensive experimental evaluation to three other clustering algorithms namely, linear, single edge and dominant sequence clustering. By keeping the mapping and scheduling phases of the algorithms identical, we compare only the difference in clustering between all algorithms. Results show that force directed clustering is very promising, especially for a limited number of processors.
Keywords :
graph theory; graphs; pattern clustering; scheduling; dominant sequence clustering; equilibrium state; force directed clustering; force model; task graph; task scheduling algorithm; Application software; Clustering algorithms; Cost function; Distributed computing; Energy states; Heuristic algorithms; Processor scheduling; Scheduling algorithm; Springs; Visualization;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Parallel and Distributed Computing, Applications and Technologies, 2008. PDCAT 2008. Ninth International Conference on
Conference_Location :
Otago
Print_ISBN :
978-0-7695-3443-5
Type :
conf
DOI :
10.1109/PDCAT.2008.89
Filename :
4710996
Link To Document :
بازگشت