Lin, Jai-MingJai-MingLinWong, D. F.D. F.WongYAO-WEN CHANG2020-06-162020-06-16199810923152https://scholars.lib.ntu.edu.tw/handle/123456789/502001https://www.scopus.com/inward/record.uri?eid=2-s2.0-0032312298&doi=10.1145%2f288548.288557&partnerID=40&md5=2996bb1e042fd4c6e2660726bdd9707fProcess technology advances will soon make the one-million gate FPGA a reality. A key issue that needs to be solved for the large-scale FPGAs to realize their full potential lies in the design of their segmentation architectures. One-dimensional segmentation designs have been studied to some degree in much of the literature; most of the previously proposed methods are based on stochastic 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 net matching problem and present a polynomial-time optimal algorithm to solve the problem. Based on the solution to the problem, we develop an effective and efficient matching-based algorithm for FPGA segmentation designs. Experimental results show that our method significantly outperforms previous work. For example, our method achieves averages of 18.2% and 8.9% improvements in routability, compared with the work in [14] and the most recent work in [7], respectively. More importantly, our approaches are very flexible and can readily extend to higher-order segmentation designs (e.g., two- or three-dimensional segmentation design, etc), which are crucial to the design of large-scale FPGAs.Algorithms; Computer aided logic design; Graph theory; Polynomials; Graph matching-based algorithms; Higher-order segmentation design; Field programmable gate arraysconference paper10.1145/288548.2885572-s2.0-0032312298https://doi.org/10.1145/288548.288557