Séminaire LSL - Hugo Thievenaz - Scalable trace-based compile-time memory allocation

Abstract

This thesis, titled "Scalable trace-based compile-time memory allocation", studies the use of trace analysis to infer efficient memory allocations. The broader goal is to use program information at runtime as a way to outpace traditional static analysis techniques, which fail to scale for kernels of high dimensions and many statements. The use-case is polyhedral High-Level Synthesis where scalable methods are required.

We propose novel methods for array contraction based on lightweight, scalable, trace analysis. Then, we provide a thorough theoretical study of our algorithms as well as implementations to quantify performance in analysis time but also memory reduction. The example programs used for performance measurement were variations of the polyhedral benchmark suite "PolyBench". The variations are most often parallelism factor, tiling, and adjustment of padding. Key contributions of this thesis are the design of two new methods of analysis for the array contraction optimization. The first one focuses on yielding constant sizes for temporary arrays, which is relevant in the context of communication buffer sizing for High-Performance Computing applications. The second method is a more general approach to memory allocation which reconstructs the array liveness information and the conflict relation between array cells, as well as an algorithm to compute linear allocations able to produce parametric sizes for the arrays. This research lead to the implementation of a tool named PoLa that totals 5637 lines of C++ code.