Space-efficient Implementation of Parallel, Multithreaded Computations

	                            Girija Narlikar
	                     CMU School of Computer Science


	Symmetric multiprocessors (SMPs) are fast becoming affordable; their uses now
	range from desktops to high-end servers.  In addition, many of today's 
	applications, including those in business, science and engineering,
	could benefit significantly from the use of multiple processors in such SMPs.
	However, due to the highly irregular and dynamic nature of these applications,
	the complexity of parallelizing them remains prohibitive.  A solution 
	is to use fine-grained, lightweight threads to express the programs in a 
	natural, high-level style.  Unless the thread system is implemented carefully, 
	however, the program can easily suffer from poor space and time performance.

	In this talk, I present two asynchronous scheduling algorithms that 
	provide low worst-case bounds on the space and time requirements of 
	high-level,  multithreaded programs on SMPs.  For programs with sufficient 
	parallelism, the space bound is significantly lower than that of previously 
	implemented space-efficient systems.  The proposed scheduling algorithms limit 
	the space requirement of a multithreaded program by prioritizing the threads 
	at runtime by their serial execution order, and by preempting threads before 
	they allocate too much memory.

	To verify that the theoretically-efficient scheduling algorithms are
	also practical, I have implemented them in the context of two multithreaded 
	runtime systems for SMPs, including an existing, commercial Pthreads package.  
	Experimental results for irregular and dynamic benchmarks indicate that my 
	schedulers effectively reduce memory usage compared to previous techniques, 
	while providing good speedups.  The scheduling algorithms also provide a 
	user-adjustable trade-off between running time and memory requirement.