Run-time characterization of irregular accesses applied toparallelization of irregular reductions

摘要

Irregular reduction operations are the core of many largescientific and engineering applications. There are, in the literature,different methods to solve these operations in parallel. In this paperwe discuss a new technique which improves performance significantly,both in terms of execution time and memory overhead. These improvementsare achieved in the preprocessing as well as in the resulting parallelcode. Our proposal is based on the use of the Irregular Access RegionDescriptor (IARD). This data structure is a compact characterization ofindirectly accessed arrays that can be used for the efficientparallelization of a wide spectrum of irregular codes. In this paper wepresent its application to parallelize irregular reduction operations