A unified semantic approach for the vectorization and parallelization of generalized reductions

Abstract

Generalized reductions include some of the most well known programming idioms, for instance loop invariant variables, induction variables and reduction operations. We propose a unified framework that allows the detection of these paradigms and thus the efficient parallel implementation of programs that use these otherwise parallel-inhibiting constructs. Moreover, using a semantic-based symbolic evaluator, this technique is able to detect parallelizable constructs inside standard benchmarks that no other vectorizer or parallelizer can currently handle. An interesting by-product of our approach is that correctness proofs can be based on the sound and powerful abstract interpretation theory. This method has been implemented in the Velour vectorizer under current development at the Bull Research Center.