Dynamic mapping in a heterogeneous environment with tasks having priorities and multiple deadlines Kim, Jong-Kook ; Shivle, Sameer ; Siegel, Howard Jay ; Maciejewski, Anthony A. ; Bruan, Tracy D. ; Schneider, Myron ; Tideman, Sonja ; Ramakrishna, Chitta ; Dilmaghani, Raheleh B. ; Joshi, Rohit S. ; Kaul, Aditya ; Sharma, Ashish ; Sripada, Siddhartha ; Vangari, Praveen ; Yallampalli, Siva Sankar "This research was supported in part by the Colorado State University George T. Abell Endowment." 15 p. 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. Colorado State University. Libraries 2003 text ; image application/pdf ECEaam00095.pdf FACFECEN100095ARTI eng c2003 IEEE
Dynamic mapping in a heterogeneous environment with tasks having priorities and multiple deadlines
Kim, Jong-Kook ; Shivle, Sameer ; Siegel, Howard Jay ; Maciejewski, Anthony A. ; Bruan, Tracy D. ; Schneider, Myron ; Tideman, Sonja ; Ramakrishna, Chitta ; Dilmaghani, Raheleh B. ; Joshi, Rohit S. ; Kaul, Aditya ; Sharma, Ashish ; Sripada, Siddhartha ; Vangari, Praveen ; Yallampalli, Siva Sankar
"This research was supported in part by the Colorado State University George T. Abell Endowment."
15 p.
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.
Colorado State University. Libraries
2003
text ; image
application/pdf
ECEaam00095.pdf
FACFECEN100095ARTI
eng
c2003 IEEE