Abstract
在這篇論文中，我們針對現場可程式邏輯陣列(FPGA)的繞線問題提出一個 繞線演算法。這個方法的主要目的不僅僅是在減低繞線時所需的 Routing Track，而且還設法減低線路的路徑時間延遲(path delay)。最 近幾年來，FPGA已經成為ASIC原型 (prototyping)的一種低成本與低製造 時間的設計方法，由於 FPGA 有別於傳統的硬體架構，例如它有特殊的 Connection Box 與 Switch Matrix 的連接方式。一些傳統的演算法不見 得能適用於 FPGA ，例如佈局和繞線法，最近幾年都不斷地有不同的演算 法提出來。以 FPGA 的繞線法而言，因為FPGA的 Routing Resource 是固 定的，所以以往發展的方法大多是針對如何以較小的 Routing Track來使 整個線路繞進去，而沒有考慮到結果對於線路的 path delay 的影響，這 樣可能會因此獲得一個效能(performance) 很差的設計。於是我們的繞線 方法針對這個缺點去改進，不僅考慮到了Routing Track 的最小化，而且 考慮到 path delay 的最小化。我們的方法是以模擬進化(Simulated Evolution) 的程序為基礎，共分為兩部份分別去解決Routing Resource Violation 與 Timing Violation 。在第一部份，我們依據每條 net 其 Routing Resource Violation的嚴重程度求得每一條 net 的 score，再 依 score 的高低作為選擇哪些 net 重繞的標準。同理在第二部份，我們 依照slack的大小算出每一條net的 score，再依此作為rip-up-and- reroute 的依據。本論文分為六章。第一章為前言；第二章簡介相關研究 ；第三章描述問題與我們所使用的模型(model) ；第四章詳述我們提出的 繞線演算法 TRACER-fpga_PR ；第五章列出實驗的結果；最後在第六章作 個結論。