使用初步佈局叢集方法之異質型FPGA擺置器

Abstract

科技日新月異，在FPGA架構及電路都愈漸複雜之下，叢集和佈局兩個電子設計自動化的步驟越顯得重要，其結果都將影響最後繞線的品質以及電路的效能。 在電子設計自動化的流程中，我們必須在叢集這個步驟將電路的基礎元件在考慮邏輯相關的電路聯繫下包裝進可設定邏輯區塊中，才能進行下一個佈局的步驟。 而現代的異質型FPGA架構中，除了基本的輸入輸出元件區塊、可設定邏輯區塊外，還有嵌入式的記憶體區塊和數位訊號處理區塊，這也使得佈局需要針對這些來做功能的調整。 在這篇論文裡，我們提出了一個使用初步佈局叢集方法的異質型FPGA擺置器。在叢集階段，我們對所有元件進行快速的初步佈局，以佈局的結果作為參考來進行基礎元件的叢集；在叢集中，我們在考慮正反器的控制訊號限制下，對基礎元件以其相關密切性來進行分群，而分群後將群組包裝成可設定邏輯元件以進行佈局。而在佈局階段，我們採用了線長驅動的全域擺置器，其中有許多針對異質型FPGA架構來進行調整的技巧，包含(1)針對複雜邏輯元件進行位置校正、(2)預估繞線壅塞程度來進行元件膨脹、(3)利用佈局遷移法來降低全域擺置到佈局合法化間的元件總位移量，最後藉由佈局合法化及詳細佈局完成整個擺置器。實驗結果顯示以上所述之方法皆可有效率的提升佈局的品質。

Packing and Placement are two crucial stages for FPGA implement. In the design flow, the basic logic units, such as look-up-tables (LUTs) and flip-flops (FFs), have to be merged into configurable logic blocks (CLBs) before placement. How the basic logic blocks are clustered in the packing stage has a great impact on the placement quality. This work presents an analytical placement framework for heterogeneous FPGAs through a rough-placed packing algorithm. In the packing stage, we first perform a fast wirelength-driven placement for the basic logic units. With the physical information from the initial placement, we implement an affinity-based clustering algorithm while taking the control signal constraints into consideration. In the placement stage, a quadratic global placer is implemented with the techniques of handing the heterogeneity, routing congestion estimation and cell inflation. An incremental placer is performed after the global placement for closing the gap between the global placement and legalization, and a detailed placer is adopted to legalize the blocks and reduce the wirelength. Experimental results show that the proposed methodologies can effectively improve the placement solutions.