A graph-theoretic sufficient condition for FPGA/FPIC switch-module routability

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

doi:10.1109/ISCAS.1997.621430

A graph-theoretic sufficient condition for FPGA/FPIC switch-module routability

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

Office of the Provost

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-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 language	English
Title of host publication	Proceedings - IEEE International Symposium on Circuits and Systems, ISCAS 1997
Publisher	IEEE
Pages	1572-1575
Number of pages	4
ISBN (Print)	078033583X
DOIs	https://doi.org/10.1109/ISCAS.1997.621430
Publication status	Published - Jun 1997
Event	1997 IEEE International Symposium on Circuits and Systems, ISCAS 1997 - , Hong Kong, China Duration: 9 Jun 1997 → 12 Jun 1997 https://ieeexplore.ieee.org/xpl/conhome/4816/proceeding

Publication series

Name	Proceedings - IEEE International Symposium on Circuits and Systems
Publisher	IEEE
ISSN (Print)	0271-4310

Conference

Conference	1997 IEEE International Symposium on Circuits and Systems, ISCAS 1997
Country/Territory	Hong Kong, China
Period	9/06/97 → 12/06/97
Internet address	https://ieeexplore.ieee.org/xpl/conhome/4816/proceeding

Access to Document

10.1109/ISCAS.1997.621430

Cite this

@inproceedings{365ba29971a341c78ef2421d86e24e74,

title = "A graph-theoretic sufficient condition for FPGA/FPIC switch-module routability",

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.",

author = "Chang, \{Yao Wen\} and Wong, \{D. F.\} and Wong, \{C. K.\}",

note = "Funding Information: This work was supported by the National Science Council of ROC under Grant No. NSC-86-2621-E-009-019-T.; 1997 IEEE International Symposium on Circuits and Systems, ISCAS 1997 ; Conference date: 09-06-1997 Through 12-06-1997",

year = "1997",

month = jun,

doi = "10.1109/ISCAS.1997.621430",

language = "English",

isbn = "078033583X",

series = "Proceedings - IEEE International Symposium on Circuits and Systems",

publisher = "IEEE",

pages = "1572--1575",

booktitle = "Proceedings - IEEE International Symposium on Circuits and Systems, ISCAS 1997",

address = "United States",

url = "https://ieeexplore.ieee.org/xpl/conhome/4816/proceeding",

}

Chang, YW, Wong, DF & Wong, CK 1997, A graph-theoretic sufficient condition for FPGA/FPIC switch-module routability. in Proceedings - IEEE International Symposium on Circuits and Systems, ISCAS 1997. Proceedings - IEEE International Symposium on Circuits and Systems, IEEE, pp. 1572-1575, 1997 IEEE International Symposium on Circuits and Systems, ISCAS 1997, Hong Kong, China, 9/06/97. https://doi.org/10.1109/ISCAS.1997.621430

A graph-theoretic sufficient condition for FPGA/FPIC switch-module routability. / Chang, Yao Wen; Wong, D. F.; Wong, C. K.
Proceedings - IEEE International Symposium on Circuits and Systems, ISCAS 1997. IEEE, 1997. p. 1572-1575 (Proceedings - IEEE International Symposium on Circuits and Systems).

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

TY - GEN

T1 - A graph-theoretic sufficient condition for FPGA/FPIC switch-module routability

AU - Chang, Yao Wen

AU - Wong, D. F.

AU - Wong, C. K.

N1 - Funding Information: This work was supported by the National Science Council of ROC under Grant No. NSC-86-2621-E-009-019-T.

PY - 1997/6

Y1 - 1997/6

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/0030719813

U2 - 10.1109/ISCAS.1997.621430

DO - 10.1109/ISCAS.1997.621430

M3 - Conference proceeding

AN - SCOPUS:0030719813

SN - 078033583X

T3 - Proceedings - IEEE International Symposium on Circuits and Systems

SP - 1572

EP - 1575

BT - Proceedings - IEEE International Symposium on Circuits and Systems, ISCAS 1997

PB - IEEE

T2 - 1997 IEEE International Symposium on Circuits and Systems, ISCAS 1997

Y2 - 9 June 1997 through 12 June 1997

ER -

A graph-theoretic sufficient condition for FPGA/FPIC switch-module routability

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this