考慮時鐘之大型異質可程式化邏輯閘陣列擺置

Clock-Aware Placement for Large-Scale Heterogeneous FPGAs

郭玧質(Yun-Chih Kuo)

指導教授 ： 張耀文

共同指導教授 ： 郭斯彥(Sy-Yen Kuo)

國立臺灣大學/電機資訊學院/電子工程學研究所/碩士(2017年)

https://doi.org/10.6342/NTU201704407

摘要

可程式化邏輯閘陣列 (field programmable gate array) 因其高度可塑性、快速縮短產品生產週期的特性、以及其非常適用於高階自動控制應用等等的特性，在近年來吸引了越來越多電路設計者的注意。現今可程式化邏輯閘陣列已經大幅度的演進，一個現代可程式化邏輯閘陣列可擁有高達數百萬的邏輯閘，並且整合了許多矽智產 (intellectual property) 模組，包括數位訊號處理器模組 (digital signal processor)、隨機存取記憶體模組 (random access memory)、高速傳輸介面模組 (high-speed transceivers)。除此之外，為了達到更低的時鐘偏移以及更好的電路效能，現代可程式化邏輯閘陣列通常會使用網狀的時鐘樹架構。然而可程式化邏輯閘陣列的邏輯繞線資源以及時鐘繞線資源皆是預先製造完成，並且有限的。現今已發表之可程式化邏輯閘陣列的擺置演算法並無考慮時鐘繞線資源的限制，這有可能導致之後的時鐘繞線失敗。
因此，為處理考慮時鐘繞線資源以及異質性整合之現場可程式化邏輯閘陣列擺置問題，在此篇論文中，我們提出一個新的針對大型異質現場可程式化邏輯閘陣列考慮時鐘之非線性擺置演算法。我們的演算法整合了：一個時鐘限制擺置區域的建置方法及限制擺置區域二次成本函數，可以有效的減少時鐘繞線資源的過度使用；一個座標轉換方法以及一個平滑的異質密度函數來處理窄通道問題以及異質擺放區域；一個異質力調變技巧來得到更好的擺置結果；一個考慮時鐘之兩階段巨集演算法；一個考慮時鐘之合法化及細部擺置演算法。
實驗結果顯示，我們所提出的方法相較於先前的研究，可以得到符合時鐘繞線資源限制且更好的電路擺置結果。並且可在大型標竿測試基準中得到驗證。

關鍵字

實體設計 ； 可程式化邏輯閘陣列 ； 電路擺置 ； 時鐘網路 ； 異質電路

並列摘要

The benefits of using FPGAs, such as the high flexibility to reconfigure functionality, the short turnaround time to market, and the natural fit for high-end control applications, have attracted higher attention from circuit designers in recent years.
Nowadays, as the architecture of the FPGA have been enhanced dramatically. The logic gate count of a modern FPGA has reached millions. Also, more and more heterogeneous intellectual property (IP) blocks, such as digital signal processing (DSP) blocks, random access memory (RAM) blocks, and high-speed transceivers, are integrated into modern FPGAs. Moreover, to achieve better skew and performance, a modern FPGA often contains a mesh-like clocking architecture. The logic and clocking resources of an FPGA are prefabricated, and thus are limited. Published FPGA placement algorithms seldom consider the clocking resource, and thus may lead to clock routing failures.
To address the special FPGA clocking architecture and heterogeneity of FPGA analytical placement problem, we proposed a novel clock-aware nonlinear placement algorithm for large-scale heterogeneous FPGAs. Our algorithm consists of:
(1) a nonlinear placement algorithm with a clock fence region construction technique and a smooth quadratic fence region cost to effectively reduce the overuse of clocking resources,
(2) a novel coordinate transformation method to handle the narrow channel problem in placement regions and a smoothed heterogeneous density function to guide heterogeneous blocks to the corresponding sites,
(3) heterogeneous force modulation technique to stabilize placement movement, and effectively increase placement quality
(4) a two-level clock-aware packing scheme considering complex, yet realistic packing and clocking constraints,
(5) clock-aware legalization and detailed placement considering the clocking constraints.

Experimental results show that our algorithm can achieve high quality placement result while considering complex packing and clocking resource constraints. We evaluate our algorithm on the 2017 ISPD Clock-Aware Placement Contest benchmark suite. Compared with the top-3 contest winners, the results show that our algorithm achieves the best overall routed wirelength. On average, our algorithm outperforms the top-3 winners by 5.7%, 9.7%, and 15.2% in routed wirelength, respectively.

並列關鍵字

Physical Design ； Field Programmable Gate Array ； Placement ； Clock Network ； Heterogeneous

參考文獻

[1] V. Betz and J. Rose, “Cluster-based logic blocks for FPGAs: Area-efficiency vs. input sharing and size,” in Proceedings of IEEE Custom Integrated Circuits Conference, pp. 551–554, 1997.

[2] ——, “VPR: A new packing, placement and routing tool for FPGA research,” in Proceedings of IEEE Field Programmable Logic and Applications, pp. 213–222, 1997.

[6] S.-Y. Chen and Y.-W. Chang, “Routing-architecture-aware analytical placement for heterogeneous FPGAs,” in Proceedings of ACM/IEEE Design Automation Conference, 2015.

[7] T.-C. Chen, Z.-W. Jiang, T.-C. Hsu, H.-C. Chen, and Y.-W. Chang, “NTUplace3: An analytical placer for large-scale mixed-size designs with preplaced blocks and density constraints,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 27, no. 7, pp. 1228–1240.

[8] Y.-C. Chen, S.-Y. Chen, and Y.-W. Chang, “Efficient and effective packing and analytical placement for large-scale heterogeneous FPGAs,” in Proceedings of IEEE/ACM International Conference on Computer-Aided Design, pp. 647–654, 2014.