Premium
Validation of parallelizing transformations of sequential programs
Author(s) -
Dutta Sudakshina
Publication year - 2017
Publication title -
concurrency and computation: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.309
H-Index - 67
eISSN - 1532-0634
pISSN - 1532-0626
DOI - 10.1002/cpe.3958
Subject(s) - computer science , parallel computing , compiler , equivalence (formal languages) , program transformation , transformation (genetics) , benchmark (surveying) , automatic parallelization , vectorization (mathematics) , loop unrolling , dependence analysis , set (abstract data type) , graph , locality , programming language , theoretical computer science , algorithm , linguistics , biochemistry , chemistry , geodesy , gene , geography , philosophy
Summary Transformations for high‐performance superscalar, vector, and parallel processors maximize parallelism and memory locality. Often parallelizing compilers apply transformations, such as loop parallelization and loop vectorization, to convert a sequential array‐handling program into a parallel program. Validation of such transformations is extremely useful in the prevalent high‐performance computing environment. This paper proposes a novel algorithm for construction of the dependence graph of the generated parallel programs. These transformations are validated by checking equivalence of the dependence graphs of the original sequential program and the transformed parallel program using a standard algorithm reported in the literature. The above equivalence checker works even when the above parallelizing transformations are preceded by various enabling transformations except for loop collapsing transformation that changes the dimensions of the arrays. In the present paper, the scope of the equivalence checker has been expanded to handle this special case by informing it of the correspondence between the index spaces of the corresponding of input and output arrays in the sequential and the parallel programs. The proposed methods are implemented and tested against a set of available benchmark programs that are parallelized by the polyhedral auto‐parallelizer LooPo and the auto‐vectorizer Scout.