反熔絲FPGA布線算法研究?

楊大為

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

反熔絲FPGA布線算法研究?

楊大為

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

國(guó)內(nèi)外學(xué)術(shù)界對(duì)目前廣泛采用的SRAM型FPGA布線算法均有大量研究，對(duì)于特殊用途反熔絲FPGA的研究卻很少。首先介紹了反熔絲FPGA及其布線算法的研究現(xiàn)狀，接著討論了目前最為流行的FPGA布線算法——路徑搜索算法的基本原理與實(shí)現(xiàn)方式，并且建立了反熔絲延時(shí)模型，然后針對(duì)反熔絲FPGA的結(jié)構(gòu)對(duì)布線算法進(jìn)行了改進(jìn)，最后在CAD實(shí)驗(yàn)平臺(tái)上實(shí)現(xiàn)了該改進(jìn)算法。實(shí)驗(yàn)表明，該改進(jìn)算法可以提高反熔絲FPGA布線的效率及電路速度。

反熔絲；路徑搜索；布線算法；FPGA

1 引 言

FPGA（現(xiàn)場(chǎng)可編程門陣列）是與CPU和DSP并列的目前半導(dǎo)體市場(chǎng)上最重要的三類核心數(shù)字器件之一。自從上世紀(jì)80年代中期被發(fā)明出來(lái)以后，它對(duì)電子產(chǎn)業(yè)產(chǎn)生的影響越來(lái)越大。根據(jù)編程結(jié)構(gòu)，F(xiàn)PGA可分為三種，分別是基于SRAM、FLASH和反熔絲（antifuse）的FPGA［1-4］。

SRAM型FPGA對(duì)單粒子效應(yīng)敏感性限制了它在太空中的應(yīng)用，特別是在太空中隨著輻射量的增加和輻射時(shí)間的增加，SRAM失效的可能性大大提高，而反熔絲FPGA卻能夠正常工作。因此在航空航天宇航等惡劣環(huán)境應(yīng)用中，反熔絲型FPGA具有不可替代的作用，成為空間領(lǐng)域使用的主流FPGA。

半導(dǎo)體工藝尺寸已經(jīng)進(jìn)入深亞微米領(lǐng)域，促使FPGA的邏輯容量大幅上升，使之能適合于實(shí)現(xiàn)更大規(guī)模的設(shè)計(jì)。為了充分利用這些深亞微米工藝技術(shù)，必須重新構(gòu)建FPGA硬件結(jié)構(gòu)和相應(yīng)的CAD工具。以下三個(gè)要素決定了FPGA的性能：將電路映射到FPGA的CAD工具質(zhì)量，F(xiàn)PGA硬件結(jié)構(gòu)特性和FPGA電路設(shè)計(jì)水平。因此開(kāi)發(fā)高效靈活的CAD軟件，對(duì)于設(shè)計(jì)FPGA也是至關(guān)重要的。布局布線是FPGA芯片設(shè)計(jì)中最耗時(shí)的階段，也對(duì)電路性能有著關(guān)鍵影響［1］。設(shè)計(jì)出更加快速、更小面積、延時(shí)少、低功耗的算法是學(xué)術(shù)界研究的熱點(diǎn)和趨勢(shì)。

反熔絲編程開(kāi)關(guān)是無(wú)源器件（融通型）［2］，占用的版圖面積很小，所以反熔絲結(jié)構(gòu)的FPGA有非常豐富的布線資源。同等芯片面積下，反熔絲FPGA的布線資源比SRAM FPGA多很多，其布線資源占芯片面積的大部分，因此布線相對(duì)耗時(shí)更多，對(duì)設(shè)計(jì)電路的速度影響也更大。目前主流的FPGA都是基于SRAM單元的，這是因?yàn)榉慈劢zFPGA的應(yīng)用很特殊，并且反熔絲制造困難，需要特殊工藝，只有國(guó)外少數(shù)公司掌握了該技術(shù)。因此目前工業(yè)界和學(xué)術(shù)界流行的FPGA布線算法都是針對(duì)島形和層次結(jié)構(gòu)的SRAM-FPGA的。反熔絲FPGA通常采用的基于行［3］的邏輯架構(gòu)（Row-based Architecture）研究較少，缺乏相關(guān)的文獻(xiàn)和工具，必須進(jìn)行充足的研究，才能確定設(shè)計(jì)方案?，F(xiàn)有算法對(duì)于開(kāi)發(fā)反熔絲FPGA布線算法有很好的指導(dǎo)意義，但是其對(duì)于FPGA的結(jié)構(gòu)具有很強(qiáng)的針對(duì)性，并沒(méi)有考慮到反熔絲FPGA的一些結(jié)構(gòu)上的特點(diǎn)。只有在修改這些算法后才能應(yīng)用在反熔絲FPGA的CAD軟件上，如何提高反熔絲FPGA的布線速度和質(zhì)量是本文研究的主要內(nèi)容。

