Optimal Fusion in Data-Parallel Languages: From Diagonal Fusion to Code Generation

Abstract

This thesis investigates the necessary steps to introduce optimal fusion into a compiler for a dataparallel, array based language. Existing literature includes various practical fusion methods, which are based on local rewrites and do not consider the global optimal solution, and methods that are able to identify the optimal fusion clustering. There are no methods that use this optimal clustering to achieve optimally fused code, whilst preserving parallelism and type-safety. In this thesis, we expand upon the latter methods and ensure that the resulting fusion system preserves parallelism and type-safety. The proposed method consists of an integer linear programming formulation to identify the optimal clustering, an explicit fusion AST to encode this clustering in the abstract syntax tree, and an explicitly loopy intermediate representation to generate fused code. In the process of developing this system, we formalise the concepts of vertical and horizontal fusion, and introduce diagonal fusion. These concepts are used in the explicit fusion AST, and allow us to preserve type-safety throughout the compiler, amounting to a partial proof of correctness. We demonstrate that this approach is viable through a partial implementation in the compiler for Accelerate, an embedded language in Haskell.