We propose and demonstrate a more powerful translation technique for making such programs run efficiently on parallel machines which support facilities such as parallel prefix operations as well as parallel and vector capabilities. The benefits of our technique extend beyond the above-mentioned architectures and can be viewed as a general program optimization method, applicable in many other situations. We show a few examples in which our method indeed outperforms existing analysis techniques. A loop is defined to be in normal form if each dependence is between two consecutive iterations.
Normal form is achieved by loop unrolling.
The CG for a loop consists of initial, middle, and final portions that accurately represent the dependence patterns of the loop. Idiom detection is performed using graph rewriting rules. The authors illustrate the power of their technique with several examples and compare their success with other parallelization techniques. This paper is important because of its novel technique, which achieves greater parallelization than previous techniques. It is well written and of moderate length, and it describes the algorithms adequately.