Abstract
在這篇論文中，我們針對可程式閘陣列積體電路 (Field Programmable Gate Arrays, FPGAs)的設計提出一個有效率的繞線方法。近年來，FPGA 廣泛地被應用在電路原型的製造上。而這種 IC 的繞線問題和傳統的半定 製式 IC 的繞線問題有非常大的差異，FPGA 的繞線資源(Interconnect Resources)是由一堆製造好的分段導線(Wiring Segment)和可程式開關( Programmable Switch)所組成，藉由規劃開關的狀態以形成不同之連接。 由於這種較受限制的繞線方式，引發我們靈感：把繞線資源視為一個大圖 形 (Graph)，直接在圖形上尋找解答。我們使用圖形來表示繞線資源，圖 中的每一個頂點代表一段導線或者一可規劃邏輯元件(Configurable Logic Block, CLB)的接腳，而每一個邊代表一個可程式開關。根據這種 表示法，FPGA繞線問題即能轉化成圖形上的問題：為每一條信號線找一棵 包含所連端點的樹，而所有的樹彼此不能有相交以確保符合電氣特性。另 外有一點要注意，如果未被使用的 CLB 接腳不能當作中間節點使用，則 需要將所對應的端點和所連的邊從圖形中除去。我們使用修改過的 Lee 氏演算法來繞各個信號線，它並沒有絕對防止不同信號線在繞線資源使用 上的衝突，而是給與有衝突的路徑一個比較高的付費。所產生的衝突是用 拔掉並重繞(Rip-up and Reroute) 的方法解決，我們採用模擬進化 (Simulated Evolution)的隨機法來選擇需被重繞的信號線，以期能有效 地逐漸解決所有的衝突而得到一可行解。我們所實作的程式命名為 TRACER-fpga，實驗結果相當不錯，和另一個名叫CGE 的繞線器相比較， TRACER-fpga 完成繞線所需之最小繞線通道寬度(軌數，Number of Tracks) 比 CGE 減少了２８％。能有這種成果的主要因素是我們不需將 繞線問題分成整體繞線(Global Routing)和詳細繞線(Detailed Routing) 兩個子問題。 In this thesis, we propose an efficient routing method for the design of RAM-based FPGAs. We model the interconnect resources as a graph, where each vertex represents either a CLB pin or a wiring segment, and each edge a programmable switch. Wiring segments can be of variable length. A routing solution is represented as a set of disjointed trees, each connects all terminals of a net, on the graph. A maze router is used to connect nets. Initially, nets are connected independently. Conflicts over the usage of interconnect resources among nets are resolved iteratively by a rip-up and rerouter, which is guided by a simulated evolution based optimization technique. The iteration terminates when all conflicts are resolved. The proposed approach has been implemented in a program called TRACER-fpga. As compared with CGE, a well-known program targeted towards the same problem, TRACER-fpga on the average required 28% less number of tracks to complete the routing given the same placement for two suits of benchmark circuits.