Utilization, predictability, workloads, and user runtime estimates in scheduling the IBM SP2 with backfilling
The work
| Authors | Ahuva Mu’alem; Dror G. Feitelson |
|---|---|
| Editors | |
| Type | article |
| Year | 2001 |
| Citekey | mualem2001utilization |
Where it appeared
| Published in | IEEE Transactions on Parallel and Distributed Systems |
|---|---|
| Publisher | Institute of Electrical and Electronics Engineers |
| Volume | 12 |
| Issue | 6 |
| Pages | 529--543 |
Identifiers
| DOI | 10.1109/71.932708 |
|---|---|
| OpenAlex | W2112168774 |
Access
| Landing page | https://doi.org/10.1109/71.932708 |
|---|
From OpenAlex, which stores abstracts as an index of words and their positions: what is shown is rebuilt from that, and reads fluently whether or not it is what the author wrote.
Abstract
Scheduling jobs on the IBM SP2 system and many other distributed-memory MPPs is usually done by giving each job a partition of the machine for its exclusive use. Allocating such partitions in the order in which the jobs arrive (FCFS scheduling) is fair and predictable, but suffers from severe fragmentation, leading to low utilization. This situation led to the development of the EASY scheduler which uses aggressive backfilling: Small jobs are moved ahead to fill in holes in the schedule, provided they do not delay the first job in the queue. We compare this approach with a more conservative approach in which small jobs move ahead only if they do not delay any job in the queue and show that the relative performance of the two schemes depends on the workload. For workloads typical on SP2 systems, the aggressive approach is indeed better, but, for other workloads, both algorithms are similar. In addition, we study the sensitivity of backfilling to the accuracy of the runtime estimates provided by the users and find a very surprising result. Backfilling actually works better when users overestimate the runtime by a substantial factor.
How it got here
| How it got here | agent via openalex |
|---|---|
| Added | 2026-10-29 05:42 UTC |
| Not denied by | a person 2026-10-29 17:12 UTC |
Cite it as
@article{mualem2001utilization,
title = {Utilization, predictability, workloads, and user runtime estimates in scheduling the IBM SP2 with backfilling},
author = {Ahuva Mu’alem and Dror G. Feitelson},
year = {2001},
journal = {IEEE Transactions on Parallel and Distributed Systems},
publisher = {Institute of Electrical and Electronics Engineers},
volume = {12},
number = {6},
pages = {529--543},
doi = {10.1109/71.932708},
}
This record lives at https://refs.drheap.org/mualem2001utilization/ and will keep doing so.