DocumentCode :
568702
Title :
Parallel heuristic graph matching algorithm for task assignment problem in distributed computing systems
Author :
Mohan, R. ; Gopalan, N.P. ; Prasanth, S. H. Dinesh ; Sanyam, Siddhant ; Varma, Saagar R.
Author_Institution :
Nat. Inst. of Technol., Tiruchirapalli, India
Volume :
2
fYear :
2012
fDate :
12-14 June 2012
Firstpage :
575
Lastpage :
579
Abstract :
Task assignment is one of the most challenging problems in distributed computing environment. An optimal task assignment guarantees minimum turnaround time for a given architecture. Several approaches of optimal task assignment have been proposed by various researchers ranging from graph partitioning based tools to heuristic graph matching. Using heuristic graph matching, it is often impossible to get optimal task assignment for practical test cases within an acceptable time limit. Some researchers have tried to solve this problem by following a “divide and conquer” strategy and have successfully applied it to find optimal task assignment on the processors constituting a node of a cluster of multi-processors giving acceptable assignments within acceptable time limits. In this paper it is attempted to parallelize the basic heuristic graph-matching algorithm of task assignment put forward by previous research. Processors to which the task assignment has been carried over are made heterogeneous by assigning different costs for each tasks to execute on different processors when assigned to them. Results show that near optimal assignments (>;90%) are obtained much efficiently than the sequential task assignment in all the cases.
Keywords :
distributed processing; graph theory; parallel processing; pattern matching; distributed computing systems; divide and conquer strategy; optimal task assignment; parallel heuristic graph matching algorithm; task assignment problem; Indexes; Silicon; Parallel task assignment; heterogeneous processors; heuristic graph matching; load balancing;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Computer & Information Science (ICCIS), 2012 International Conference on
Conference_Location :
Kuala Lumpeu
Print_ISBN :
978-1-4673-1937-9
Type :
conf
DOI :
10.1109/ICCISci.2012.6297096
Filename :
6297096
Link To Document :
بازگشت