Preemptive resource management for dynamically arriving tasks in an oversubscribed heterogeneous computing system

Dylan Machovec; Sudeep Pasricha; Anthony A. Maciejewski; Howard Jay Siegel; Gregory A. Koenig; Michael Wright; Marcia Hilton; Rajendra Rambharos; Thomas Naughton; Neena Imam

doi:10.1109/IPDPSW.2017.158

Preemptive resource management for dynamically arriving tasks in an oversubscribed heterogeneous computing system

Dylan Machovec, Sudeep Pasricha, Anthony A. Maciejewski, Howard Jay Siegel, Gregory A. Koenig, Michael Wright, Marcia Hilton, Rajendra Rambharos, Thomas Naughton, Neena Imam

Programming Systems

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

1 Scopus citations

Abstract

We design resource management heuristics that assign serial tasks to the nodes of a heterogeneous high performance computing (HPC) system. The value of completing these tasks is modeled using monotonically decreasing utility functions that represent the time-varying importance of the task. The value of completing a task is equal to its utility function at the time of its completion. The overall performance of this system is measured using the total utility earned by all tasks during some interval of time. To maximize the performance of such a system where the preemption of tasks is possible, we have designed, analyzed, and compared a set of resource allocation heuristic techniques. We combine two utility-aware heuristics with three different preemption techniques to create six preemption-capable heuristics. We also consider the two utility-aware heuristics without preemption. We use simulation studies to evaluate this set of eight heuristics and compare them with an FCFS heuristic, which is often used in real systems, and random assignments. In general, our set of eight heuristics is able to significantly outperform the comparison heuristics, and the preemption-capable heuristics are able to significantly increase the utility earned compared to the heuristics that do not use preemption. We analyze the performance tradeoffs among the different preemption-capable heuristics under a variety of oversubscribed workload environments.

Original language	English
Title of host publication	Proceedings - 2017 IEEE 31st International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2017
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	54-64
Number of pages	11
ISBN (Electronic)	9781538634080
DOIs	https://doi.org/10.1109/IPDPSW.2017.158
State	Published - Jun 30 2017
Event	31st IEEE International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2017 - Orlando, United States Duration: May 29 2017 → Jun 2 2017

Publication series

Name	Proceedings - 2017 IEEE 31st International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2017

Conference

Conference	31st IEEE International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2017
Country/Territory	United States
City	Orlando
Period	05/29/17 → 06/2/17

Funding

