Program optimization and parallelization using idioms

Abstract

Programs in languages such as FORTRAN, Pascal, and C, were designed and written for a sequential machine model. Several methods to vectorize such programs and recover other forms of parallelism that apply to more advanced machine architectures have been developed during the last decade. We propose and demonstrate a more powerful translation technique for making such programs run efficiently on parallel machines which offer facilities such as parallel prefix operations as well as parallel and vector capabilities. This technique, which is global in nature and involves a modification of the traditional definition of the program dependence graph (PDG), is based on the extraction of parallelizable pro-grain structures ("idioms") from the given (sequential) program. The benefits of our technique extend beyond the abovementioned architectures, and can be viewed as a general program optimization iriethod, applicable in many other situations. We show a few examples in which our method indeed outperforms existing analysis techniques.