Space-Efficient Scheduling of Nested Parallelism

ACM Transactions on Programming Languages and Systems (TOPLAS), 21(1), January 1999.

Earlier version appeared in the proceeding of the Sixth ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, June 1997.

140k compressed postscript / 470k PDF

Abstract: Many of today's high level parallel languages support dynamic, fine-grained parallelism. These languages allow the user to expose all the parallelism in the program, which is typically of a much higher degree than the number of processors. Hence an efficient scheduling algorithm is required to assign computations to processors at runtime. Besides having low overheads and good load balancing, it is important for the scheduling algorithm to minimize the space usage of the parallel program.

This paper presents an on-line scheduling algorithm that is provably space-efficient and time-efficient for nested parallel languages. For a computation with depth D and serial space requirement S₁ the algorithm generates a schedule that requires at most S₁ + O(pD) space (including scheduler space) on p processors. To allow the scheduler to scale with the number of processors, we also parallelize the scheduler and analyze the space and time bounds of the computation to include scheduling costs. In addition to showing that the scheduling algorithm is space and time efficient in theory, we demonstrate that it is effective in practice. We have implemented a runtime system that uses our algorithm to schedule lightweight parallel threads. The results of executing parallel programs on this system show that our scheduling algorithm significantly reduces memory usage compared to previous techniques, without compromising performance.

Keywords: Space efficiency, dynamic scheduling, nested parallelism, multithreading, scalable runtime systems, parallel language implementation.

@article	{NarlikarToplas99,
author		= "Girija J. Narlikar and Guy E. Blelloch",
title		= "Space-Efficient Scheduling of Nested Parallelism",
journal		= "{ACM} Transactions on Programming Languages and Systems", 
volume		= 21,
number 		= 1,
year		= 1999,
month		= "January",
pages		= "138--173"}