High-level synthesis makes heavy use of compile-time memory allocation to generate communication channels. However, state-of-theart allocation algorithms drastically lack of scalability and cannot be used directly. In this thesis, we investigate how to rephrase such algorithms to improve their scalability and make them applicable in this new context. We show how trace analysis might be exploited to reproduce either the same result or an approximation.

In our first contribution, we show how to reproduce in quick fashion the results of the successive maxima algorithm by analyzing a single particular execution trace. We introduce the notion of localizability to characterize the subset of programs for which our method can be soundly applied. In addition to correctness proofs, experimental results shows that our method allows to quickly allocate the channels from kernels of the Polybench suite. In our second contribution, we address the scaling of linear allocation, a more general approach to memory allocation which makes possible to further reduce the memory footprint.

We show how to extrapolate the liveness analysis for arrays, the costly step in terms of analysis time, from several execution traces by using a widening operator. We prove that this extrapolation is possible when liveness constraints are totally unimodular and we show how this translates to program-level constraints. As for localizability, these constraints are general enough to fit most Polybench kernels. The experimental results show a significant improvement of the allocation time.

This research led to the implementation of a prototype tool named PoLa that totals around 4000 lines of C++ code.