Figure 1: maximizing communication locality

of sequential code, which are guaranteed to terminate, onece they have been scheduled. At the same time, thread represent the basic scheduling units, which can be scheduled to execute on any processor. By exposing threads in this way, we can experiment with various static and dynamic scheduling policies to optimize the overall machine utilization. For example:

• A thread can be made to directly transfer control to another thread, similar to the control transfer mechanism used to implement tail-recursions. This mechanism bypasses the dynamic scheduling entirely, thus avoiding all of its associated costs.

• The scheduler uses work stealing as its default policy. This creates patterns of locality in which threads can pass arguments through local memory rather than across the network most of the time, thus greatly reducing the communication frequency.

We tried to show the effect of these optimizations in Figure 1. As this diagram clearly suggests, they provide an optimal compromise between maintaining the locality, or sequentiality, of the parallel computation and the demand for dynamic load balancing.

The rest of this paper is structured as follows. Section 2 introduces the PCM thread specification language and present in some detail all of its components. Section 3 introduces a cost model, intended to clarify the reader’s intuition of understanding the costs involved in dynamic execution. Section ?? and section ?? contain in depth explanation of two actual problems, implemented with the PCM package. Section 6 concludes the paper.

2 The Parallel Continuation Machine

The parallel continuation machine implements an SPMD programming model, where all processors keep their own local copy of the entire code. The execution itself is completely asynchronous, meaning that each node may execute entirely different pieces of the program.

2.1 Elements of the PCM

A PCM program consists of a collection of threads cooperatively solving the actual problem. Statically, a thread identifies nothing more than a sequence of instructions, written in the machine language of the processor. At runtime, an application can create arbitrary numbers of dynamic instances of a static thread, each with its own set of arguments.^{2}

The PCM thread specification language, which is explained in the remainder of this section, allows the programmer to define threads and to specify how threads communicate with each other. All machine specific execution details, such as dynamic load balancing or the mechanism required to enable transparent inter-thread communication, are part of the PCM runtime system and do not have to be specified by the user. This should simplify the task of writing explicit multithreaded applications without sacrificing the programmer’s power for experimentation.

Figure 2: The PCM model: threads, closures and continuations

A dynamic thread is created by making a closure. A closure is essentially a data structure that contains a pointer to the thread code and all the arguments needed to execute the code. The thread is ready to execute when the closure becomes full, or in other words, when it has obtained all the arguments. Full closures are passed to the scheduler, which keeps them in a ready queue and will later schedule them for the encapsulated threads to run.

Reflecting the nature of parallel processing, a closure can be created with some of the arguments missing. These arguments are to be supplied by other threads in the future. A thread supplying an argument to a (non-ready) closure must obtain a reference to where the argument is to be sent. Such references will be called continuations, or in other words, a continuation is just a pointer to a closure plus an integer offset into the closure. Note that we are slightly abusing the term continuation here, which is used to refer (in sequential computations) to the rest of the computation seen from a particular program control point. In parallel programs, however, there is usually no such thing as “the rest of the computation” from a single control point, and the issue of how a thread can be regarded as “continuing” from another thread, which sends one of the needed argument, is further complicated by synchronization involved.

In order to detect when a closure becomes full, every closure has an additional slot called the join counter, indicating the number of its outstanding arguments. The join counter is initialized with an integer equal to the number of missing arguments at closure creation time, and decremented each time the closure receives an argument. No closure is given to the scheduler until the join counter reaches zero.

2We decided not to introduce a new term for these dynamic thread instances. No confusion should occur if the reader bears in mind that the word thread is used both in a static and in a dynamic sense.

2.2 The Thread Specification Language

The thread specification language described in this section is implemented as an extension to C. An example program computing the Fibonacci function is shown in Figure 3.

thread fib spread (int n, cont parent) {

if (n<2) send argument (n, parent); else { closure k1, s1, s2;

k1 = make closure (fib sum, , , parent);

s1 = make closure (fib spread, n−1, cont{k1, fib sum:x}); s2 = make closure (fib spread, n−2, cont{k1, fib sum:y}); post (s1); post (s2);

} }

