|
Process 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 theirfull potential lies in the design of their segmentation architectures [10].One-dimensional segmentation designs have been studied to some degree in much ofthe literature, most of the previously proposed methods are based on Stochasticor analytical analysis. In this thesis, we address a new direction for studyingsegmentation architectures. Our method is based on graph-theoretic formulation.We first formulate a net matching problem and present a polynomial- timealgorithm to solve the problem. Based on the solution to the problem, we developan effective and efficient matching based algorithm for FPGA segmentation designs. Experimental results show that our method significantly outperforms the previous work. For example, our method achieves averages of 18.0% and 8.9% improvements in routability, compared with the work in [14] and the most recentwork in [7], respectively. More importantly, our approaches are very flexibleand can readily extend to high- order segmentation designs (eg., two- or three-dimensional segmentation design, etc), which is crucialto the design of large-scale FPGAs.
|