魏 巖

（中國電子科技集團公司第四十七研究所，沈陽110032）

反熔絲FPGA布局算法

魏 巖

（中國電子科技集團公司第四十七研究所，沈陽110032）

布局是大規(guī)模集成電路設計中非常重要的環(huán)節(jié)。在現(xiàn)場可編程門陣列（Field Programmable Gate Array，F(xiàn)PGA）的應用中，由于布線資源已經(jīng)確定，所以FPGA的布局算法更加重要。針對反熔絲FPGA的布局應用，在目前最流行的布局算法上進行改進和優(yōu)化很有必要。以建立高性能、低擁擠的布局為目標，從反熔絲FPGA芯片結構和布局算法兩方面進行了深入研究。根據(jù)更精確的代價值計算，以及代價框模型和移動上限的改善，得到更有效的布局結果。反熔絲FPGA的布局算法需要新的代價值計算方法和計算公式。通過實驗驗證，改進后的反熔絲FPGA布局算法的布局結果更為合理，為下一步的布線工作展開建立了良好接口。

布局算法；反熔絲；現(xiàn)場可編程門陣列；模擬退火算法；行排列FPGA；代價值

1 引 言

目前，市場上有三種基本的FPGA編程技術：SRAM、Flash、反熔絲。其中反熔絲具有高抗干擾性和低功耗的優(yōu)點，適用于要求高可靠性、高保密性的定型產(chǎn)品。學術界大都是針對孤島型結構的SRAM的FPGA布局算法進行研究，對行排列的反熔絲FPGA的研究較為匱乏［1］。傳統(tǒng)的布局算法應用在反熔絲FPGA時效率低、布局結果差，對布線造成較大壓力。所以，需要在反熔絲FPGA的結構上，有針對性的對布局算法進行改進和優(yōu)化。

2 反熔絲FPGA布局算法的設計和實現(xiàn)

2.1 基本布局算法模型

布局問題屬于NP難題，想要找到較好的布局結果非常困難。目前典型的布局算法模型有：基于劃分的布局算法、遺傳算法、模擬退火布局算法等。其中，模擬退火算法［2-3］計算過程簡單、通用，在增加新的優(yōu)化目標或者約束方面方便得多。

2.2 反熔絲FPGA結構簡介及傳統(tǒng)布局算法面臨的問題

有別于其它結構的FPGA，反熔絲FPGA的邏輯單元都是N輸入、1輸出的邏輯結構，而且反熔絲FPGA的結構是行排列的FPGA結構［4］。如圖1所示。

由于這種特殊的結構，傳統(tǒng)布局算法如果直接應用在反熔絲FPGA上則會造成水平線網(wǎng)資源浪費以及對多扇出線網(wǎng)預估不足的問題。

例如，在傳統(tǒng)布局算法下，一根5扇出的線網(wǎng)在布局布線后可能會得到圖2的結果。

圖2 傳統(tǒng)布局算法下1根5扇出的線網(wǎng)所占用的資源

可以看到，由于傳統(tǒng)布局算法對反熔絲結構的預估不足，在這根5扇出的線網(wǎng)上使用了4根水平線和2根垂直線。對于反熔絲FPGA的結構來說，這樣的布局結果在布線后會造成很大的線網(wǎng)資源浪費。

2.3 針對反熔絲FPGA布局算法的改進

布局算法在衡量布局結果是否合理時需要預估線網(wǎng)對布線資源產(chǎn)生的壓力和代價。而在布局器預估代價值的大小時，建立了一個半周長線長模型［5］。半周長模型包含線網(wǎng)所有頂點的一個最小矩形稱為邊界框［6］。在反熔絲布局中，為了精確計算線網(wǎng)的代價值，分別計算水平方向和垂直方向的邊界框線長：

普通模擬退火算法的代價函數(shù)計算公式抽象為：

其中，q（i）是補償因子。這是因為當線網(wǎng)端點數(shù)目超過3時，邊界框線長模型低估了所需要的連線［7］。bbx和bby分別代表水平、垂直方向代價框的值。

由于反熔絲和Flash系列的FPGA結構多為N輸入、單輸出的邏輯單元。在結構上鼓勵由一個輸出驅動的多個邏輯單元布局在同一水平排列上，并勵電路盡量利用橫向的布線資源。所以，修改代價函數(shù)計算公式如下：

其中，βx和βy分別是根據(jù)FPGA的水平、垂直方向的線網(wǎng)資源得到的針對水平方向和垂直方向的相對代價成本。fanout（i）是根據(jù)當前線網(wǎng)neti的扇出數(shù)做出的代價重視增益。也就是說在網(wǎng)表的代價計算時要更多的為多扇出的線網(wǎng)考慮，并降低橫向布局成本，提高縱向布局成本。所述線網(wǎng)neti的代價值與fanout（i）成正比，與βx和βy成反比。

