Static and Dynamic Memory Footprint Reduction for FPGA Routing Algorithms

This article presents techniques to reduce the static and dynamic memory requirements of routing algorithms that target field-programmable gate arrays. During routing, memory is required to store both architectural data and temporary routing data. The architectural data is static, and provides a representation of the physical routing resources and programmable connections on the device. We show that by taking advantage of the regularity in FPGAs, we can reduce the amount of information that must be explicitly represented, leading to significant memory savings. The temporary routing data is dynamic, and contains scoring parameters and traceback information for each routing resource in the FPGA. By studying the lifespan of the temporary routing data objects, we develop several memory management schemes to reduce this component. To make our proposals concrete, we applied them to the routing algorithm in VPR and empirically quantified the impact on runtime memory footprint, and place and route time.