2 反熔絲FPGA布線算法

2.1 基本布線算法

常見(jiàn)的FPGA布線器可以分為兩大類［1］，其中一種是全局兼詳細(xì)組合布線，這種布線方式一步就可以完成FPGA的布線。另一種方法是分為兩步實(shí)現(xiàn)布線：第一步運(yùn)行全局布線決定每條線網(wǎng)所使用的每個(gè)邏輯單元的引腳和可以使用的可分割線通道，第二步運(yùn)行詳細(xì)布線，根據(jù)第一步的結(jié)果，在允許使用的可分割通道中連接各個(gè)線網(wǎng)。因?yàn)镕PGA布線的靈活性有限，并且全局布線限制了各線網(wǎng)所能使用的通道線段，所以FPGA詳細(xì)布線器經(jīng)常不能或者很困難地完成布線任務(wù)。因?yàn)槿旨嬖敿?xì)布線器能夠避免這種限制，所以它能更好的優(yōu)化布線。

迷宮布線器用來(lái)連接各條線網(wǎng)的各個(gè)終點(diǎn)，而迷宮布線器其核心又是采用Dijkstra算法，即在布線資源圖［4］中尋找連接線網(wǎng)源端和漏端的最短路徑（最小成本）。在各種算法中，為了衡量布線結(jié)果的好壞而提出成本函數(shù)（Cost Function）［1］的概念，通常值越低表示布線結(jié)果越好，而對(duì)于不同的布線優(yōu)先目標(biāo)，成本函數(shù)也相應(yīng)不同。

因?yàn)镕PGA電路的速度很重要，所以我們主要研究有關(guān)時(shí)序驅(qū)動(dòng)的布線算法。目前最流行的基本算法是擁擠度和延時(shí)兼顧的路徑搜索算法［5］（Path finder），它采用了一種使用連線關(guān)鍵度控制連線擁擠度和延時(shí)兼顧的折中方法。也就是，時(shí)序關(guān)鍵的線網(wǎng)使用延時(shí)最短的路徑進(jìn)行布線，即使這是一條擁擠路徑，而時(shí)序不關(guān)鍵的線網(wǎng)將占有不擁擠的長(zhǎng)路徑。

路徑搜索算法反復(fù)地拆線，重布電路中的各條線網(wǎng)，直到所有的擁擠度問(wèn)題都得到解決。每次重布電路中的一條線網(wǎng)，就稱為一次布線迭代。在第一次布線迭代中，每條連線均已最小延時(shí)為目標(biāo)進(jìn)行布線，即使會(huì)導(dǎo)致布線資源的擁擠或重用。重用的布線資源是無(wú)效的，一根線不可能被兩個(gè)不同的線網(wǎng)使用。因此，一次布線迭代后存在重用，必須再執(zhí)行一次，直到解決擁擠問(wèn)題。每次布線迭代之后都要增加重用布線資源的成本，從而解決布線擁擠問(wèn)題。每次布線迭代后，都可能得到完整的但是可能無(wú)效的布線結(jié)果。因此，能從這次布線中確定線網(wǎng)的延時(shí)，并且進(jìn)行完整的時(shí)序分析以計(jì)算各源點(diǎn)和漏點(diǎn)間的延時(shí)裕量。在下一輪布線迭代中，這些裕量就可以用于控制減少連線延時(shí)或避免擁擠度的力度。

從線網(wǎng)的源端i到漏端j的連線關(guān)鍵度定義為

公式（1）中，Dmax是電路關(guān)鍵路徑的延時(shí)，slack（i，j）是在不影響電路關(guān)鍵路徑前提下的延時(shí)裕量。因此Crit（i，j）的值介于0和1之間。把布線資源節(jié)點(diǎn)n作為（i，j）的部分連接的成本是：

