Report ID
1995-01
Report Authors
Klaus E. Schauser, David E. Culler, and Seth C. Goldstein
Report Date
Abstract
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.
Document
1995-01.ps644.73 KB