可布性驅動的FPGA總體布局優化算法

張曉珂　高文超　周強 錢旭 賈澤宇

摘要 自從FPGA問世以來，FPGA布局研究一直是設計自動化研究領域的熱點，傳統FPGA布局一般要求芯片連線總長最短、芯片面積最小。隨著 IC工藝技術的飛速發展，可布性研究越來越受到關注。而擁擠度是衡量可布性的重要指標，布線中擁擠的出現往往來源于布局不合理，因此需要在布局階段就考慮可布性。提出了一種考慮水平和垂直溢出的可布性驅動的線長模型，將其與解析式布局的目標函數相結合，以優化布線擁擠和線長，減少運算的復雜度。實驗證明，相比FPGA解析式布局算法，線長和擁擠度都有了很大改進。

關鍵詞 FPGA；可布性；擁擠度；總體布局

DOI DOI： 10.11907/rjdk.162490

中圖分類號： TP312

文獻標識碼： A 文章編號 文章編號： 16727800（2017）002004803

0 引言

隨著時代的發展，專用集成電路（ASIC）已遠遠不能滿足用戶需求，因而更多的研究者將目光轉向了半定制設計模式的器件，成為近期用途最廣泛的一種可編程邏輯器件。FPGA（現場可編程門陣列）憑借著靈活性、高集成度、低功耗等特點備受設計人員的矚目。FPGA通常包含3類可編程資源：二維的可編程邏輯模塊（Configuration logic blocks，CLB）、外圍的輸入輸出模塊（I/O Blocks，IOB）和可編程互聯線資源（Interconnection Resource，IR）。

近年來，FPGA的結構也層出不窮，下列是幾種用途比較廣泛的結構：對稱式、基于行結構、門海式及層次式等。對稱型結構，又稱為孤島型結構，是用途最廣泛的一種結構。島型 FPGA 包含了行排和列排的邏輯單元 CLB，水平和垂直的布線通道包含不同長度的布線段。邏輯單元的引腳通過連接盒（Connection Box）連接到水平盒垂直布線通道中的線段上，這些線段再通過開關盒（Switch Box）以一定的方式互相連接。

在FPGA整體設計過程中，布局和布線是非常重要的兩大部分，在布線階段不能實現100%的布通率，需要返回去重新布局，直到完全可布，往返的過程會大大增加設計時間。因此，在布局階段關注可布性，能夠極大提高FPGA的設計效率。本文研究的重點就是在FPGA布局過程中讓可布性問題得到更好的解決。

1 布局器介紹

本文的可布性優化策略均在解析式布局器[1]的基礎上進行實驗。使用最小線長目標，同時盡量減少模塊間的重疊。問題表達為：

其中，HPWL（x，y）是所有模塊總的半周長，Db（x，y）是密度公式，Mb是期望得到的每個網格里的平均密度。線長和密度公式都不可微，因此首先要對這兩個函數進行平滑轉換。

使用log-sum-exp方法來近似式（1）中非線性半周長線長。

采用鐘形公式[3]來模擬密度部分：

用懲罰函數方法將線長目標和密度約束連接起來，這樣，有限制的最優化問題就轉化成為一個無約束的優化問題：

最后采用共軛梯度法進行求解。

2 基于線長模型的可布性優化算法

可布性驅動的FPGA布局算法有3方面的核心技術[2]：可布性評價標準、可布性預測和可布性優化。

2.1 可布性評價標準

可布性評價就是當布局完成后進行總體布線，然后根據總體布線結果評價布局結果的可布性。目前最常用的方法就是結合總線長和總體布線的擁擠度作為可布性的評價標準。

在島型結構上實現布局算法，就是對CLBs進行放置以后，為了能夠將電路芯片進行合理的連接運行，這需要了解開關盒資源的利用情況，因此擁擠度的研究將集中在開關盒（Switch Box）上。布線資源Se是一個固定值，根據芯片的技術參數如可用的布線層數、每一層的走線方向以及開關盒的尺寸來進行計算。布線需求De是穿過邊開關盒線網的總數。當且僅當De大于Se時 ，即開關盒的布線資源使用量超出布線資源擁有量時，就出現布線擁擠的情況，此時布線溢出量（Overflow）大于零。對于一塊FPGA芯片而言，總的布線溢出量可以用來評價一個已知布局的擁擠度情況。

2.2 可布性預測

可布性預測采用布線估計模型設計，布線估算模型主要分為兩類：脫離線網拓撲結構模型（Topology-Free Modeling）和基于線網拓撲結構模型（Topology-Based Modeling）。

基于拓撲結構的布線模型一般采用斯坦納樹（Steiner Tree）結構對每個線網進行布線需求建模。但是在布線過程中，對網表中所有的線網建立ST樹是一個較為復雜的過程。同時，每次布局更新操作中，布線路徑都會發生變化，因此需要重新進行ST樹的建立，這樣將會引發大量的計算，因此該模型時間代價較高。先對部分網格預先計算好斯坦納樹，然后在布局過程中利用這些數據，這種方法可降低計算的復雜度。對于多端線網而言，增量式的A*tree算法，可以建立一個線性的斯坦納樹分支來支持增量更新，這樣也可降低算法的計算量。脫離拓撲結構的布線模型在布局階段不進行實際布線，只是根據某種策略估算布線需求，因此計算量小、速度快，但其精確性依賴于FPGA具體結構和估算策略。

2.3 可布性優化

可布性優化采用布線擁擠度方案選取的方法進行，布線模型完成后，在全局布線網格上可以得到一個布線擁擠度圖（Congestion Map）。到目前為止，已研究出多種可布性的優化算法，如圖1所示。

