Efficient scheduling of strict multithreaded computations

In this paper we study the problem of efficiently scheduling a wide class of multithreaded computations, called strict; that is, computations in which all dependencies from a thread go to the thread's ancestors in the computation tree. Strict multithreaded computations allow the limited use of synchronization primitives. We present the first fully distributed scheduling algorithm which applies to any strict multithreaded computation. The algorithm is asynchronous, on-line, and follows the work-stealing paradigm. We prove that our algorithm is efficient not only in terms of its memory requirements and its execution time, but also in terms of its communication complexity. Our analysis applies to both shared and distributed memory machines. More specifically, the expected execution time of our algorithm is O(T-1/P + hT(infinity)), where T-1 is the minimum serial execution time, T-infinity is the minimum execution time with an infinite number of processors, P is the number of processors, and h is the maximum "distance" in the computation tree between any two threads that need to communicate. Furthermore, the total space required during the execution is O(S1P), where S-1 is the space required by a serial computer to execute the computation, while the expected communication cost incurred by our algorithm is O(PhTinfinity(1 + n(d)) S-max), where n(d) is the maximum number of dependencies entering any thread and S-max is the largest amount of storage needed for the execution of any specific thread of the computation. Our communication complexity bound is the first nontrivial bound ever proved for the model of strict parallel programming.