PROGRAM OPTIMIZATION AND PARALLELIZATION USING IDIOMS

Citation
Ss. Pinter et Ry. Pinter, PROGRAM OPTIMIZATION AND PARALLELIZATION USING IDIOMS, ACM transactions on programming languages and systems, 16(3), 1994, pp. 305-327
Citations number
36
Categorie Soggetti
Computer Sciences","Computer Science Software Graphycs Programming
ISSN journal
01640925
Volume
16
Issue
3
Year of publication
1994
Pages
305 - 327
Database
ISI
SICI code
0164-0925(1994)16:3<305:POAPUI>2.0.ZU;2-M
Abstract
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.