Validation of Loop Parallelization and Loop Vectorization Transformations

Sudakshina Dutta, Dipankar Sarkar, Arvind Rawat, Kulwant Singh

2016

Abstract

Loop parallelization and loop vectorization of array-intensive programs are two common transformations applied by parallelizing compilers to convert a sequential program into a parallel program. Validation of such transformations carried out by untrusted compilers are extremely useful. This paper proposes a novel algorithm for construction of the dependence graph of the generated parallel programs. The transformations are then validated by checking equivalence of the dependence graphs of the original sequential program and the parallel program using a standard and fairly general algorithm reported elsewhere in the literature. The above equivalence checker still works even when the above parallelizing transformations are preceded by various enabling transformations except for loop collapsing which changes the dimensions of the arrays. To address the issue, the present work expands the scope of the checker to handle this special case by informing it of the correspondence between the index spaces of the corresponding arrays in the sequential and the parallel programs. The augmented algorithm is able to validate a large class of static affine programs. The proposed methods are implemented and tested against a set of available benchmark programs which are parallelized by the polyhedral auto-parallelizer LooPo and the auto-vectorizer Scout. During experiments, a bug of the compiler LooPo on loop parallelization has been detected.

Paper Citation

in Harvard Style

Dutta S., Sarkar D., Rawat A. and Singh K. (2016). Validation of Loop Parallelization and Loop Vectorization Transformations . In Proceedings of the 11th International Conference on Evaluation of Novel Software Approaches to Software Engineering - Volume 1: ENASE, ISBN 978-989-758-189-2, pages 195-202. DOI: 10.5220/0005869501950202

in Bibtex Style

@conference{enase16,
author={Sudakshina Dutta and Dipankar Sarkar and Arvind Rawat and Kulwant Singh},
title={Validation of Loop Parallelization and Loop Vectorization Transformations},
booktitle={Proceedings of the 11th International Conference on Evaluation of Novel Software Approaches to Software Engineering - Volume 1: ENASE,},
year={2016},
pages={195-202},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0005869501950202},
isbn={978-989-758-189-2},
}

in EndNote Style

TY - CONF
JO - Proceedings of the 11th International Conference on Evaluation of Novel Software Approaches to Software Engineering - Volume 1: ENASE,
TI - Validation of Loop Parallelization and Loop Vectorization Transformations
SN - 978-989-758-189-2
AU - Dutta S.
AU - Sarkar D.
AU - Rawat A.
AU - Singh K.
PY - 2016
SP - 195
EP - 202
DO - 10.5220/0005869501950202