公式（2）中第一項(xiàng)是延時(shí)項(xiàng)，是這條連接的關(guān)鍵度乘以該節(jié)點(diǎn)的自身延時(shí)。第二項(xiàng)是擁擠度項(xiàng)。b（n）是節(jié)點(diǎn)n的基本成本。h（n）是節(jié)點(diǎn)n的歷史擁擠度成本，每次節(jié)點(diǎn)n被重用，h（n）就會(huì)增加，布線器會(huì)保留“擁擠記錄”。p（n）是節(jié)點(diǎn)n的當(dāng)前擁擠度成本，如果在一次布線迭代中，該節(jié)點(diǎn)只被使用一次，p（n）就為1，它隨著節(jié)點(diǎn)重用次數(shù)的增加而增加。p（n）也是已經(jīng)運(yùn)行的布線迭代次數(shù)的函數(shù)：在初始迭代中，p（n）隨著當(dāng)前節(jié)點(diǎn)n的重用緩慢增加，在末期迭代中，p（n）隨著節(jié)點(diǎn)n的重用迅速增加［1］。

路徑搜索器的優(yōu)越性主要?dú)w功于兩方面的創(chuàng)新，包括允許布線資源的重用，通過(guò)成本函數(shù)使得擁擠度逐步得到解決，并且直接優(yōu)化時(shí)序。隨著布線迭代次數(shù)的增加，位于關(guān)鍵路徑上的連接占用最快路徑，而非關(guān)鍵路徑避免使用重用連接并逐步占用慢速路徑。

直接搜索算法又稱A*算法［6］，是人工智能中一種典型的啟發(fā)式搜索算法。啟發(fā)式搜索就是在狀態(tài)空間中的搜索對(duì)每一個(gè)搜索位置（節(jié)點(diǎn)）進(jìn)行評(píng)估，得到認(rèn)為最好的位置，再?gòu)倪@個(gè)位置進(jìn)行搜索直到目標(biāo)。這樣可以省略大量無(wú)謂的搜索路徑，提高了效率。在啟發(fā)式搜索中，對(duì)位置的估價(jià)是十分重要的。采用不同的估價(jià)可以有不同的效果。

路徑搜索算法的啟發(fā)式搜索算法改進(jìn)算法可以在不影響布線質(zhì)量的前提下，快速提高運(yùn)行布線速度。這是通過(guò)在節(jié)點(diǎn)成本中加入了對(duì)節(jié)點(diǎn)到目標(biāo)漏端預(yù)期成本的方法實(shí)現(xiàn)的。具體將在時(shí)序驅(qū)動(dòng)布線算法中詳細(xì)介紹。

2.2 反熔絲FPGA延時(shí)模型

FPGA中線網(wǎng)延時(shí)包括邏輯塊的內(nèi)部延時(shí)和連接延時(shí)。在本延時(shí)模型中分別對(duì)這兩種延時(shí)采用不同的計(jì)算方法：對(duì)于邏輯塊內(nèi)部，由于其路徑的有限性，可以通過(guò)SPICE模擬仿真得到邏輯塊內(nèi)部所有路徑的延時(shí)；連接線網(wǎng)延時(shí)是FPGA延時(shí)的主要部分。線網(wǎng)延時(shí)是指從線網(wǎng)的源端到該線網(wǎng)的終端之間的延時(shí)，其目的是決定布線后的電路速度、決定布線時(shí)的不同線網(wǎng)拓?fù)浣Y(jié)構(gòu)的延時(shí)。理想情況下，通過(guò)SPICE仿真可以得到精確的仿真值，但是布線線網(wǎng)數(shù)目有成千上萬(wàn)條，用SPICE仿真是不明智的，因此采用在布線中廣泛應(yīng)用的延時(shí)模型Elmore模型［7］。采用Elmore模型進(jìn)行連線延時(shí)計(jì)算時(shí)，對(duì)FPGA布線資源中的傳輸晶體管，緩沖器及金屬線進(jìn)行RC電路的等效替換，以得到布線資源線網(wǎng)的RC樹(shù)（RC Tree）。

反熔絲燒通后其電阻為一個(gè)線性電阻，為雙向?qū)?，且不?huì)隔離下游電容，因此其Elmore延時(shí)模型可用傳輸管模型代替。如圖1（a）為反熔絲等效電路，圖1（b）為輸出緩沖器等效電路，輸出緩沖器具有本征延時(shí)和電阻，且會(huì)隔離下游電阻電容。圖1（c）為布線等效電路。