thread fib sum (int x, int y, cont parent) { send yargument (x+y, parent); }

Figure 3: multithreaded PCM Example program that computes the Fibonacci function in two threads.

In this language, a program consists of threads, marked by the specifier thread, and normal C functions. A preprocessor will expand just the threads into C functions, while copying the rest of the C code literally. The resulting C program can then be compiled by a C compiler and linked with the PCM runtime library.

Runtime primitives are used by the threads to create closures, sending arguments, and transferring closures to the scheduler:

• make_closure (Thread, arg_{1}, …, arg_{n}) Allocates a closure of size n + 2, and returns a pointer to the closure. The two additional slots are reserved for the join counter and the code pointer. Closures can be created without specifying all the arguments, in which case a missing argument has to be indicated by “_”. The join counter is always initialized to the the number of missing arguments.

• post (k) Hands the closure k over to the scheduler. Only a full closure can be posted inside the thread that created it. Closures with empty slots will be posted by send_argument when the join counter reaches zero.

• send_argument (v, c) Sends value v to continuation c and decrements the join counter of the target closure. The closure is posted if the join counter becomes zero. A continuation has the type cont and contains two fields: a pointer to a closure, and an integer offset within the closure. A new continuation can be constructed, for example, using the expression cont{k1, sum:x}, where k1 is a closure pointer and sum:x a symbolic reference to the zeroth argument slot.

The preprocessor expands a thread, for example fib_spread, into a C function that takes a single argument, namely a closure, and fetches all specified arguments from the closure before starting its actual execution.

2.3 Executing a PCM Program

We shall use Figure 4 to illustrate how the Fibonacci program runs on a single processor. The only difference when there are multiple processors is that full closures may be migrated to ensure a balanced load across all available processors. These scheduling issues will be discussed in more details in section 3.

The execution of a PCM program can be divided into three phases: initialization, computation, and termination. We did not show the initializtion and termination code in figure 3, since they are not really important. The first and third phases are usually very short, with the computation phase constituting the bulk of the overall execution.

During the initialization phase, shown in Figure 4.0, the program creates two closures. One specifies the start of the computation, in this example a ready instance of fib_spread), and one specifies the actions to be taken when the computation ends, in this example a non-ready instance of a special thread called top. This top thread is supplied by the runtime system and its responsabilities are the to terminate the computation and to print the result(s). The top closure can be instructed to expect any number of results and must be the one to execute last.

During the computation phase, the scheduler enters a perpetual loop: popping a full closure from the ready queue; calling the thread function, such as fib_spread or fib_sum, specified by the closure with closure supplied as the only argument. Figure 4.1–4.7 show snapshots of the machine state, once after each full closure is scheduled to run. For example, in figure 4.1, the closure for fib_spread with argument 3 is scheduled to run. It creates three closures: two full ones for fib_spread with arguments 2 and 1 respectively, and a closure for fib_sum waiting for two arguments. The full closures are immediately posted. The waiting closure captures the parent continuation, and creates two new continuations, one for each argument slot, that are passed to the closures to its left and right. In figure 4.2, the top closure (lower-left) in the ready queue is scheduled to run, which sends the argument 1 to the fib_sum closure, and decrements the join counter there from 2 to 1, …, etc.

During the termination phase, shown in Figure 4.8, the top thread is scheduled to run. It will print the result of the computation and then cause the scheduler to exit the loop, thereby terminating the computation. For multiprocessor computations, the processor on which the top thread is executed also signals schedulers on other processors to exit their work loops.

0  1  2

3  4  5

6  7  8

Figure 4: Snapshots of the state of PCM after each top-most closure in the ready queue is scheduled to run and before it is released.

2.4 Tail-Calls

A thread may directly call other threads via the following runtime primitive:

• tail_call (Thread, arg_{1}, …, arg_{n})