圖1（a）代表了初始的預估布線拓撲結構。假設每個布線邊緣的布線容量為1，那么它有3個水平邊緣的溢出。假設每個pin點都在網格的中央，得到線網的總線長為11。圖1（b）代表了單元膨脹的可布性優化算法。單元膨脹是將每個標準單元按固定比例的大小進行放大，等到下一次迭代過程，標準單元所占布局區域的比例就會更大，將標準單元體積縮小到正常大小時，它與其它標準單元之間的間隔就會增大。經過單元膨脹，水平邊緣的溢出數量減少為2個，線長維持不變為11。單元膨脹策略被廣泛應用于很多布局算法中，例如Ripple、SimPLR[3]、CRISP[4]等。CROP[5]布局算法介紹了一種基于權重的線長模型，能夠有效減少線網邊界框的大小，以此來控制布線擁擠。如圖1（c）所示，它最終發生了兩個水平邊緣的溢出，線長的大小減少為6。TimberWolf布局算法提出了另一種基于權重的線長模型。為了更加全面地緩解布線擁擠，Jiang et al.[6]和 Chuang et al.[7]通過在全局布局中引入了一個擁擠度近似模型來移除線網邊界框之間的重疊。如圖1（d）所示，只有將線網邊界框的重疊移除，才能有效地最小化布線擁擠。相比之下，Tsota et al.[8]將線長密度應用到解析式布局框架中。Hsu et al.[9]通過引入一個s-型方程減少布線擁擠，它是基于解析式布局的溢出改進算法。Hsu et al.[10]進一步提出了一個線網擁擠優化技術來分散這些線網邊界框的密度，使其均勻地分布在整個布局區域來優化可布性。圖1（e）最終的結果是0個溢出，單位長度為9。

本文提出了一種同時考慮水平溢出和垂直溢出的可布性驅動的線長模型，將其與解析式布局的目標函數相結合以優化布線擁擠和線長。如圖1（f）所示，通過可布性驅動的線長模型，布局完成后的結果為0個溢出和5個單位長度的線長。對線長公式進行改進，可布性驅動線長的非線性公式被定義為：

其中，αe和βe分別代表了線網e的水平和垂直權重。為了準確地模型化水平和垂直布線擁擠的影響，定義水平和垂直的線網權重如下：

θy，e和θx，e分別代表了標準化的垂直和水平溢出。為了同時優化線長和可布性，αe和βe都由相同的可布性因素決定，其中一個增加，另一個則減小。而線網邊界框形狀的改變都要依靠標準化的水平和垂直溢出，這樣可布性驅動的線長不會有明顯改變。

這樣，可以將log-sum-exp公式轉變為如下形式：

然后使用共軛梯度法（CG）來解決這個無約束的最小化問題。

3 實驗結果

FPGA全局布局流程程序使用C++編程語言在OA平臺上實現，運行在使用Intel Xeon 3.0GHz CPU，6G內存的Linux服務器上。由于FPGA無太多測試用例，因而實驗選取ISPD04 benchmarks[13]進行測試。

表1為本文布局器與基礎布局器的實驗結果對比，第1列為選取的ISPD2014的前12個例子，第2、3列為本文布局器的詳細布局線長和占用內存，第4、5列為基礎布局器的詳細布局線長和占用內存，其中dpWL代表的是詳細布局的線長，作為評價總線長的標準，單位為毫米（mm），CPU以時間為標準，單位為分（min）。表1的最后一行為本文布局器和基礎布局器12個例子的平均線長，相比基礎布局器，本文布局器的平均線長優化了14%，保證了在優化可布性的同時，布局線長也有所優化。

4 結語

本文實現了一個基于線長模型的FPGA可布性優化算法，它以孤島型FPGA結構為依據，采用解析式布局器作為基礎布局器，在優化大多數布局存在可布性問題的同時還能夠優化線長。不僅在布線階段解決了擁擠問題，且與解析式布局算法相比較，有更好的質量結果。實驗證明了其結果的有效性和合理性。期望后續研究可以實現：可針對開關模塊（Switch Box）提出擁擠度優化策略，根據可布性評價標準，在APlace框架的目標約束中增加可布性約束。

參考文獻：

[1] 高文超，周強，呂勇強，等.應用于大規模FPGA的解析式布局算法[J].計算機輔助設計與圖形學學報，2011（11）：19441948.

[2] 周全.詳細布線可布性驅動的布局算法研究[D].北京：清華大學，2015.

[3] M C KIM，J HU，D J LEE，et al.A simplr method for routabilitydriven placement[C].In Proc.of ICCAD，2011：6773.

[4] J A ROY，N VISWANATHAN，G J NAM，et al.crisp：congestion reduction by iterated spreading during placement[C].In Proc.of ICCAD，2009：357362.

[5] Y ZHANG，C CHU CROP.Fast and effective congestion refinement of placement[C].In Proc.of ICCAD，2009：344350.

[6] Z W JIANG，B Y SU，Y W CHANG.Routabilitydriven analytical placement by net overlapping removal for largescale mixedsize designs[C].In Proc.of DAC，2008：167172.

[7] Y L CHUANG，G J NAM，C J ALPERT，et al.Designhierarchy aware mixedsize placement for routability optimization[C].In Proc.of ICCAD，2010：663668.

[8] K TSOTA，C KOH，V BALAKRISHNAN.Guiding global placement with wire density[C].In Proc.of ICCAD，2008：212217.

[9] M K HSU，S CHOU，T H LIN，et al.Routabilitydriven analytical placement for mixedsize circuit designs[C].In Proc.of ICCAD，2011：8084.

[10] M K HSU，Y F CHEN，C C HUANG，et al.Routabilitydriven placement for hierarchical mixedsize circuit designs[C].In Proc.of DAC，2013：16.

（責任編輯：孫 娟）