Algorithms for Embedded Memory Binding in FPGAS

Abstract

Recent advancements in semiconductor fabrication technology have enabled field-programmable gate arrays (FPGAs) with hundreds of embedded memories. Usually, these embedded memories can be configured to work with different widths of address and data buses, In some FPGAs there is also a variety of different types of embedded memories with different capacities and configuration sets. As a consequence, it is becoming cumbersome to bind the data memory of an algorithm to these embedded memories manually. A computer-aided design tool that automates the process of binding embedded memories can save the engineering time for a design, as well as explore different alternatives to bind the data memory with the use of less embedded memories and less amount of peripheral hardware in terms of logic cells of the FPGA. In this thesis, we first motivate the need for an algorithmic solution to the memory binding problem in FPGAs and explain the design trade-offs. Then we present an exact solution for the problem using a branching method to search the solution space exhaustively. However, due to the large solution space and the plenitude of choices in each step of the algorithm, the runtime of the algorithm is far from being acceptable for realistic problems. To manage the runtime, we have developed a fast heuristic approach. Our experimental results show that the heuristic method can achieve a suboptimal solution, which for the small problem instances is shown to be close to the optimal in acceptable runtime. Moreover, when compared to manual solutions, besides substantially improving the implementation time, the heuristic can often enable a more efficient usage of the FPGA logic resources and embedded memories.