MANAGING STORAGE FOR MULTITHREADED COMPUTATIONS
Robert D. Blumofe · DSpace@MIT (Massachusetts Institute of Technology) · 1992
Multithreading has become a dominant paradigm in general purpose MIMD parallel computation. To execute a multithreaded computation on a parallel computer, a scheduler must order and allocate threads to run on the individual processors. The scheduling algorithm dramatically affects both the speedup attained and the space used when executing the computation. We consider the problem of scheduling multithreaded computations to achieve linear speedup without using significantly more space-per-processor than required for a single-processor execution. We show that for general multithreaded computations, no scheduling algorithm can simultaneously make efficient use of space and time. In particular, we show that there exist multithreaded computations such that any execution schedule X that achieves P-processor execution time T P (X ) T 1 =ae, where T 1 is the minimum possible serial execution time, must use space at least S P (X ) 1 4 (ae \\Gamma 1) p T 1 + S 1 , where S 1 is the space use...