圖1 Elmore延時(shí)模型

通過(guò)對(duì)緩沖器反熔絲和線建立RC模型后，可以計(jì)算源端到漏端路徑的Elmore延時(shí)是：

RC樹(shù)的Elmore延時(shí)能夠在線性時(shí)間內(nèi)計(jì)算出來(lái)，即使Elmore延時(shí)有點(diǎn)不準(zhǔn)確，它依然有較高的可信度，也就是它仍然能夠?qū)Σ煌牟季€拓?fù)浣Y(jié)構(gòu)電路進(jìn)行正確排序。這個(gè)特征十分有用，它意味著基于Elmore延時(shí)的布線器能夠通過(guò)不同拓?fù)浣Y(jié)構(gòu)的相對(duì)比較而做出正確的排序。

3 反熔絲FPGA布線算法的改進(jìn)

3.1 成本函數(shù)的改進(jìn)

由于在FPGA布線算法中，能夠在FPGA布線資源上布通電路永遠(yuǎn)都處于優(yōu)先考慮的位置，因此在FPGA時(shí)序驅(qū)動(dòng)布線中，我們需要采用延時(shí)和擁擠度綜合考慮算法。在算法中通過(guò)每種連接的擁擠度與延時(shí)折中度來(lái)控制節(jié)點(diǎn)的選取，而每種連接的擁擠度與延時(shí)折中度是由與其關(guān)鍵路徑相比的危險(xiǎn)程度（critical）來(lái)控制的，即關(guān)鍵路徑的連接采用盡可能短的延時(shí)路徑，即使這種情況會(huì)產(chǎn)生其他節(jié)點(diǎn)擁擠度問(wèn)題，而對(duì)非關(guān)鍵路徑的線網(wǎng)就用長(zhǎng)一點(diǎn)卻不會(huì)產(chǎn)生擁擠度問(wèn)題的路徑連接。

考慮時(shí)序的布線算法需要對(duì)節(jié)點(diǎn)Cost進(jìn)行修改，使Cost中包含節(jié)點(diǎn)的時(shí)序信息，以便在布線搜索中優(yōu)先考慮時(shí)延小的節(jié)點(diǎn)，修改后的代價(jià)函數(shù)表達(dá)式如公式（4）。

其中Cost（n）和基于布通率的代價(jià)函數(shù)表達(dá)式一樣，包含節(jié)點(diǎn)的基本代價(jià)、上一次擁擠度、當(dāng)前擁擠度；公式中Dmax為關(guān)鍵路徑時(shí)延，slack（i，j）為第i條線網(wǎng)源與第j個(gè)終節(jié)點(diǎn)的松弛時(shí)間，MaxCrit表示該連接的時(shí)延與擁擠度折中系數(shù)。當(dāng)公式（5）-（7）中的MaxCrit＝1、η＝1時(shí)，這種情況表示具有0松弛時(shí)間，即關(guān)鍵路徑上的連接可以完全忽略擁擠的費(fèi)用，而當(dāng)MaxCrit＝0時(shí)，算法完全忽略所有線網(wǎng)連接延時(shí)，而僅僅考慮擁擠度費(fèi)用，算法就變成了基于布通率的布線算法。經(jīng)驗(yàn)表明，MaxCrit＝0.99比MaxCrit＝l具有更好的布通率且不影響電路延時(shí)；而當(dāng)MaxCrit＝l時(shí)，有兩條關(guān)鍵路徑上的節(jié)點(diǎn)共享一個(gè)節(jié)點(diǎn)，將沒(méi)辦法解決布通率問(wèn)題。

接下來(lái)還要定義一個(gè)路徑成本的概念，路徑費(fèi)用表示已布線資源路徑1到節(jié)點(diǎn)n的成本值總和，其表達(dá)式如公式（6）：

