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

In this paper we present substantially improved thread partitioning algorithmsfor modern implicitly parallel languages. We present a new block partitioningalgorithm, separation constraint partitioning, which is both more powerful andmore flexible than previous algorithms. Our algorithm is guaranteed to derivemaximal threads. We present a theoretical framework for proving thecorrectness of our partitioning approach, and we show how separation constraintpartitioning makes interprocedural partitioning viable.We have implemented the partitioning algorithms in an Id90 compiler forworkstations and parallel machines. Using this experimental platform, wequantify the effectiveness of different partitioning schemes on wholeapplications.