DocumentCode :
1493794
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
Volume :
20
Issue :
6
fYear :
2001
fDate :
6/1/2001 12:00:00 AM
Firstpage :
784
Lastpage :
791
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;
fLanguage :
English
Journal_Title :
Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on
Publisher :
ieee
ISSN :
0278-0070
Type :
jour
DOI :
10.1109/43.924831
Filename :
924831
Link To Document :
بازگشت