Scheduling algorithms to improve utilization in toroidal-interconnected systems

BlueGene/L is a massively parallel cellular architecture system with a toroidal inter-connect, currently being developed at the IBM T.J.Watson Research Center. Cellular architectures with a toroidal interconnect are effective at producing highly scalable computing systems, but typically require job partitions to be both rectangular and contiguous. These restrictions introduce fragmentation issues that affect the utilization of the system and the wait time and slowdown of queued jobs. To solve these fragmentation problems, this thesis presents the analysis and application of scheduling algorithms that augment a baseline first come first serve (FCFS) scheduler. Restricting ourselves to space-sharing techniques, which constitute a simpler solution to the requirements of cellular computing, we present simulation results for migration and backfilling techniques on BlueGene/L. These techniques are explored individually and jointly to determine their impact on the system. We develop an efficient Projection Of Partitions (POP) algorithm for determining the size of the largest free rectangular partition in a toroidal system, a basic operation that is the computational bottleneck for our scheduling algorithms. Our results demonstrate that migration may be effective for a pure FCFS scheduler but that backfilling produces even more benefits. We also show that migration may be combined with backfilling to produce more opportunities to better utilize a parallel machine.

Department dc:contributor.department

Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2003

Author dc:creator

• Krevat, Elie, 1980-

Advisor dc:contributor.advisor

• José E. Moreira and Madhu Sudan.

• Electrical Engineering and Computer Science.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/16978

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/16978