Space-efficient scheduling of multithreaded computations
Robert D. Blumofe, Charles E. Leiserson · ACM Symposium on Theory of Computing (STOC) · 1993
. This paper considers the problem of scheduling dynamic parallel computations to achieve linear speedup without using significantly more space per processor than that required for a single-processor execution. Utilizing a new graph-theoretic model of multithreaded computation, execution efficiency is quantified by three important measures: T 1 is the time required for executing the computation on 1 processor, T1 is the time required by an infinite number of processors, and S 1 is the space required to execute the computation on 1 processor. A computation executed on P processors is time-efficient if the time is O(T 1 =P + T1 ), that is, it achieves linear speedup when P = O(T 1 =T1 ), and it is space-efficient if it uses O(S 1 P ) total space, that is, the space per processor is within a constant factor of that required for a 1-processor execution. The first result derived from this model shows that there exist multithreaded computations such that no execution schedule can simultan...
Cited by 70 works. doi:10.1145/167088.167196
Authors
References
- Bounds for Certain Multiprocessing Anomalies
- Bounds on Multiprocessing Timing Anomalies
- A Bridging Model for Parallel Computation
- Active messages
- The Parallel Evaluation of General Arithmetic Expressions
- MULTILISP: a language for concurrent symbolic computation
- Fine-grain parallelism with minimal hardware support: a compiler-controlled threaded abstract machine
- Probabilistic construction of deterministic algorithms: Approximating packing integer programs
- APRIL
- Scheduling multithreaded computations by work stealing