YAO-WEN CHANGLin, Jai-MingJai-MingLinWong, M. D. F.M. D. F.Wong2009-02-252018-07-062009-02-252018-07-06200102780070http://www.scopus.com/inward/record.url?eid=2-s2.0-0035369721&partnerID=MN8TOARShttp://scholars.lib.ntu.edu.tw/handle/123456789/293583http://ntur.lib.ntu.edu.tw/bitstream/246246/141362/1/07.pdfProcess technology advances have made multimillion gate field programmable gate arrays (FPGAs) a reality. A key issue that needs to be solved in order for the large-scale FPGAs to realize their full potential lies in the design of their segmentation architectures. Channel segmentation designs have been studied to some degree in much of the literature; the previous methods are based on experimental studies, stochastic models, or analytical analysis. In this paper, we address a new direction for studying segmentation architectures. Our method is based on graph-theoretic formulation. We first formulate a problem of finding the optimal segmentation architecture for two input routing instances and present a polynomial-time optimal algorithm to solve the problem. Based on the solution to the problem, we develop an effective and efficient multilevel matching-based algorithm for general channel segmentation designs. Experimental results show that our method significantly outperforms the previous work. For example, our method achieves average improvements of 18.2% and 8.9% in routability in comparison with other work.application/pdf294264 bytesapplication/pdfen-USDetailed routing; Interconnect; Layout; Physical design; RoutingAlgorithms; Computer simulation; Graph theory; Interconnection networks; Logic design; Polynomials; Random processes; Theorem proving; Channel segmentation design; Graph theoretic formula; Matching based algorithm; Multilevel matching based algorithm; Polynomial time optimal algorithm; Field programmable gate arraysjournal article10.1109/43.9248312-s2.0-0035369721WOS:000168866600008http://ntur.lib.ntu.edu.tw/bitstream/246246/141362/1/07.pdf