Zhu, K.K.ZhuWu, G.-M.G.-M.WuWong, D.F.D.F.WongWong, C.K.C.K.WongYAO-WEN CHANG2018-09-102018-09-10200310844309http://www.scopus.com/inward/record.url?eid=2-s2.0-0037222671&partnerID=MN8TOARShttp://scholars.lib.ntu.edu.tw/handle/123456789/303299Switch 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.application/pdfapplication/pdfComputer-aided design of VLSI; FPGA; FPIC; Layout; SynthesisAlgorithms; Combinatorial circuits; Computer aided design; Switches; VLSI circuits; Flow analyzers; Field programmable gate arraysjournal article10.1145/606603.6066052-s2.0-0037222671WOS:000180959600002