請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/74373
標題: | 在多重可程式化邏輯閘陣列系統上之效能導向同時分區和繞線 Performance-Driven Simultaneous Partitioning and Routing on Multi-FPGA Systems |
作者: | Jun-Jie Wang 王俊傑 |
指導教授: | 張耀文(Yao-Wen Chang) |
關鍵字: | 實體設計,多重可程式化邏輯閘陣列系統,分時多工,電路分區,電路繞線, Physical Design,Field Programmable Gate Array,Time-Division Multiplexing,Partitioning,Routing, |
出版年 : | 2019 |
學位: | 碩士 |
摘要: | 現今多重可程式化邏輯閘陣列(FPGA)系統因其優異的效能以及可擴縮性而逐漸流行用於晶片設計中的重要步驟邏輯驗證,邏輯驗證目標為驗證一個電路設計的功能性是否正確。多重可程式化邏輯閘陣列系統包含多顆可程式化邏輯閘陣列,這些可程式化邏輯閘陣列是利用實體線作連接,在邏輯驗證中,一個電路會被分區成多塊,且放置於各個可程式化邏輯閘陣列中,再利用實體線將各塊的信號連接起來。然而,受限於單個可程式化邏輯閘陣列中有限數量的輸入輸出,不是所有訊號都能完整的傳送,繞線資源可能無法容納所有跨可程式化邏輯閘陣列的訊號。因此,輸入輸出分時多工技術(Input/output time-division multiplexing)被引進,此技術可以使一組訊號共用一個繞線通道,雖然會有額外的時間懲罰,但能解決繞線資源不足的問題。
為了優化系統效能,在本篇論文中,我們提出一個同時分區和繞線且考量分時多工技術的時間懲罰的演算法。在此演算法中,我們提出一個新穎考量繞線的初始分區框架,能夠減少在初期估計繞線的複雜度且能夠處理系統中不規則的實體線連接,以及一個考量分區的繞線計策,能夠在每次分區遍數中優化繞線,改善在分區接繞線兩階段流程中的不足。 實驗結果顯示,我們所提出的方法相較於先前的研究,可以得到良好的分區和繞線結果,並且可在大型標竿測試基準中得到驗證。 The multi-FPGA system has become popular for logic verification, which aims to verify the functionality of a design, due to its high performance and scalability. A multi-FPGA system consists of multiple FPGAs connected by physical wires, and a circuit is partitioned to fit each FPGA and routed on the system by such physical wires. Due to the limited numbers of input/output (I/O) pins in an FPGA, however, not all signals can be transmitted between FPGAs directly. Moreover, the routing resource may not be sufficient to accommodate a large number of cross-FPGA signals from circuit partitioning. As a result, input/output time-division multiplexing (TDM) is introduced to send a group of cross-FPGA signals in a routing channel with timing penalty. To optimize the performance of such a system, it is desirable to develop a simultaneous partitioning and routing algorithm considering the timing penalty caused by I/O TDM. Considering TDM delay penalty, in this thesis, we propose a simultaneous partitioning and routing algorithm with a novel routing-aware initial partitioning framework to reduce the problem size of routing and a partition-aware routing scheme to optimize routing in each partitioning pass, remedying the insufficiency of the two-stage flow of partitioning followed by routing. Experimental results show that our proposed algorithm can achieve better quality partitioning and routing results than the classic flow. Our program is evaluated on the titan23 benchmark suite and two multi-FPGA systems, one from the 2019 CAD Contest at ICCAD and the other modified from the previous one. Compared with the classic flow, our algorithm can outperform averagely 54\% and 57\% in the maximum timing cost for two FPGA system respectively. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/74373 |
DOI: | 10.6342/NTU201902811 |
全文授權: | 有償授權 |
顯示於系所單位: | 電子工程學研究所 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-108-1.pdf 目前未授權公開取用 | 2.36 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。