現場可程式化邏輯閘陣列導線段之設計

Abstract

由於製程技術的不斷改進，百萬邏輯閘的可程式化閘陣列 (FPGA)即 將問世。然而，在達成此一目標之前，我們必須先解決導線段結構設計的 問題[10]。我的論文目的就是希望能夠在有限面積的前提下設計出一個具 有高可繞度的導線段結構。目前已經有多項文獻從事一維導線段結構的研 究[7, 9, 14]，其方法大致可歸納成統計 (stochastic) 和解析 (analytical)的方法。本論文提出一個新的研究方向--組合式( combinatorial)法。根據此方法，導線段結構的問題可被轉化成圖形匹配 的問題 (graph matching)。首先，我們定義一個net matching的問題， 並且利用weighted bipartite matching 的演算法在polynomial時間內來 找出此問題的最佳解，而此最佳解可被當成子程式來處理整個導線結構設 計的問題。對於一維導線段的設計，根據的實驗的結果顯示，我們的方法 與[2]比較平均能夠提高約18.0%的繞線成功率，與目前最佳的結果[4]比 較，本法可以提高8.9%的繞線成功率。更重要的是，我們的組合式方法還 具有高延展性，所以此法可以輕易地延伸到高維的導線段設計。此為解決 高複雜的FPGA導線段結構設計所須具備的重要性質。 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.