反熔絲FPGA布局算法

魏 巖

（中國(guó)電子科技集團(tuán)公司第四十七研究所，沈陽(yáng)110032）

反熔絲FPGA布局算法

魏 巖

（中國(guó)電子科技集團(tuán)公司第四十七研究所，沈陽(yáng)110032）

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

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

1 引 言

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

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

2.1 基本布局算法模型

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

2.2 反熔絲FPGA結(jié)構(gòu)簡(jiǎn)介及傳統(tǒng)布局算法面臨的問題

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

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

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

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

可以看到，由于傳統(tǒng)布局算法對(duì)反熔絲結(jié)構(gòu)的預(yù)估不足，在這根5扇出的線網(wǎng)上使用了4根水平線和2根垂直線。對(duì)于反熔絲FPGA的結(jié)構(gòu)來(lái)說(shuō)，這樣的布局結(jié)果在布線后會(huì)造成很大的線網(wǎng)資源浪費(fèi)。

2.3 針對(duì)反熔絲FPGA布局算法的改進(jìn)

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

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

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

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

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

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

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

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

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

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

2.4 測(cè)試與驗(yàn)證

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

表1 布局算法改進(jìn)前后布局模塊耗時(shí)對(duì)比

3 結(jié)束語(yǔ)

針對(duì)反熔絲FPGA的結(jié)構(gòu)特點(diǎn)，對(duì)傳統(tǒng)的FPGA布局算法進(jìn)行改進(jìn)。改進(jìn)的布局算法通過測(cè)試表明，這些改進(jìn)可以大幅提高布局質(zhì)量，減少布線器的壓力。

［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］ 洪先龍，嚴(yán)曉浪，喬長(zhǎng)閣.超大規(guī)模集成電路布圖理論與算法［M］.北京：科學(xué)出版社，1998.

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

［6］ 王燕華.可布性驅(qū)動(dòng)的層次式FPGA布局算法研究［D］.北京：華北電力大學(xué)，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-），男，遼寧省盤錦市人，助理工程師，主研方向：集成電路設(shè)計(jì)。

2015-01-15