Title :
Matching-based algorithm for FPGA channel segmentation design
Author :
Chang, Yao-Wen ; Lin, Jai-Ming ; Wong, M.D.F.
Author_Institution :
Inst. of Comput. & Inf. Sci., Nat. Chiao Tung Univ., Hsinchu, Taiwan
fDate :
6/1/2001 12:00:00 AM
Abstract :
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 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 multi-level 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
Keywords :
field programmable gate arrays; graph theory; integrated circuit interconnections; logic CAD; network routing; FPGA channel segmentation design; graph-theoretic formulation; input routing; matching-based algorithm; multi-level matching-based algorithm; multimillion gate field programmable gate arrays; polynomial-time optimal algorithm; routability; segmentation architectures; stochastic models; Algorithm design and analysis; Application specific integrated circuits; Delay; Field programmable gate arrays; Large-scale systems; Logic programming; Routing; Stochastic processes; Switches; Wire;
Journal_Title :
Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on