This manuscript has been administered by UT-Battelle, LLC under Contract No. DE-AC05-00OR22725 with the U.S. Department of Energy. The United States Government retains and the publisher, by accepting the article for publication, acknowledges that the United States Government retains a nonexclusive, paid-up, irrevocable, world-wide license to publish or reproduce the published form of this manuscript, or allow others to do so, for United States Government purposes. The Department of Energy will provide public access to these results of federally sponsored research in accordance with the DOE Public Access Plan (http://energy.gov/downloads/doe-public-accessplan). This research used resources of the National Center for Computational Sciences at Oak Ridge National Laboratory (ORNL), supported by the Extreme Scale Systems Center at ORNL, which is supported by the Department of Defense (DoD); and by NSF Grant CCF-1302693. This work also utilized CSU\u2019s ISTeC Cray system, which is supported by the National Science Foundation (NSF) under grant number CNS-0923386.

Keywords

heterogeneous computing
preemption
resource management heuristics
scheduling
utility functions

Access to Document

10.1109/IPDPSW.2017.158

Cite this

Machovec, D., Pasricha, S., Maciejewski, A. A., Siegel, H. J., Koenig, G. A., Wright, M., Hilton, M., Rambharos, R., Naughton, T., & Imam, N. (2017). Preemptive resource management for dynamically arriving tasks in an oversubscribed heterogeneous computing system. In Proceedings - 2017 IEEE 31st International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2017 (pp. 54-64). Article 7965025 (Proceedings - 2017 IEEE 31st International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2017). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/IPDPSW.2017.158

Machovec, Dylan ; Pasricha, Sudeep ; Maciejewski, Anthony A. et al. / Preemptive resource management for dynamically arriving tasks in an oversubscribed heterogeneous computing system. Proceedings - 2017 IEEE 31st International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2017. Institute of Electrical and Electronics Engineers Inc., 2017. pp. 54-64 (Proceedings - 2017 IEEE 31st International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2017).

@inproceedings{f18740252a4c4a7484de7ee2d28eb1e9,

title = "Preemptive resource management for dynamically arriving tasks in an oversubscribed heterogeneous computing system",

abstract = "We design resource management heuristics that assign serial tasks to the nodes of a heterogeneous high performance computing (HPC) system. The value of completing these tasks is modeled using monotonically decreasing utility functions that represent the time-varying importance of the task. The value of completing a task is equal to its utility function at the time of its completion. The overall performance of this system is measured using the total utility earned by all tasks during some interval of time. To maximize the performance of such a system where the preemption of tasks is possible, we have designed, analyzed, and compared a set of resource allocation heuristic techniques. We combine two utility-aware heuristics with three different preemption techniques to create six preemption-capable heuristics. We also consider the two utility-aware heuristics without preemption. We use simulation studies to evaluate this set of eight heuristics and compare them with an FCFS heuristic, which is often used in real systems, and random assignments. In general, our set of eight heuristics is able to significantly outperform the comparison heuristics, and the preemption-capable heuristics are able to significantly increase the utility earned compared to the heuristics that do not use preemption. We analyze the performance tradeoffs among the different preemption-capable heuristics under a variety of oversubscribed workload environments.",

keywords = "heterogeneous computing, preemption, resource management heuristics, scheduling, utility functions",

author = "Dylan Machovec and Sudeep Pasricha and Maciejewski, {Anthony A.} and Siegel, {Howard Jay} and Koenig, {Gregory A.} and Michael Wright and Marcia Hilton and Rajendra Rambharos and Thomas Naughton and Neena Imam",

note = "Publisher Copyright: {\textcopyright} 2017 IEEE.; 31st IEEE International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2017 ; Conference date: 29-05-2017 Through 02-06-2017",

year = "2017",

month = jun,

day = "30",

doi = "10.1109/IPDPSW.2017.158",

language = "English",

series = "Proceedings - 2017 IEEE 31st International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2017",

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

pages = "54--64",

booktitle = "Proceedings - 2017 IEEE 31st International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2017",

}

Machovec, D, Pasricha, S, Maciejewski, AA, Siegel, HJ, Koenig, GA, Wright, M, Hilton, M, Rambharos, R, Naughton, T & Imam, N 2017, Preemptive resource management for dynamically arriving tasks in an oversubscribed heterogeneous computing system. in Proceedings - 2017 IEEE 31st International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2017., 7965025, Proceedings - 2017 IEEE 31st International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2017, Institute of Electrical and Electronics Engineers Inc., pp. 54-64, 31st IEEE International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2017, Orlando, United States, 05/29/17. https://doi.org/10.1109/IPDPSW.2017.158

Preemptive resource management for dynamically arriving tasks in an oversubscribed heterogeneous computing system. / Machovec, Dylan; Pasricha, Sudeep; Maciejewski, Anthony A. et al.
Proceedings - 2017 IEEE 31st International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2017. Institute of Electrical and Electronics Engineers Inc., 2017. p. 54-64 7965025 (Proceedings - 2017 IEEE 31st International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2017).

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

TY - GEN

T1 - Preemptive resource management for dynamically arriving tasks in an oversubscribed heterogeneous computing system

AU - Machovec, Dylan

AU - Pasricha, Sudeep

AU - Maciejewski, Anthony A.

AU - Siegel, Howard Jay

AU - Koenig, Gregory A.

AU - Wright, Michael

AU - Hilton, Marcia

AU - Rambharos, Rajendra

AU - Naughton, Thomas

AU - Imam, Neena

PY - 2017/6/30

Y1 - 2017/6/30

N2 - We design resource management heuristics that assign serial tasks to the nodes of a heterogeneous high performance computing (HPC) system. The value of completing these tasks is modeled using monotonically decreasing utility functions that represent the time-varying importance of the task. The value of completing a task is equal to its utility function at the time of its completion. The overall performance of this system is measured using the total utility earned by all tasks during some interval of time. To maximize the performance of such a system where the preemption of tasks is possible, we have designed, analyzed, and compared a set of resource allocation heuristic techniques. We combine two utility-aware heuristics with three different preemption techniques to create six preemption-capable heuristics. We also consider the two utility-aware heuristics without preemption. We use simulation studies to evaluate this set of eight heuristics and compare them with an FCFS heuristic, which is often used in real systems, and random assignments. In general, our set of eight heuristics is able to significantly outperform the comparison heuristics, and the preemption-capable heuristics are able to significantly increase the utility earned compared to the heuristics that do not use preemption. We analyze the performance tradeoffs among the different preemption-capable heuristics under a variety of oversubscribed workload environments.

AB - We design resource management heuristics that assign serial tasks to the nodes of a heterogeneous high performance computing (HPC) system. The value of completing these tasks is modeled using monotonically decreasing utility functions that represent the time-varying importance of the task. The value of completing a task is equal to its utility function at the time of its completion. The overall performance of this system is measured using the total utility earned by all tasks during some interval of time. To maximize the performance of such a system where the preemption of tasks is possible, we have designed, analyzed, and compared a set of resource allocation heuristic techniques. We combine two utility-aware heuristics with three different preemption techniques to create six preemption-capable heuristics. We also consider the two utility-aware heuristics without preemption. We use simulation studies to evaluate this set of eight heuristics and compare them with an FCFS heuristic, which is often used in real systems, and random assignments. In general, our set of eight heuristics is able to significantly outperform the comparison heuristics, and the preemption-capable heuristics are able to significantly increase the utility earned compared to the heuristics that do not use preemption. We analyze the performance tradeoffs among the different preemption-capable heuristics under a variety of oversubscribed workload environments.

KW - heterogeneous computing

KW - preemption

KW - resource management heuristics

KW - scheduling

KW - utility functions

UR - http://www.scopus.com/inward/record.url?scp=85028043462&partnerID=8YFLogxK

U2 - 10.1109/IPDPSW.2017.158

DO - 10.1109/IPDPSW.2017.158

M3 - Conference contribution

AN - SCOPUS:85028043462

T3 - Proceedings - 2017 IEEE 31st International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2017

SP - 54

EP - 64

BT - Proceedings - 2017 IEEE 31st International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2017

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 31st IEEE International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2017

Y2 - 29 May 2017 through 2 June 2017

ER -

Machovec D, Pasricha S, Maciejewski AA, Siegel HJ, Koenig GA, Wright M et al. Preemptive resource management for dynamically arriving tasks in an oversubscribed heterogeneous computing system. In Proceedings - 2017 IEEE 31st International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2017. Institute of Electrical and Electronics Engineers Inc. 2017. p. 54-64. 7965025. (Proceedings - 2017 IEEE 31st International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2017). doi: 10.1109/IPDPSW.2017.158

Preemptive resource management for dynamically arriving tasks in an oversubscribed heterogeneous computing system

Abstract

Publication series

Conference

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this