Space-Efficient Implementation of Nested Parallelism

114k compressed postscript / 339k 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 a scheduling algorithm that is provably space-efficient and time-efficient for nested parallel languages. In addition to proving the space and time bounds of the parallel schedule generated by the algorithm, we demonstrate that it is efficient in practice. We have implemented a runtime system that uses our algorithm to schedule 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, language implementation.

@inproceedings	{NarlikarPPoPP97,
author		= "Girija J. Narlikar and Guy E. Blelloch",
title		= "Space-Efficient Implementation of Nested Parallelism",
booktitle	= "Proceedings of the Sixth ACM SIGPLAN Symposium on 
			Principles and Practice of Parallel Programming",
year		= 1997,
month		= "June",
pages		= "25--36"}