Wong, D.F.D.F.WongWong, C.K.C.K.WongYAO-WEN CHANG2018-09-102018-09-10199702714310http://www.scopus.com/inward/record.url?eid=2-s2.0-0030719813&partnerID=MN8TOARShttp://scholars.lib.ntu.edu.tw/handle/123456789/332290Switch 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.Algorithms; Approximation theory; Electric network analysis; Graph theory; Integrated circuit layout; Logic gates; Microprocessor chips; Problem solving; Switching circuits; Switching networks; Field programmable gate arrays (FPGA); Field programmable interconnected chip (FPIC); Logic designconference paper2-s2.0-0030719813