TY - GEN
T1 - Dynamic mapping in a heterogeneous environment with tasks having priorities and multiple deadlines
AU - Kim, Jong Kook
AU - Shivle, Sameer
AU - Siegel, Howard Jay
AU - Maciejewski, Anthony A.
AU - Braun, Tracy D.
AU - Schneider, Myron
AU - Tideman, Sonja
AU - Chitta, Ramakrishna
AU - Dilmaghani, Raheleh B.
AU - Joshi, Rohit
AU - Kaul, Aditya
AU - Sharma, Ashish
AU - Sripada, Siddhartha
AU - Vangari, Praveen
AU - Yellampalli, Siva Sankar
N1 - Publisher Copyright:
© 2003 IEEE.
PY - 2003
Y1 - 2003
N2 - In a distributed heterogeneous computing system, the resources have different capabilities and tasks have different requirements. To maximize the performance of the system, it is essential to assign resources to tasks (match) and order the execution of tasks on each resource (schedule in a manner that exploits the heterogeneity of the resources and tasks. The mapping (defined as matching and scheduling) of tasks onto machines with varied computational capabilities has been shown, in general, to be an NP-complete problem. Therefore, heuristic techniques to find a near-optimal solution to this mapping problem are required. Dynamic mapping is performed when the arrival of tasks is not known a priori. In the heterogeneous environment considered in this study, tasks arrive randomly, tasks are independent (i.e., no communication among tasks), and tasks have priorities and multiple deadlines. This research proposes, evaluates, and compares eight dynamic heuristics. The performance of the best heuristics is 83% of an upper bound.
AB - In a distributed heterogeneous computing system, the resources have different capabilities and tasks have different requirements. To maximize the performance of the system, it is essential to assign resources to tasks (match) and order the execution of tasks on each resource (schedule in a manner that exploits the heterogeneity of the resources and tasks. The mapping (defined as matching and scheduling) of tasks onto machines with varied computational capabilities has been shown, in general, to be an NP-complete problem. Therefore, heuristic techniques to find a near-optimal solution to this mapping problem are required. Dynamic mapping is performed when the arrival of tasks is not known a priori. In the heterogeneous environment considered in this study, tasks arrive randomly, tasks are independent (i.e., no communication among tasks), and tasks have priorities and multiple deadlines. This research proposes, evaluates, and compares eight dynamic heuristics. The performance of the best heuristics is 83% of an upper bound.
UR - http://www.scopus.com/inward/record.url?scp=35348897417&partnerID=8YFLogxK
U2 - 10.1109/IPDPS.2003.1213201
DO - 10.1109/IPDPS.2003.1213201
M3 - Conference contribution
AN - SCOPUS:35348897417
T3 - Proceedings - International Parallel and Distributed Processing Symposium, IPDPS 2003
BT - Proceedings - International Parallel and Distributed Processing Symposium, IPDPS 2003
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - International Parallel and Distributed Processing Symposium, IPDPS 2003
Y2 - 22 April 2003 through 26 April 2003
ER -