每次充分迭代后，根據(jù)新的布局代價評估重新計算溫度、交換限制。交換限制的計算公式為：

percsucc是上一個溫度下移動接受的百分比，根據(jù)實驗得出：percsucc＝0.44是最佳移動接受率［8］，所以公式使用（1-0.44＋percsucc）可以找到最合適的交換限制。Cx和Cy代表水平和垂直方向的平均布線通道寬度，由于水平布線資源比垂直布線資源豐富，所以布局算法可以通過Cx和Cy來限制垂直方向的對交換，提高水平方向的調整速率。

通過上述有針對性的改進，在圖2所示的同樣的5扇出線網(wǎng)會有如圖3中所示的改善：

圖3 改進后的布局算法下1根5扇出的線網(wǎng)所占用的資源

如圖3所示，同樣的線網(wǎng)在布局算法改進之后只占用了2根水平線和1根垂直線，線網(wǎng)資源的利用率得到了明顯改善。

2.4 測試與驗證

為了對改進的布局算法進行驗證，在基于反熔絲結構的FPGA芯片上（規(guī)模為100×30個邏輯單元）進行了測試。在布線器不做調整的前提下，測試不同的布局算法得到布局結果對布線器的影響。節(jié)選測試結果如表1所示。通過表1可以看到，基于改進的布局算法得到的布局結果對布線的壓力明顯減少。布線器能夠更快的找到布線路徑，也就是說改進的布局算法得到的布局結果更為合理。

表1 布局算法改進前后布局模塊耗時對比

3 結束語

針對反熔絲FPGA的結構特點，對傳統(tǒng)的FPGA布局算法進行改進。改進的布局算法通過測試表明，這些改進可以大幅提高布局質量，減少布線器的壓力。

［1］ PEDRAM M，NOBANDEGANI B S，PREAS B T.Design and analysis of segmented routing channels for rowbased FPGA＇s［J］.IEEE Trans Computer-Aided Design Integr Circ＆Syst，1994，13（12）：1470-1479.

［2］ SHARMA A，HAUCK S，EBELING C.Architecture adaptive routability-driven placement for FPGAs［C］.//Int Conf Field Program Logic＆Appl，2005：427-432.

［3］ Sechen C.The Timber Wolf placement and routing package［J］.Solid-State Circuits，1985，21：510-522.

［4］ S Brown，R Francis，J Rose.Filed Programmable Gate Arrays［M］.Boston，Kluwer Academic Publishers，1992.

［5］ 洪先龍，嚴曉浪，喬長閣.超大規(guī)模集成電路布圖理論與算法［M］.北京：科學出版社，1998.

Hong Xian long，Yan Xiao lang，Qiao Chang ge.Placement algorithm for Grand scale ic［M］.Beijing：Scientific Publishers，1998.

［6］ 王燕華.可布性驅動的層次式FPGA布局算法研究［D］.北京：華北電力大學，2008.

Wang Yan hua.Research of the Placement algorithm for Hierarchical FPGA［D］.Beijing：North China Electric Power University，2008.

［7］ KIRKPATRICK S，GELATT C D，VBCCHIM P.Optimization by simulated annealing［J］.Science，1983，220（4598）：671-678.

［8］ LAM J，DELOSME JM.Pedonmnce of a new anneling schedule［C］.//Proc 25th ACM/IEEE Des Autom Conf，1988：306-311.

Placement Algorithm s for Antifuse FPGA

Wei Yan
（The 47th Research Institute of China Electronics Technology Group Corporation，Shenyang 110032，China）

Placement is a very important part of Large Scale Integration Design.It＇s especially important on the application of Field Programmable GateWay（FPGA）as a result of the routing resource is fixed.It＇s necessary to improve algorithm to adapt for antifuse FPGA based on the most popular placement algorithm.Aiming at the higher performance and lower congestion，this article mainly focuses on the antifuse FPGA architecturemodel and related placement algorithm.The better placement result is found according to the exact cost and the improved bounding box and move limit.The placement algorithms of antifuse FPGA needs a new way to compute the cost and the corresponding mathematical model.The experimental results show that the improved algorithm ismore reasonable for antifuse FPGA and provides the better interface for the routing.

Placement algorithm；Antifuse；FPGA；Simulate Annealing algorithm；Row-style FPGA；Cost

10.3969/j.issn.1002-2279.2015.03.002

TN4

A

1002-2279（2015）03-0004-03

魏巖（1986-），男，遼寧省盤錦市人，助理工程師，主研方向：集成電路設計。

2015-01-15