The authors present a new translation technique for automatic parallelization based on recognition of “idioms” (standard constructs such as reductions and scans). Their technique consists of transforming all loops into a normal form, generating computation graphs (CGs), and detecting idioms based on patterns in the CGs. 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. An extensive bibliography points to excellent texts and papers on compiler optimization and parallelization techniques. Both compiler writers and theorists will find this paper useful.