Custom Multi-Cache Architectures for Heap Manipulating Programs

Abstract

Memory-intensive implementations often require access to an external, off-chip memory which can substantially slow down an FPGA accelerator due to memory bandwidth limitations. Buffering frequently reused data on chip is a common approach to address this problem and the optimization of the cache architecture introduces yet another complex design space. This paper presents a high-level synthesis (HLS) design aid that automatically generates parallel multi-cache systems which are tailored to the specific requirements of the application. Our program analysis identifies non-overlapping memory regions, supported by private caches, and regions which are shared by parallel units after parallelization, which are supported by coherent caches and synchronization primitives. It also decides whether the parallelization is legal with respect to data dependencies. The novelty of this work is the focus on programs using dynamically allocated, pointer-based data structures which, while common in software engineering, remain difficult to analyze and are beyond the scope of the overwhelming majority of HLS techniques to date. Secondly, we devise a high-level cache performance estimation to find a heterogeneous configuration of cache sizes that maximizes the performance of the multi-cache system subject to an on-chip memory resource constraint. We demonstrate our technique with three case studies of applications using dynamic data structures and use Xilinx Vivado HLS as an exemplary HLS tool. We show up to 15× speed-up after parallelization of the HLS implementations and the insertion of the application-specific distributed hybrid multi-cache architecture.