Fusion of parallel array operations

TY - GEN

T1 - Fusion of parallel array operations

AU - Kristensen, Mads Ruben Burgdorff

AU - Lund, Simon Andreas Frimann

AU - Blum, Troels

AU - Avery, James Emil

N1 - Conference code: 25

PY - 2016

Y1 - 2016

N2 - We address the problem of fusing array operations based on criteria such as shape compatibility, data reuse, and minimizing for data reuse, the fusion problem has been formulated as a static weighted graph partitioning problem (known as the Weighted Loop Fusion problem). We show that this scheme cannot accurately track data reuse between multiple independent loops, since it overestimates total data reuse of certain cases. Our formulation in terms of partitions allows use of realistic cost functions that can track resource usage accurately. We give correctness proofs, and prove that WSP can maximize data reuse in programs exactly, in contrast to prior work. For the exact optimal solution, which is NP-hard to find, we present a branch-and-bound algorithm together with a polynomial-time preconditioner that reduces the problem size significantly in practice. We further present a polynomial-time greedy approximation that is fast enough to use for JIT-compilation and gives near-optimal results in practice. All algorithms have been implemented in the automatic parallelization platform Bohrium, run on a set of benchmarks, and compared to existing methods from the literature.

AB - We address the problem of fusing array operations based on criteria such as shape compatibility, data reuse, and minimizing for data reuse, the fusion problem has been formulated as a static weighted graph partitioning problem (known as the Weighted Loop Fusion problem). We show that this scheme cannot accurately track data reuse between multiple independent loops, since it overestimates total data reuse of certain cases. Our formulation in terms of partitions allows use of realistic cost functions that can track resource usage accurately. We give correctness proofs, and prove that WSP can maximize data reuse in programs exactly, in contrast to prior work. For the exact optimal solution, which is NP-hard to find, we present a branch-and-bound algorithm together with a polynomial-time preconditioner that reduces the problem size significantly in practice. We further present a polynomial-time greedy approximation that is fast enough to use for JIT-compilation and gives near-optimal results in practice. All algorithms have been implemented in the automatic parallelization platform Bohrium, run on a set of benchmarks, and compared to existing methods from the literature.

U2 - 10.1145/2967938.2967945

DO - 10.1145/2967938.2967945

M3 - Article in proceedings

SN - 978-1-4503-4121-9

SP - 71

EP - 85

BT - PACT' 16

PB - Association for Computing Machinery

T2 - The 25th International Conference on Parallel Architectures and Compilation Techniques

Y2 - 11 September 2016 through 15 September 2016

ER -