Ss. Pinter et Ry. Pinter, PROGRAM OPTIMIZATION AND PARALLELIZATION USING IDIOMS, ACM transactions on programming languages and systems, 16(3), 1994, pp. 305-327
Programs in languages such as Fortran, Pascal, and C were designed and
written for a sequential machine model. During the last decade, sever
al methods to vectorize such programs and recover other forms of paral
lelism that apply to more advanced machine architectures have been dev
eloped (particularly for Fortran, due to its pointer-free semantics).
We propose and demonstrate a more powerful translation technique for m
aking such programs run efficiently on parallel machines which support
facilities such as parallel prefix operations as well as parallel and
vector capabilities. This technique, which is global in nature and in
volves a modification of the traditional definition of the program dep
endence graph (PDG), is based on the extraction of parallelizable prog
ram structures (''idioms'') from the given (sequential) program. The b
enefits of our technique extend beyond the above-mentioned architectur
es and can be viewed as a general program optimization method, applica
ble in many other situations. We show a few examples in which our meth
od indeed outperforms existing analysis techniques.