以時間效能為導向的現場可程式化閘陣列繞線器的製作

Abstract

現場可程式化閘陣列繞線器 (FPGA) 的繞線資源 (routing resources) 是由導線段 (wire segments) 及可程式化開關 (programmable switches) 所組成。現場可程式化閘陣列的繞線乃藉由控制導線段間的可程式化開關來完成導線段連通。可程式化開關有很高的電阻與電容，會導致較大的訊號延遲。在過去的文獻顯示：線路在做繞線時，所使用的開關總數 (而非導線段總長度) 對於控制繞線延遲 (routing delay) 的影響最大。在現場可程式化閘陣列的繞線中，繞線使用的開關數總並不一定與繞線使用的導線段長度成正比。所以，考慮繞線使用導線段長度的傳統延遲模型 (delay model)，並不適用於現場可程式化閘陣列。再者，為了同時增進線路效能及保有合理的可繞度，繞線軌道 (tracks) 會由不同長度的導線段所組成。過去文獻所提之繞線器通常只考慮一種長度的導線段。 在本篇論文中，我們實作了在 [41] 中提出的以時間效能為導向的現場可程式化閘陣列區域性繞線器 (global router) 及細部繞線器 (detailed router)，同時，再提出三個經驗法則 (heuristics) 來增進此繞線器的效能。此繞線器能針對各種不同長度的導線段做處理，而其使用的時間模型，是考量繞線所使用開關總數。此繞線器是用階層式由上往下 (hierarchical top-down) 的方法。首先，使用一分隔線 (cut line) 將電路分成兩子電路。在每個階層中，使用一全域性繞線器來判斷兩子電路間的線路會經由哪些區域，而後再應用 bipartite matching 演算法來決定各線路的細部繞線途徑。而後，兩子電路重複使以相同的方法。直到所有子電路都能很簡單地來個別處理。實驗結果顯示：對於一基於傳統時間模型的繞線器，若是使用此時間效能為導向的繞線器，不滿足延遲要求線路的總數將會減少78%。 本論文亦提出三個經驗法則 (heuristics) 來增進此時間效能為導向繞線器的性能，分別為：端點轉換 (pin swapping)、轉彎數預測 (bend prediction)、線路傳送 (net propagation)。端點轉換是為邏輯模組上的端點找一較佳位置讓繞線使用的開關總數達到最少，轉彎數預測是估計繞線使用開關數目的多寡，而線路傳送則是藉由傳遞線路的資訊用來幫助細部繞線器選擇較佳的導線段。實驗結果顯示，對於原時間效能為導向的繞線器，若是加以應用端點轉換、轉彎數預測、線路傳送，則不滿足延遲要求線路的總數將會減少41%、 21%、17%。最後，如果我們將三個經驗法則都應用到此繞線器，不滿足延遲要求線路的總數將會減少 50%。

FPGA routing resources consist of wire segments and programmable switches. 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 switches, instead of wirelength, used by a net is the most critical factor in controlling routing delay in an FPGA. In FPGA routing, the number of switches used by a signal is not necessarily proportional to the wirelength of the signal. Therefore, the traditional measure of routing delay based on the geometric distance of a signal is no longer accurate for FPGAs. Further, to improve circuit performance and maintain reasonable routability simultaneously, FPGA routing tracks consist of wires with a versatile set of lengths. Previous work often considers only unit-length wire segments. In this thesis, we implement an FPGA timing-driven global and detailed router proposed in [41] and present three heuristics to improve the performance of the router. The router considers wire segments of multiple lengths and is based on a timing model associated with the number of switches used. The router uses a hierarchical top-down approach, starting at dividing an entire circuit into two subcircuits by a cut line. At each hierarchical level, we first use a global router to determine the region assignments for connections between the two subcircuits and then apply the weighted bipartite matching algorithm to allocate the detailed routing paths for each net. The hierarchical process proceeds recursively until the subcircuits are easy to be handled. Experimental results show that the timing-driven router can achieve an average of 78\% reduction in the total number of nets violating timing constraints, compared with a router based on the traditional timing model. We also present three effective heuristics to further improve the performance of the timing-driven router, namely, pin swapping, bend prediction, and net propagation. The pin-swapping heuristic is to pick a better logic-module pin position to minimize the number of bends used by a net. The bend-prediction heuristic is to predict the number of bends used by a net. The net-propagation heuristic is to assist the detailed router to select more suitable wire segments by propagating the information for net connections. Experimental results show that the pin-swapping, the bend-prediction, and the net-propagation heuristics can achieve respective averages of 41\%, 21\%, and 17\% further reductions in the total number of nets violating timing constraints, compared with the original timing-driven router. Finally, if we simultaneously apply the three heuristics to the original timing-driven router, the total number of timing violations will be reduced by an average of 50\%.