Memory Footprint Reduction for FPGA Routing Algorithms

TitleMemory Footprint Reduction for FPGA Routing Algorithms
Publication TypeConference Paper
Year of Publication2007
AuthorsChin, S. Y. L., and S. J. E. Wilton
Conference NameField-Programmable Technology, 2007. ICFPT 2007. International Conference on
Pagination1 -8
Date Publisheddec.
KeywordsCAD tools, directed graph, field programmable gate arrays, FPGA routing algorithms, logic CAD, network routing, programmable connections, routing resource graph, run-time memory footprint reduction, storage requirement, tile-based nature, VPR tool

In this paper, we present a technique to reduce the run-time memory footprint of FPGA routing algorithms. These algorithms require a representation of the physical routing resources and programmable connections on the device; this representation dominates the storage requirements of FPGA routers. We show that by taking advantage of the tile-based nature of FPGAs, we can reduce the amount of information that must be explicitly represented, leading to significant memory savings. To make our proposal concrete, we applied it to the routing algorithm in VPR and quantified the impact on run-time memory footprint, and place and route compile-time. We found that a memory reduction of 5X to 13X could be achieved at a routing runtime penalty of 2.26X and an overall place-and-route runtime penalty of 1.28X.


a place of mind, The University of British Columbia

Electrical and Computer Engineering
2332 Main Mall
Vancouver, BC Canada V6T 1Z4
Tel +1.604.822.2872
Fax +1.604.822.5949

Emergency Procedures | Accessibility | Contact UBC | © Copyright 2021 The University of British Columbia