當(dāng)每次找到線網(wǎng)的一個(gè)sink時(shí)，Crit（i，j）和delay（n）都會(huì)發(fā)生變化，因此當(dāng)一個(gè)sink到達(dá)時(shí)對(duì)于優(yōu)先隊(duì)列中存儲(chǔ)的每個(gè)PathCost值都將變得無(wú)效，因此不能采用基于布通率中提到的將已布線路徑上節(jié)點(diǎn)作為下次擴(kuò)展的源節(jié)點(diǎn)，即將所有路徑上節(jié)點(diǎn)Cost設(shè)置為0的方法。因?yàn)樵诨跁r(shí)序驅(qū)動(dòng)的布線算法完成時(shí)，即每當(dāng)一個(gè)sink到達(dá)時(shí)，優(yōu)先隊(duì)列被清空，而不能繼續(xù)作為擴(kuò)展的節(jié)點(diǎn)使用，算法需要重新計(jì)算每個(gè)節(jié)點(diǎn)Cost后再進(jìn)行搜索，這樣會(huì)導(dǎo)致搜索速度變慢。因此在時(shí)序驅(qū)動(dòng)的布線算法中，我們采用直接搜索算法，在每一次節(jié)點(diǎn)擴(kuò)展時(shí)對(duì)節(jié)點(diǎn)進(jìn)行評(píng)估，減小沒(méi)有必要的搜索。

為了在布線中使用直接搜索算法，需要預(yù)計(jì)出從當(dāng)前節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)總共的估計(jì)費(fèi)用值ExpectedCost（n），對(duì)于源節(jié)點(diǎn)和邏輯塊輸出節(jié)點(diǎn)定義其估計(jì)費(fèi)用值為0，因?yàn)橐粭l線網(wǎng)只有一個(gè)源節(jié)點(diǎn)、大多數(shù)情況下輸出節(jié)點(diǎn)在MAZE擴(kuò)展中不需要進(jìn)行嘗試搜索。為計(jì)算ExpectedCost（n），假定：①?gòu)漠?dāng)前節(jié)點(diǎn)n出發(fā)，連接目標(biāo)節(jié)點(diǎn)J，使用與n具有相同類型的可分割線；②沿最短路徑上的各個(gè)節(jié)點(diǎn)不存在擁擠度問(wèn)題，即對(duì)于所有節(jié)點(diǎn)P（m），h（n）均等于1。由于當(dāng)前布線節(jié)點(diǎn)（n）和目標(biāo)節(jié)點(diǎn)（j）都在FPGA芯片資源表示的范圍內(nèi)，通過(guò)計(jì)算連接目標(biāo)節(jié)點(diǎn)和當(dāng)前布線節(jié)點(diǎn)中，所使用的與當(dāng)前節(jié)點(diǎn)具有相同類型的可分割線的總數(shù)，根據(jù)該信息，我們可以計(jì)算出連接兩節(jié)點(diǎn)所使用的所有開(kāi)關(guān)，因此可以計(jì)算出目標(biāo)節(jié)點(diǎn)的Elmore延時(shí)；作為目標(biāo)估計(jì)費(fèi)用，使用如下公式計(jì)算出節(jié)點(diǎn)n的總費(fèi)用。

其中α表示采用直接搜索的程度，α＝0即變成寬度優(yōu)先搜索算法。RT（i）：當(dāng)前處理的線網(wǎng)net（i）中節(jié)點(diǎn)n的集合，同時(shí)儲(chǔ)存了這些節(jié)點(diǎn)的延時(shí)信息。

由于燒通后的反熔絲電阻電容相對(duì)較大，反熔絲型FPGA的線網(wǎng)通路過(guò)的反熔絲不能過(guò)多，最好不超過(guò)三個(gè)反熔絲。雖然反熔絲FPGA所采用的行結(jié)構(gòu)設(shè)計(jì)已經(jīng)很大程度上避免了這個(gè)問(wèn)題，但是實(shí)際隨著電路規(guī)模的增加，線網(wǎng)長(zhǎng)度增加還是很有可能出現(xiàn)這種情況的，因此需要修改布線算法，并加以約束。

在改進(jìn)的反熔絲FPGA布線器中，布線迭代結(jié)束的判斷標(biāo)志不僅是布通與否，也應(yīng)包括有沒(méi)有線網(wǎng)通過(guò)超過(guò)四個(gè)反熔絲。由于布線算法是靠成本函數(shù)來(lái)控制布線資源節(jié)點(diǎn)的選擇，從路徑搜索算法得到的啟發(fā)，因此修改也是基于對(duì)布線資源節(jié)點(diǎn)成本的動(dòng)態(tài)修改來(lái)實(shí)現(xiàn)的。在原來(lái)的成本函數(shù)非時(shí)序成本上乘一個(gè)新的成本因子pass（n），這表明是線網(wǎng)通過(guò)反熔絲的個(gè)數(shù)影響成本。新的成本函數(shù)如公式（8）和公式（9）所示。

