Matching-based algorithm for FPGA channel segmentation design

Process 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 desi gn of their segmentation architectures. Channel segmentation designs have b een studied to some degree in much of the Literature; the previous methods are based on experimental studies, stochastic models, or analytical analysi s, In this paper, we address a new direction for studying segmentation arch itectures. Our method is based on graph-theoretic formulation. We first for mulate a problem of finding the optimal segmentation architecture for two i nput routing instances and present a polynomial-time optimal algorithm to s olve the problem. Based on the solution to the problem, we develop an effec tive and efficient multilevel matching-based algorithm for general channel segmentation designs. Experimental results show that our method significant ly outperforms the previous work. For example, our method achieves average improvements of 18.2% and 8.9% in routability in comparison with other work .