Introduction to Algorithms December 5, 2005 Massachusetts Institute of Technology 6.046J/18.410J Professors Erik D. Demaine and Charles E. Leiserson Handout 29 A Minicourse on Dynamic Multithreaded Algorithms Charles E. Leiserson ∗ MIT Computer Science and Artificial Intelligence Laboratory Cambridge, Massachusetts 02139, USA December 5, 2005 Abstract This tutorial teaches dynamic multithreaded algorithms using a Cilk-like [11, 8, 10] model. The material was taught in the MIT undergraduate class 6.046 Introduction to Algorithms as two 80-minute lectures. The style of the lecture notes follows that of the textbook by Cormen, Leiserson, Rivest, and Stein [7], but the pseudocode from that textbook has been “Cilkified” to allow it to describe multithreaded algorithms. The first lecture teaches the basics behind multithreading, including defining the measures of work and critical-path length. It culminates in the greedy scheduling theorem due to Graham and Brent [9, 6]. The second lecture shows how parallel applications, including matrix multiplication and sorting, can be analyzed using divide-and-conquer recurrences. 1 Dynamic multithreaded programming As multiprocessor systems have become increasingly available, interest has grown in parallel pro-gramming. Multithreaded programming is a programming paradigm in which a single program is broken into multiple threads of control which interact to solve a single problem. These notes provide an introduction to the analysis of “dynamic” multithreaded algorithms, where threads can be created and destroyed as easily as an ordinary subroutine can be called and return. 1.1 Model Our model of dynamic multithreaded computation is based on the procedure abstraction found in virtually any programming language. As an example, the procedure FIB gives a multithreaded algorithm for computing the Fibonacci numbers:1 ∗Support was provided in part by the Defense Advanced Research Projects Agency (DARPA) under Grant F30602-97-1-0270, by the National Science Foundation under Grants EIA-9975036 and ACI-0324974, and by the Singapore-MIT Alliance. 1This algorithm is a terrible way to compute Fibonacci numbers, since it runs in exponential time when logarithmic methods are known [7, pp. 902–903], but it serves as a good didactic example. 2Handout 29: Dynamic Multithreaded Algorithms 3 FIB(n) 1 if n < 2 2 then return n 3 x ← spawn FIB(n − 1) 4 y ← spawn FIB(n − 2) 5 sync 6 return (x + y) A spawn is the parallel analog of an ordinary subroutine call. The keyword spawn before the subroutine call in line 3 indicates that the subprocedure FIB(n − 1) can execute in parallel with the procedure FIB(n) itself. Unlike an ordinary function call, however, where the parent is not resumed until after its child returns, in the case of a spawn, the parent can continue to execute in parallel with the child. In this case, the parent goes on to spawn FIB(n − 2). In general, the parent can continue to spawn off children, producing a high degree of parallelism. A procedure cannot safely use the return values of the children it has spawned until it executes a sync statement. If any of its children have not completed when it executes a sync, the procedure suspends and does not resume until all of its children have completed. When all of its children return, execution of the procedure resumes at the point immediately following the sync statement. In the Fibonacci example, the sync statement in line 5 is required before the return statement in line 6 to avoid the anomaly that would occur if x and y were summed before each had been computed. The spawn and sync keywords specify logical parallelism, not “actual” parallelism. That is, these keywords indicate which code may possibly execute in parallel, but what actually runs in parallel is determined by a scheduler, which maps the dynamically unfolding computation onto the available processors. We can view a multithreaded computation in graph-theoretic terms as a dynamically unfolding dag G = (V, E), as is shown in Figure 1 for FIB. We define a thread to be a maximal sequence of instructions not containing the parallel control statements spawn , sync, and return . Threads make up the set V of vertices of the multithreaded computation dag G. Each procedure execution is a linear chain of threads, each of which is connected to its successor in the chain by a continuation edge. When a thread u spawns a thread v, the dag contains a spawn edge (u, v) ∈ E, as well as a continuation edge from u to u’s successor in the procedure. When a thread u returns, the dag contains an edge (u, v), where v is the thread that immediately follows the next sync in the parent procedure. Every computation starts with a single initial thread and (assuming that the computation terminates), ends with a single final thread. Since the procedures are organized in a tree hierarchy, we can view the computation as a dag of threads embedded in the tree of procedures. 1.2 Performance Measures Two performance measures suffice to gauge the theoretical efficiency of multithreaded algorithms. We define the work of a multithreaded computation to be the total time to execute all the operations in the computation on one processor. We define the critical-path length of a computation to be the longest time to execute the threads along any path of dependencies in the dag. Consider, for4Handout 29: Dynamic Multithreaded Algorithms000000000011111111110000000000000000001111111111111111110000000000001111111111110000000000111111111100000000000000011111111111111100000000000000011111111111111100000000000000011111111111111100000000011111111100000000000000000000111111111111111111110000000000000001111111111111110000000001111111110000000000000000000011111111111111111111000000000000000111111111111111000000000000111111111111000000000000000000111111111111111111000000000000000000111111111111111111000000000000111111111111fib(3)fib(2)fib(1)fib(1)fib(2)fib(1) fib(0)fib(0)fib(4)Figure 1: A dag representing the multithreaded computation of FIB(4). Threads are shown as circles, andeach group of threads belonging to the same procedure are surrounded by a rounded rectangle. Downwardedges are spawns dependencies, horizontal edges represent continuation dependencies within a procedure,and upward edges are return dependencies.example, the computation in Figure 1. Suppose that every thread can be executed in unit time.Then,