Separation Constraint Partitioning - A New Algorithm for Partitioning Non-strict Programs into Sequential Threads

In this paper we present substantially improved thread partitioning algorithms for modern implicitly parallel languages. We present a new block partitioning algorithm, separation constraint partitioning, which is both more powerful and more flexible than previous algorithms. Our algorithm is guaranteed to derive maximal threads. We present a theoretical framework for proving the correctness of our partitioning approach, and we show how separation constraint partitioning makes interprocedural partitioning viable. We have implemented the partitioning algorithms in an Id90 compiler for workstations and parallel machines. Using this experimental platform, we quantify the effectiveness of different partitioning schemes on whole applications. 1 Introduction Modern implicitly parallel languages, such as the functional language Id90, allow the elegant formulation of a broad class of problems while exposing substantial parallelism. However, their non-strict semantics require fine-grain dynami..