因?yàn)檫@是一個(gè)非延時(shí)成本，所以只在非延時(shí)項(xiàng)乘了pass（n），該成本函數(shù)會(huì)實(shí)時(shí)跟蹤當(dāng)前線網(wǎng)擴(kuò)張時(shí)通過(guò)反熔絲的情況。在每次布線之后，布線器還會(huì)記錄每個(gè)線網(wǎng)通過(guò)的反熔絲數(shù)目，下次布線時(shí)根據(jù)線網(wǎng)通過(guò)上次布線的反熔絲數(shù)目和歷史記錄線網(wǎng)通過(guò)反熔絲數(shù)目。公式4-13是pass（n）的表達(dá)式，numpass（n）是當(dāng)前線網(wǎng)通過(guò)反熔絲的數(shù)目，his_ pass（net）是線網(wǎng)布線通過(guò)超過(guò)三次的次數(shù)，如果線網(wǎng)當(dāng)前布線擴(kuò)展通過(guò)的反熔絲數(shù)目越多則numpass（n）越大，這使得布線器選擇通過(guò)反熔絲少的路徑。若上次布線線網(wǎng)通過(guò)反熔絲的數(shù)目越多則pre_pass（net）越大，pass（n）越小，這樣使得通過(guò)反熔絲多的線網(wǎng)使用節(jié)點(diǎn)的成本變小。隨著布線迭代，線網(wǎng)反熔絲通過(guò)數(shù)目超過(guò)三個(gè)的次數(shù)的增加，his_pass（net）會(huì)逐漸增加，pass（n）逐漸減小。這樣讓布線器逐步選擇通過(guò)反熔絲較多的路徑逐漸占用通過(guò)反熔絲少的路徑，即使該路徑很擁擠，以期減少反熔絲的通過(guò)量。

通過(guò)監(jiān)控線網(wǎng)路徑通過(guò)的反熔絲數(shù)目，每次布線迭代時(shí)布線器總是尋找通過(guò)反熔絲少的路徑。這樣在布線迭代中，布線器會(huì)減少盲目的布線擴(kuò)展，因?yàn)橥ㄟ^(guò)反熔絲太多的線網(wǎng)是不會(huì)被采用的。這在很多情況下會(huì)大大提高軟件的布線速度，因?yàn)椴季€擴(kuò)展是非常耗時(shí)的，尤其當(dāng)FPGA規(guī)模很大的時(shí)候。

3.2 線網(wǎng)布線順序的改進(jìn)

根據(jù)布線算法的普遍研究和實(shí)驗(yàn)［1］，線網(wǎng)布線順序?qū)Σ季€結(jié)果的影響很大。這是因?yàn)椴季€資源節(jié)點(diǎn)存在一個(gè)重用成本的問(wèn)題，布線資源節(jié)點(diǎn)被線網(wǎng)使用后，成本就會(huì)變高。因此將通過(guò)反熔絲數(shù)目多的線網(wǎng)先布線，會(huì)減少通過(guò)的反熔絲數(shù)目。因此程序必須在每次布線迭代之后都要記錄下每條線網(wǎng)通過(guò)的反熔絲數(shù)目，并在下一次布線時(shí)對(duì)線網(wǎng)進(jìn)行排序。同樣對(duì)于存在多扇出的線網(wǎng)，扇出的線網(wǎng)布線順序不同對(duì)布線結(jié)果也是有影響的，因此改進(jìn)的布線算法也記錄下了線網(wǎng)的不同扇出所經(jīng)過(guò)的反熔絲。在對(duì)每條線網(wǎng)布線時(shí)，布線器根據(jù)不同扇出所經(jīng)過(guò)的反熔絲數(shù)目，對(duì)其進(jìn)行排序，將經(jīng)過(guò)反熔絲數(shù)目多的扇出進(jìn)行優(yōu)先布線，這也大大減少了線網(wǎng)經(jīng)過(guò)的反熔絲數(shù)。

3.3 實(shí)驗(yàn)結(jié)果

