Publications Details

Compile-time partitioning of a non-strict language with side-effects into sequential threads

Hoch, J.E.; Davenport, D.M.; Grafe, V.G.; Steele, K.M.

This paper presents a practical algorithm for partitioning a program into sequential threads. A thread is a sequence of instructions, possibly including branches, which can be scheduled as an indivisible unit on a von Neumann-like processor. The partitioning algorithm is designed for a non-strict (but not lazy) language with non-strict data structures and side-effects. The primary target of the proposed compilation strategy is large-scale parallel systems which rely on multithreading at the processor level to tolerate long communication latencies. As such, the algorithm incorporates a mechanism to balance the desire to maximize thread length with the desire to expose useful high-level parallelism. Although this paper focuses on non-strict semantics in conjunction with a parallel multithreaded architecture, the partitioning analysis is equally well suited (with appropriate simplifications) to a non-strict language on a sequential machine or a strict language on a parallel multithreaded machine. Our analysis is accomplished without compromising non-strict semantics and without creating dependencies which sacrifice useful high-level parallelism. It can also exploit known dependency information. The analysis starts with a traditional dataflow graph and partitions it into a set of interrelated threads. 16 refs., 9 figs.