Safe In-Place Updates for ILP Fusion in Array Languages

Abstract

Accelerate is a combinator based, parallel array programming language embedded in Haskell capable of targeting the CPU and GPU. To eliminate the overhead of intermediate arrays, Accelerate uses a fusion step to combine combinators into larger, more efficient computation clusters. This fusion step is implemented as an ILP that solves for the most efficient clustering of combinators for a given cost function. Another optimization is in-place (or destructive) updates. When an in-place update happens, the output of a computation is written to one of its input arrays, destroying the input in the process. The order of computations, which is determined by fusion, is therefor highly important when applying in-place updates. This thesis explores how in-place updates can be integrated into Accelerate’s existing fusion ILP. The resulting ILP is implemented in Accelerate and benchmarked. It turns out that in-place update have a particularly high impact on programs with little possibility for fusion and/or many sparse scatter-like operations. In case of the former they reduce memory usage by running (parts of) programs fully in-place. In the latter case, in-place updates eliminate the need to make a copy of the destination array, reducing runtime by up to 5×.