以現場可程式化邏輯閘陣列結構導向同步放置與全域繞線的測度法

Abstract

由於其低設計成本、使用者可程式化和較短的設計週期，現場可程式化邏輯閘陣列 (FPGAs) 已經成為一種很普及的邏輯電路設計方法。現場可程式化邏輯閘陣列的繞線資源 (routing resources) 是由導線段 (wire segments) 及可程式化開關 (programmable switches) 所組成; 再者，為了同時增進電路效能及保有合理的可繞度，現場可程式化邏輯閘陣列的繞線軌道 (routing tracks) 通常會由不同長度的導線段所組成。現場可程式化邏輯閘陣列的繞線動作乃是藉由控制導線間的可程式化開關來完成導線段之間的連通。可程式化開關有很高的電阻與電容，以致於會導致較大的訊號延遲。在過去的文獻□顯示：電路在做繞線時，所使用的開關總數 (而非導線段的總長度) 對於控制繞線延遲 (routing delay) 與繞線成本 (cost) 的影響最大。所以，在現場可程式化閘陣列的繞線中，電路做繞線時使用的開關數總並不一定與繞線時使用的導線段長度成正比。 由於分段式繞線結構 (segmented architecture)，傳統測量繞線成本 (如導線段總長，訊號延遲時間，通道阻塞程度等等) 都只是依據在幾何最短距離(geometric distance) 和 (或) 通道疏密度 (channel density) ，這樣子的測度方式對於現場可程式化邏輯閘陣列並不準確。再者，繞線通道的通道阻塞程度應該是依據各個不同長度的次通道 (subchannel) 可使用導線段，而不是只去計算整個通道的疏密度。在過去的所做過放置 (placement) 與全域繞線 (global routing) 的研究文獻中，他們通常都只有考慮單一長度的導線段。為了充分發揮分段式結構以及利用各種長度的繞線軌道，我們提出了一個以現場可程式化邏輯閘陣列結構為導向的測度法 (metric) 去同步放置與全域繞線。這個新的測度法考慮了目前仍可使用的各種長度次通道內導線段與其長度資源去將繞線成本最佳化。為了要去探索我們所提出新測度法的效用，我們將新測度法與傳統的測度法分別應用到同步放置與全域繞線的演算法中，做放置與全域地繞 SEGA 測試電路 (benchmark circuits) 。然後，將其各自全域繞線之後的結果再分別餵入 SEGA 細部繞線器 (detailed router) 中 (因為SEGA 細部繞線器可以考量分段式繞線結構) 去得到最後的繞線結果。在實驗中，我們將所提出的結構導向的新測度與傳統測度法分別應用在近似 Xilinx XC4000E, XC4000EX與 Lucent ORCA2C的商業用現場可程式化邏輯閘陣列結構上面。實驗結果顯示比之前的傳統測度法在所使用的繞線軌道數目 (面積) 、最大線段延遲時間、平均線段延遲時間方面各平均地減低 (改進) 了7.8%, 22.4%, 20.1%。

Due to their low prototyping cost, user programmability and short turnaround time, Field Programmable Gate Arrays (FPGAs) have become a very popular design style for ASIC applications. FPGA routing resources typically consist of wire segments and programmable switches; to improve circuit performance and maintain reasonable routability simultaneously, FPGA routing tracks usually consist of wire segments with a versatile set of lengths. Routing in FPGAs is performed by programming the switches to make connections between wire segments. The switches usually have high resistance and capacitance, and thus incur significant delays. Researchers have shown that the number of segments (i.e. number of switches used), instead of geometric distance, travelled by a net is the most crucial factor in controlling the routing delay and cost in an FPGA. Thus, in FPGA routing, the number of switches used by a signal is not necessarily proportional to the wirelength of the signal. Due to the segmented routing architectures, the traditional measure of wiring cost (wirelength, delay, congestion, etc) based on geometric distance and/or channel density is no longer accurate for FPGAs. Further, the congestion information of a routing channel shall be measured by the available segments of specific lengths, instead of the density in a whole channel alone. Previous work often considers only unit-length wire segments during placement and global routing phase. To remedy the deficiency, we propose an architecture-driven metric for simultaneous FPGA placement and global routing in this thesis. The new metric considers the available segments and their lengths to optimize the wiring cost for placement and global routing. To explore the effects of our new metric on routing solutions, we incorporate the architecture-driven and traditional metrics into a simultaneous placement and global routing algorithm to place and globally route the SEGA benchmarks. The global routing results generated from each metric are then fed into SEGA detailed router (which can consider the segmented routing architecture) to obtain the final routing solutions. Experiments show that the new metric results in respective average reductions of 7.8\%, 22.4\%, and 20.1\% in the number of tracks used (area), maximum net delay, and average net delay based on the Xilinx XC4000E-like, XC4000EX-like, and Lucent ORCA2C-like architectures, compared with the traditional metric of geometric distance and channel density.