By David Keppel

Threads are units of concurrent execution that can be viewed as abstract data types (ADTs) with operations to initialize and run them. It is common to improve performance by hard-coding allocation and scheduling policies, but that has led to the development of many threads packages, each with policies tuned for a particular set of applications. Further, the machine-dependence of threads packages restricts the availability of applications built on top of them. This paper examines techniques for building threads packages and discusses tradeoffs between performance, flexibility, and portability. It then introduces QuickThreads, a simple threads toolkit with a portable interface. This paper shows how QuickThreads can be used to implement a basic uniprocessor threads package and discusses the implementation of portable threads packages tuned to the needs of particular applications. For example, QuickThreads can be used to build barrier synchronization that runs in O(lg2 processors) time units instead of the traditional O(lg2 threads). This paper also reports on the performance and implementation of QuickThreads and describes some experiences using it to reimplement and port existing multiprocessor threads packages.

%A David Keppel
%T Tools and Techniques for Building Fast Portable Threads Packages
%R UWCSE 93-05-06
%I University of Washington Department of Computer Science and Engineering
%D May 1993

@techreport{Keppel:93b,
    author={David Keppel},
    title={Tools and Techniques for Building Fast Portable Threads Packages},
    number={UWCSE 93-05-06},
    institution={University of Washington Department of Computer
                 Science and Engineering},
    month={May},
    year={1993}
}

An older version is also available, because there's bound to be obscure problems with the new version.

It's usually pretty simple to port QuickThreads. if you'd like to write code for another target, send e-mail to pardo@cs.washington.edu. Some retargets have already been started.

• Register Windows and User-Space Threads on the SPARC, which explains the SPARC implementation here in more detail.
• FastThreads, a predecessor of QuickThreads. Papers and source code for FastThreads are both available.
• NewThreads, a contemporary of QuickThreads. Papers and source code (including a user document) are available. NewThreads runs on several machines that currently lack QuickThreads targets (including the i860, PowerPC, 68000 and HP-PA), so if you want to help retarget QuickThreads, your job may be really easy. (Why use QuickThreads? NewThreads is a whole threads package and is designed for multiprocessors without shared memory; QuickThreads is a toolkit used for building threads packages across a wider variety of architectures.)
• Presto, a predecessor of QuickThreads. Papers and source code for Presto are available, as are various multithreaded Presto applications.
• Scheduler Activations work including the UW tech report Adding Scheduler Activations to Mach 3.0 (92KB).