Analysis of FPGA/FPIC switch modules
Resource
ACM Transactions on Design Automation of Electronic Systems 8 (1): 11-37
Journal
ACM Transactions on Design Automation of Electronic Systems
Journal Volume
8
Journal Issue
1
Pages
11-37
Date Issued
2003
Author(s)
Abstract
Switch modules are the most important component of the routing resources in FPGAs/FPICs. Previous works have shown that switch modules with higher routability result in better area performance for practical applications. We consider in this paper an FPGA/FPIC switch-module analysis problem: the inputs consist of a switch-module description and the number of nets required to be routed through the switch module; the question is to determine if there exists a feasible routing for the routing requirements on the switch module. As a fundamental problem for the analysis of switch modules, this problem is applicable to the design and routability evaluation of FPGA/FPIC switch modules and FPGA/FPIC routing. We present a network-flow-based approximation algorithm for this problem. Based on mathematical analyses, we show that this algorithm has provably good performance with the bounds 5 and 5/4 away from the optima for two types of switch modules, respectively. Extensive experiments show that this algorithm is highly accurate and runs very efficiently.
Subjects
Computer-aided design of VLSI; FPGA; FPIC; Layout; Synthesis
Other Subjects
Algorithms; Combinatorial circuits; Computer aided design; Switches; VLSI circuits; Flow analyzers; Field programmable gate arrays
Type
journal article