Author retrospective for adaptive reduction parallelization techniques

Abstract

Modern applications are dynamic and input dependent and algorithm performance is input and environment sensitive. This potential mismatch between algorithmic choice and performance is exacerbated in the case of parallel programs because the penalty for less than optimal locality grows with the size of the machine. Reductions, e.g., map-reduce are one of the most important algorithms used in parallel codes are also input sensitive. This led us to develop an adaptive framework that used a statistical method to learn how to select the best algorithm for every execution instance. We applied it to parallel reduction algorithm selection. The importance of better reduction methods as well as adaptive selection methods has only increased since the time this paper was first published. Copyright