A tail-call represents a more efficient invocation of a thread, avoiding any of the the dynamic execution costs incurred otherwise. In the example shown in Figure ??, the thread fib_spread creates two full closures s1 and s2 and posts both of them before releasing control and returning to the scheduler. After receiving control, the immediate action of the scheduler will be to pop the s2 closure and to call its thread function fib_spread, which in turn needs to unpack the s2 closure prior to doing actual work. We can thus avoid this costly detour through the scheduler by rewriting the code with a tail-call as follows:

s1 = make closure (spread, n−1, cont{k1, sum:x}); post (s1); tail call (spread, n−2, cont{k1, sum:y});

To implement this mechanism, the thread preprocessor actually expands a thread into two C functions: a general entry version, which is what we have shown before; and a fast entry version which receives all arguments directly. A tail_call is thus converted into a standard C function call to the fast entry version. The actual performance improvements obtained with the tail-call mechanism can be quite impressive, especially for fine-grained applications, such as the Fibonacci example, where the performance improved by almost 25 %.

2.5 Passing Vectors in Closures

This section introduces an additional mechanism provided by the thread language to allow vectors of arbitrary sizes to be passed in closures. These vectors can then be referenced within a thread like any other local variable. Vector arguments are always packed into the tail of a closure, after all the other non-vector arguments. The thread specification

thread foo (…, type vect[])

declares a vector argument vect of type type. The vector argument must always be the last argument and it is the responsibility of the creator of the closure to initialize the vector. For example, the expression

make_closure (foo, …, vect = [size])

creates a closure for foo, allocating a vector of size and declares vect to be a pointer initialized to the zeroth word of the vector. vect must be used subsequently to initialize the vector, which would otherwise be empty. If we write _instead of vect, then the vector is intentionally left empty, and the size will be added to the initial join counter setting.

2.6 Partitioning Functions into Threads

Consider the following C program, which can be viewed as the “source” of the two threads shown in Figure 3.

int fib (int n)

{ if (n<2) return (n); else return (fib(n−1) + fib(n−2));

}

The function fib as shown has no parallelism. It order to expose parallelism, we must post one or both of the sub-calls to fib. But here we encounter a major difficulty: the addition depends on the return value of both calls. How can we set up the linkage between threads or instruct the scheduler to execute the addition after both sub-calls, implemented as dynamic threads, complete?

One well-known solution, of course, is to use a preemptive thread model. In such a model, the runtime system would suspend an executing fib thread after it forked off its two subcalls and later, when the two sub-calls terminate, resumes the thread so that it can continue its execution. Since both, suspension and resumption are performed by the runtime system, they need to be fairly generic, blindly saving/restoring everything that is volatile. These mechanisms can be expected to be too heavy for cases where threads only run for relatively short durations.

The solution shown in Figure 3 uses a non-preemptive thread model. In this model, we have to split the original programs into threads, so that all threads become non-preemptive entities – this means, threads are guaranteed to terminate once they start executing. For example, thread fib_spread makes a closure for sum, which is exactly saving the context needed for sum to execute later. Now the difference is that the user thread performs the context switch, knowing exactly what to save. In this example, only the continuation needs to saved parent. The result is a light-weight, more efficient implementation.

From a language point of view, threads provide an abstraction which is lower than the ones of functions. As we have seen, a function such as fib translates into two threads. As pointed out in the introduction, there are compilers with automatic partitioners, systematically converting and packaging a function into threads. Automatic partitioning is still a very active area of research (see for example, []), but we will not touch it further, since we are mainly interested in using the thread language in its own right in this paper.

3 Scheduling PCM Threads on a Multiprocessor

This section will introduce a cost model for the PCM to motivate the work stealing scheduling system, which we implemented to schedule PCM threads on the CM-5 parallel processor. All communications mechanisms, required to implement the work stealer and the inter-thread communication, have been build using a version of active messages [?].

As Figure 6 tries to suggest, we will equate useful computation with what a sequential program would have to do and classify everthing else, such as communication, synchronization, and dynamic scheduling as additional overhead. The goal of this classification is to