Theory and algorithm for generalized memory partitioning in high-level synthesis

The signicant development of high-level synthesis tools has greatly facilitated FPGAs as general computing platforms. During the parallelism optimization for the data path, mem-ory becomes a crucial bottleneck that impedes performance enhancement. Simultaneous data access is highly restricted by the data mapping strategy and memory port constraint. Memory partitioning can eciently map data elements in the same logical array onto multiple physical banks so that the accesses to the array are parallelized. Previous meth-ods for memory partitioning mainly focused on cyclic parti-tioning for single-port memory. In this work we propose a generalized memory-partitioning framework to provide high data throughput of on-chip memories. We generalize cyclic partitioning into block-cyclic partitioning for a larger de-sign space exploration. We build the conict detection algo-rithm on polytope emptiness testing, and use integer points counting in polytopes for intra-bank oset generation. Mem-ory partitioning for multi-port memory is supported in this framework. Experimental results demonstrate that com-pared to the state-of-art partitioning algorithm, our pro-posed algorithm can reduce the number of block RAM by 19.58%, slice by 20.26% and DSP by 50%.EI