Graph-theoretic sufficient condition for FPGA/FPIC switch-module routability

Yao Wen Chang, D. F. Wong, C. K. Wong

Research output: Contribution to journalConference articlepeer-review

Abstract

Switch modules are the most important component of the routing resources in FPGA's/FPIC's. 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. This problem is applicable to the routability evaluation of FPGA/FPIC switch modules, the switch-module design for FPGA's/FPIC's, and FPGA/FPIC routing. We present a graph-theoretic sufficient condition for the analysis problem. The implications of the condition are: (1) there exist several classes of efficient approximation algorithms for the analysis problem; (2) there exist several classes of switch-module architectures on which the analysis problem can be solved efficiently.

Original languageEnglish (US)
Pages (from-to)1572-1575
Number of pages4
JournalProceedings - IEEE International Symposium on Circuits and Systems
Volume3
StatePublished - 1997
Externally publishedYes
EventProceedings of the 1997 IEEE International Symposium on Circuits and Systems, ISCAS'97. Part 4 (of 4) - Hong Kong, Hong Kong
Duration: Jun 9 1997Jun 12 1997

ASJC Scopus subject areas

  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'Graph-theoretic sufficient condition for FPGA/FPIC switch-module routability'. Together they form a unique fingerprint.

Cite this