A Runtime FPGA Placement and Routing Using Low-Complexity Graph Traversal

作者：Ferreira Ricardo^*; Rocha Luciana; Santos Andre G; Nacif Jose A M; Wong Stephan; Carro Luigi

来源：ACM Transactions on Reconfigurable Technology and Systems, 2015, 8(2): 9.

DOI：10.1145/2660775

• Design
• Algorithms
• Performance
• FPGA
• Place and route
• Run-time reconfiguration
• Graph traversal

Dynamic Partial Reconfiguration (DPaR) enables efficient allocation of logic resources by adding new functionalities or by sharing and/or multiplexing resources over time. Placement and routing (P&R) is one of the most time-consuming steps in the DPaR flow. P&R are two independent NP-complete problems, and, even for medium size circuits, traditional P&R algorithms are not capable of placing and routing hardware modules at runtime. We propose a novel runtime P&R algorithm for Field-Programmable Gate Array (FPGA)-based designs. Our algorithm models the FPGA as an implicit graph with a direct correspondence to the target FPGA. The P&R is performed as a graph mapping problem by exploring the node locality during a depth-first traversal. We perform the P&R using a greedy heuristic that executes in polynomial time. Unlike state-of-the-art algorithms, our approach does not try similar solutions, thus allowing the P&R to execute in milliseconds. Our algorithm is also suitable for P&R in fragmented regions. We generate results for a manufacturer-independent virtual FPGA. Compared with the most popular P&R tool running the same benchmark suite, our algorithm is up to three orders of magnitude faster.

• 出版日期2015-4