為了驗(yàn)證改進(jìn)算法的可行性，本文提出了一個(gè)4×8的行結(jié)構(gòu)反熔絲FPGA，借助反熔絲FPGA CAD平臺(tái)進(jìn)行布線實(shí)驗(yàn)。圖2是全加器電路在實(shí)驗(yàn)FPGA布線完成后的圖形顯示，通過(guò)圖形顯示可以很清楚的看到關(guān)鍵路徑可以方便電路設(shè)計(jì)者修改電路提高速度。四組對(duì)比實(shí)驗(yàn)結(jié)果表明，修改后的算法布線速度平均提高20%，電路速度平均提高了15%（見(jiàn)表1）。

圖2 全加器布線結(jié)果

表1 四組測(cè)試電路布線結(jié)果

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

首先介紹了學(xué)術(shù)界流行的FPGA布線算法，包括其主要思想和實(shí)現(xiàn)方式，還闡述了成本函數(shù)的選擇和關(guān)鍵路徑的分析。為了進(jìn)行時(shí)序驅(qū)動(dòng)布線，又對(duì)布線結(jié)果進(jìn)行時(shí)序分析，提出了反熔絲FPGA的時(shí)序模型。根據(jù)反熔絲FPGA的特點(diǎn)，對(duì)傳統(tǒng)布線算法的成本函數(shù)和布線速度進(jìn)行了修改，以促進(jìn)布線器盡量減少線網(wǎng)中的反熔絲數(shù)目并提高布線速度。最后，在反熔絲FPGA CAD實(shí)驗(yàn)平臺(tái)實(shí)現(xiàn)了改進(jìn)布線算法，成功對(duì)四組實(shí)驗(yàn)電路進(jìn)行了布線。實(shí)驗(yàn)結(jié)果表明這些改進(jìn)可以大幅提高布線的效率和電路速度。本文所提出的改進(jìn)還需要更多的理論和實(shí)驗(yàn)研究來(lái)驗(yàn)證，特別是需要提高實(shí)驗(yàn)FPGA的規(guī)模以對(duì)更多典型電路進(jìn)行測(cè)試。

［1］Vaughn B，Jonathan R，Alexander M.Architecture and CAD for deep-submicron FPGAs［M］.US，springer，1999：10-50.

［2］Jonathon G，Esmat H，Sam B.Antifuse field programmable gate arrays［J］.Proceedings of the IEEE，1993.

［3］Actel Corporation，Introduction to ACTEL FPGA architecture［J］.Application Note AC165，1997.

［4］Carl E，Larry MM，Scott H.Placement and routing tools for the Triptych FPGA［J］.IEEE Transactions on VLSI Systems，Department of Computer Science and Engineering，University ofWashington，Seattle，1995.

［5］Larry MM，Carl E.PathFinder：A Negotiation-Based Performance-Driven Router for FPGAs［C］.Third International ACM Symposium on Field-Programmable Gate Arrays（FPGA＇95），Monterey，California，USA，1995.

［6］Russell T.Negotiated A*routing for FPGAs*［J］.The Fifth Canadian Workshop on Field-Programmable Devices，MIT Laboratory for Computer Science Cambridge，1998.

［7］Wang Y，Wang L，Han R.A delay model for SRAMBased FPGA interconnections［J］.49th IEEE International Midwest Symposium on，2006.

Research on the Routing Algorithm of Antifuse FPGA

YANG Da-wei
（The 47th Research Institute of China Electronics Technology Group Corporation，Shenyang 110032，China）

Routing algorithm based on SRAM FPGA is very popular in the academia，however the special antifuse FPGA is rarely discussed.This paper presents the current status of the development of antifuse FPGA and its routing algorithm.Then fundamental principles and implementationmethods of the most popular Pathfinder routing algorithm are discussed，and the antifuse FPGA delay models are also introduced.Afterward two improvements of the algorithm targeting antifuse FPGA are described，and the modified algorithm is realized in the antifuse CAD platform.The result of several experiments shows that themodified algorithm can optimize routing efficiency and circuit speed implemented on antifuse FPGA.

Antifuse；Path finder；Routing algorithm；FPGA

10.3969／j.issn.1002-2279.2014.01.013

TN4

：A

：1002-2279（2014）01-0046-05

總裝“核高基”重大專項(xiàng)：高可靠反熔絲FPGA設(shè)計(jì)技術(shù)研究

楊大為（1977-），男（回族），山東省濟(jì)陽(yáng)縣人，高級(jí)工程師，主研方向：集成電路設(shè)計(jì)。

2013-08-26