Analysis of FPGA/FPIC switch modules

Yao Wen Chang, Kai Zhu, Guang Ming Wu, D. F. Wong, C. K. Wong

Research output: Contribution to journalJournal articlepeer-review

2 Citations (Scopus)


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.

Original languageEnglish
Pages (from-to)11-37
Number of pages27
JournalACM Transactions on Design Automation of Electronic Systems
Issue number1
Publication statusPublished - Jan 2003

Scopus Subject Areas

  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering

User-Defined Keywords

  • Computer-aided design of VLSI
  • FPGA
  • FPIC
  • Layout
  • Synthesis


Dive into the research topics of 'Analysis of FPGA/FPIC switch modules'. Together they form a unique fingerprint.

Cite this