Dynamic mapping in a heterogeneous environment with tasks having priorities and multiple deadlines

Jong Kook Kim; Sameer Shivle; Howard Jay Siegel; Anthony A. Maciejewski; Tracy D. Braun; Myron Schneider; Sonja Tideman; Ramakrishna Chitta; Raheleh B. Dilmaghani; Rohit Joshi; Aditya Kaul; Ashish Sharma; Siddhartha Sripada; Praveen Vangari; Siva Sankar Yellampalli

doi:10.1109/IPDPS.2003.1213201

Dynamic mapping in a heterogeneous environment with tasks having priorities and multiple deadlines

Jong Kook Kim, Sameer Shivle, Howard Jay Siegel, Anthony A. Maciejewski, Tracy D. Braun, Myron Schneider, Sonja Tideman, Ramakrishna Chitta, Raheleh B. Dilmaghani, Rohit Joshi, Aditya Kaul, Ashish Sharma, Siddhartha Sripada, Praveen Vangari, Siva Sankar Yellampalli

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

34 Citations (Scopus)

Abstract

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.

Original language	English
Title of host publication	Proceedings - International Parallel and Distributed Processing Symposium, IPDPS 2003
Publisher	Institute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)	0769519261, 9780769519265
DOIs	https://doi.org/10.1109/IPDPS.2003.1213201
Publication status	Published - 2003
Externally published	Yes
Event	International Parallel and Distributed Processing Symposium, IPDPS 2003 - Nice, France Duration: 2003 Apr 22 → 2003 Apr 26

Publication series

Name	Proceedings - International Parallel and Distributed Processing Symposium, IPDPS 2003

Other

Other	International Parallel and Distributed Processing Symposium, IPDPS 2003
Country/Territory	France
City	Nice
Period	03/4/22 → 03/4/26

Bibliographical note

Publisher Copyright:
© 2003 IEEE.

ASJC Scopus subject areas

Computational Theory and Mathematics
Theoretical Computer Science
Software

Access to Document

10.1109/IPDPS.2003.1213201

Cite this

Kim, J. K., Shivle, S., Siegel, H. J., Maciejewski, A. A., Braun, T. D., Schneider, M., Tideman, S., Chitta, R., Dilmaghani, R. B., Joshi, R., Kaul, A., Sharma, A., Sripada, S., Vangari, P., & Yellampalli, S. S. (2003). Dynamic mapping in a heterogeneous environment with tasks having priorities and multiple deadlines. In Proceedings - International Parallel and Distributed Processing Symposium, IPDPS 2003 Article 1213201 (Proceedings - International Parallel and Distributed Processing Symposium, IPDPS 2003). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/IPDPS.2003.1213201

Dynamic mapping in a heterogeneous environment with tasks having priorities and multiple deadlines. / Kim, Jong Kook; Shivle, Sameer; Siegel, Howard Jay et al.
Proceedings - International Parallel and Distributed Processing Symposium, IPDPS 2003. Institute of Electrical and Electronics Engineers Inc., 2003. 1213201 (Proceedings - International Parallel and Distributed Processing Symposium, IPDPS 2003).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Kim, JK, Shivle, S, Siegel, HJ, Maciejewski, AA, Braun, TD, Schneider, M, Tideman, S, Chitta, R, Dilmaghani, RB, Joshi, R, Kaul, A, Sharma, A, Sripada, S, Vangari, P & Yellampalli, SS 2003, Dynamic mapping in a heterogeneous environment with tasks having priorities and multiple deadlines. in Proceedings - International Parallel and Distributed Processing Symposium, IPDPS 2003., 1213201, Proceedings - International Parallel and Distributed Processing Symposium, IPDPS 2003, Institute of Electrical and Electronics Engineers Inc., International Parallel and Distributed Processing Symposium, IPDPS 2003, Nice, France, 03/4/22. https://doi.org/10.1109/IPDPS.2003.1213201

Kim JK, Shivle S, Siegel HJ, Maciejewski AA, Braun TD, Schneider M et al. Dynamic mapping in a heterogeneous environment with tasks having priorities and multiple deadlines. In Proceedings - International Parallel and Distributed Processing Symposium, IPDPS 2003. Institute of Electrical and Electronics Engineers Inc. 2003. 1213201. (Proceedings - International Parallel and Distributed Processing Symposium, IPDPS 2003). doi: 10.1109/IPDPS.2003.1213201

Kim, Jong Kook ; Shivle, Sameer ; Siegel, Howard Jay et al. / Dynamic mapping in a heterogeneous environment with tasks having priorities and multiple deadlines. Proceedings - International Parallel and Distributed Processing Symposium, IPDPS 2003. Institute of Electrical and Electronics Engineers Inc., 2003. (Proceedings - International Parallel and Distributed Processing Symposium, IPDPS 2003).

@inproceedings{54003dfaa595443c80a4d9cd8b20d63f,

title = "Dynamic mapping in a heterogeneous environment with tasks having priorities and multiple deadlines",

abstract = "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.",

author = "Kim, {Jong Kook} and Sameer Shivle and Siegel, {Howard Jay} and Maciejewski, {Anthony A.} and Braun, {Tracy D.} and Myron Schneider and Sonja Tideman and Ramakrishna Chitta and Dilmaghani, {Raheleh B.} and Rohit Joshi and Aditya Kaul and Ashish Sharma and Siddhartha Sripada and Praveen Vangari and Yellampalli, {Siva Sankar}",

note = "Publisher Copyright: {\textcopyright} 2003 IEEE.; International Parallel and Distributed Processing Symposium, IPDPS 2003 ; Conference date: 22-04-2003 Through 26-04-2003",

year = "2003",

doi = "10.1109/IPDPS.2003.1213201",

language = "English",

series = "Proceedings - International Parallel and Distributed Processing Symposium, IPDPS 2003",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

booktitle = "Proceedings - International Parallel and Distributed Processing Symposium, IPDPS 2003",

}

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

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 -

Dynamic mapping in a heterogeneous environment with tasks having priorities and multiple deadlines

Abstract

Publication series

Other

Bibliographical note

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this