Space-efficient Scheduling for Parallel, Multithreaded Computations
Abstract
The goal of high level parallel programming models or languages is to facilitate the writing of well structured, simple and portable code. However, the performance of a program written using a high level language may vary significantly, depending on the implementation of the underlying system. This dissertation presents two asynchronous scheduling algorithms that provide worst case upper bounds on the space and time requirements of high level, nested parallel programs on shared memory machines. In particular, for a program with D depth and a serial space requirement of S(sub 1), both algorithms guarantee a space bound of S(sub 1) + O(K p D) on p processors. Here, K is a user controllable runtime parameter, which specifies the amount of memory a thread may allocate before being preempted by the scheduler. Typically, in practice, K is fixed to be a few thousand bytes. Most parallel programs have a small depth D. For such programs, the above space bound is lower than the space bound provided by any previously implemented system. The first of the two scheduling algorithms presented in this dissertation, algorithm AsyncDF, prioritizes threads at runtime by their serial, depth first execution order, and preempts threads before they allocate too much memory. This ensures that the parallel execution does not require too much more memory than the serial execution. The second scheduling algorithm, DFDeques, enhances algorithm AsyncDF by adding ideas from work stealing. It replaces the single, fiat priority queue of AsyncDF with ordered, per-processor queues of ready threads, and allows some deviation from the depth first priorities while scheduling threads. Consequently, it results in lower scheduling overheads and better locality than AsyncDF for finer grained threads, at the cost of a slight increase in memory requirement. To ensure scalability with the number of processors, I also describe and analyze fully parallelized versions of the schedulers for both the algorithmc
Document Details
- Document Type
- Technical Report
- Publication Date
- May 01, 1999
- Accession Number
- ADA366195
Entities
People
- Girija Narlikar
Organizations
- Carnegie Mellon University