Efficient Resource Scheduling in Multiprocessors
Abstract
As multiprocessing becomes increasingly successful in scientific and commercial computing, parallel systems will be subjected to increasingly complex and challenging workloads. To ensure good job response and high resource utilization, algorithms are needed to allocate resources to jobs and to schedule the jobs. The focus of this thesis is in between the theory and practice of scheduling: it includes modeling, performance analysis and practical algorithmic. We present a variety of new techniques for scheduling problems relevant to parallel scientific computing. The thesis progresses from new compile-time algorithms for message scheduling through new runtime algorithms for processor scheduling to a unified framework for allocating multiprocessor resources to competing jobs while optimizing both individual application performance and system throughput. The compiler algorithm schedules network communication for parallel programs accessing distributed arrays. By analyzing and optimizing communication patterns globally, we often reduce communication costs by factors of two to three in an implementation based on IBM's High-Performance Fortran compiler. The best parallelizing compilers at present support regular, static, array-based parallelism. But parallel programmers are out-growing this model. Many scientific and commercial applications have a two-level structure: the outer level is a potentially irregular and dynamic task graph, and the inner level comprises relatively regular parallelism within each task. We give new runtime algorithms for allocating processors to such tasks.
Document Details
- Document Type
- Technical Report
- Publication Date
- Nov 01, 1996
- Accession Number
- ADA637067
Entities
People
- Soumen Chakrabarti
Organizations
- University of California, Berkeley