Validation of parallelizing transformations of sequential programs. (23rd January 2017)

• Record Type: Journal Article
• Authors: Dutta, Sudakshina
• Is Part Of: Concurrency and computation. Volume 29:Number 8(2017)
• Page Start: n/a
• Page End: n/a
• Publication Date: 2017-01-23
• Subjects: conflict access -- dependence graphs -- loop parallelization -- loop vectorization -- validation; Parallel processing (Electronic computers) -- Periodicals; Parallel computers -- Periodicals; 004.35
• DOI: 10.1002/cpe.3958
• Languages: English
• ISSNs: 1532-0626

Abstract

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.