Pthreads for Dynamic Parallelism

Girija J. Narlikar and Guy E. Blelloch
CMU-CS-98-114, April 1998

60k compressed postscript


Expressing a large number of lightweight, parallel threads in a shared address space significantly eases the task of writing a parallel program. Threads can be dynamically created to execute individual parallel tasks; the implementation schedules these threads onto the processors and effectively balances the load. However, unless the threads scheduler is designed carefully, such a parallel program may suffer poor space and time performance.

In this paper, we evaluate the performance of a native, lightweight POSIX threads (Pthreads) library on a shared memory machine using a set of parallel benchmarks that dynamically create a large number of threads. By studying the performance of one of the benchmarks, matrix multiply, we show how simple, yet provably good modifications to the library can result in significantly improved space and time performance. With the modified Pthreads library, each of the parallel benchmarks performs as well as its coarse-grained, hand-partitioned counterpart. These results demonstrate that, provided we use a good scheduler, the rich functionality and standard API of Pthreads can be combined with the advantages of dynamic, lightweight threads to result in high performance.

author		= "Girija J. Narlikar and Guy E. Blelloch",
title		= "Pthreads for Dynamic Parallelism",
institution	= "Computer Science Department, Carnegie Mellon University",
number		= "CMU-CS-98-114",
year		= 1998,
month		= "April"