Boosting irregular array Reductions through In-lined Block-ordering on fast processors
Boosting irregular array Reductions through In-lined Block-ordering on fast processors. In Proceedings of HPEC 2015. IEEE High Performance Extreme Computing Conference. (pp. 1-6). Waltham, MA USA.
Array-type reductions represent a frequently occurring algorithmic pattern in many scientific applications. A special case occurs if array elements are accessed in an irregular, often random manner, making their concurrent and scalable execution difficult. In this work we present a new approach that consists of language and runtime support and targets popular parallel programming models such as OpenMP. Its runtime support implements Privatization with In-lined, Block-Ordered Reductions (PIBOR), a new approach that trades processor cycles to increase locality and bandwidth efficiency for such algorithms. A reference implementation in OmpSs, a task-parallel programming model, shows promising results on current multicore systems.