Paper Info
Title
Time-Division Multiplexing Based System-Level FPGA Routing for Logic Verification*
Abstract
Multi-FPGA prototyping is widely used for modern VLSI verification, but the limited number of inter-FPGA connections in a multi-FPGA system may cause routing failures. As a result, the time-division multiplexing (TDM) technique is adopted to increase its resource utilization by transmitting multiple signals through the same routing channel. Due to the large signal delay between FPGA pairs, however, the performance of such a system greatly depends on the inter-FPGA routing quality. In this paper, we propose a TDM-based system-level routing algorithm to simultaneously minimize the maximum TDM (signal multiplexing) ratio and runtime, considering the crucial ratio constraints. By weighting the routing edges, we first model the net routing as a Steiner minimum tree (SMT) problem and solve it with an approximation algorithm with the performance bound 2(1 — 1/1), where l is the number of leaves in an optimal SMT. Then, a timing-driven assignment method is presented to evenly distribute the TDM ratio to routing signals, followed by a novel reassignment algorithm to efficiently handle unbalanced net groups. Finally, a ratio-aware refinement technique is employed to further improve the solution quality. Compared with the top-3 winners at the 2019 CAD Contest at ICCAD based on the contest benchmarks, experiment results show that our proposed algorithm achieves the best runtime and TDM ratio while satisfying all TDM constraints.
Year
DOI
Venue
2020
10.1109/DAC18072.2020.9218569
2020 57th ACM/IEEE Design Automation Conference (DAC)
Keywords
DocType
ISSN
• Hardware → Electronic design automation,Physical Design,Logic Verification,Multi-FPGA,Steiner Minimum Tree
Conference
0738-100X
ISBN
Citations 
PageRank 
978-1-7281-1085-1
0
0.34
References 
Authors
0
7
Name
Order
Citations
PageRank
Peng Zou101.01
Zhifeng Lin2106.30
Shi Xiao395.97
Yingjie Wu44012.68
Jianli Chen563.86
Jun Yu62315.94
Yao-Wen Chang73437253.54