Space-efficient scheduling for parallel, multithreaded computations
Girija J. Narlikar, Guy E. Blelloch · 1999
Abstract The goal of high-level parallel programming models or languages is to facilitate the writing ofwell-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 underlyingsystem. This dissertation presents two asynchronous scheduling algorithms that provide worst-case up-per 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 S1, both algorithms guarantee a space bound of S1 + O(K \\Delta p \\Delta D) on p processors. Here, K is auser-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 thousandbytes. Most parallel programs have a small depth D. For such programs, the above space bound islower than the space bound provided by any previously implemented system.