反熔絲FPGA布線算法研究?

楊大為

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

反熔絲FPGA布線算法研究?

楊大為

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

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

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

1 引 言

FPGA（現場可編程門陣列）是與CPU和DSP并列的目前半導體市場上最重要的三類核心數字器件之一。自從上世紀80年代中期被發明出來以后，它對電子產業產生的影響越來越大。根據編程結構，FPGA可分為三種，分別是基于SRAM、FLASH和反熔絲（antifuse）的FPGA［1-4］。

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

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

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

2 反熔絲FPGA布線算法

2.1 基本布線算法

常見的FPGA布線器可以分為兩大類［1］，其中一種是全局兼詳細組合布線，這種布線方式一步就可以完成FPGA的布線。另一種方法是分為兩步實現布線：第一步運行全局布線決定每條線網所使用的每個邏輯單元的引腳和可以使用的可分割線通道，第二步運行詳細布線，根據第一步的結果，在允許使用的可分割通道中連接各個線網。因為FPGA布線的靈活性有限，并且全局布線限制了各線網所能使用的通道線段，所以FPGA詳細布線器經常不能或者很困難地完成布線任務。因為全局兼詳細布線器能夠避免這種限制，所以它能更好的優化布線。

迷宮布線器用來連接各條線網的各個終點，而迷宮布線器其核心又是采用Dijkstra算法，即在布線資源圖［4］中尋找連接線網源端和漏端的最短路徑（最小成本）。在各種算法中，為了衡量布線結果的好壞而提出成本函數（Cost Function）［1］的概念，通常值越低表示布線結果越好，而對于不同的布線優先目標，成本函數也相應不同。

因為FPGA電路的速度很重要，所以我們主要研究有關時序驅動的布線算法。目前最流行的基本算法是擁擠度和延時兼顧的路徑搜索算法［5］（Path finder），它采用了一種使用連線關鍵度控制連線擁擠度和延時兼顧的折中方法。也就是，時序關鍵的線網使用延時最短的路徑進行布線，即使這是一條擁擠路徑，而時序不關鍵的線網將占有不擁擠的長路徑。

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

從線網的源端i到漏端j的連線關鍵度定義為

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

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

路徑搜索器的優越性主要歸功于兩方面的創新，包括允許布線資源的重用，通過成本函數使得擁擠度逐步得到解決，并且直接優化時序。隨著布線迭代次數的增加，位于關鍵路徑上的連接占用最快路徑，而非關鍵路徑避免使用重用連接并逐步占用慢速路徑。

直接搜索算法又稱A*算法［6］，是人工智能中一種典型的啟發式搜索算法。啟發式搜索就是在狀態空間中的搜索對每一個搜索位置（節點）進行評估，得到認為最好的位置，再從這個位置進行搜索直到目標。這樣可以省略大量無謂的搜索路徑，提高了效率。在啟發式搜索中，對位置的估價是十分重要的。采用不同的估價可以有不同的效果。

路徑搜索算法的啟發式搜索算法改進算法可以在不影響布線質量的前提下，快速提高運行布線速度。這是通過在節點成本中加入了對節點到目標漏端預期成本的方法實現的。具體將在時序驅動布線算法中詳細介紹。

2.2 反熔絲FPGA延時模型

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

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

圖1 Elmore延時模型

通過對緩沖器反熔絲和線建立RC模型后，可以計算源端到漏端路徑的Elmore延時是：

RC樹的Elmore延時能夠在線性時間內計算出來，即使Elmore延時有點不準確，它依然有較高的可信度，也就是它仍然能夠對不同的布線拓撲結構電路進行正確排序。這個特征十分有用，它意味著基于Elmore延時的布線器能夠通過不同拓撲結構的相對比較而做出正確的排序。

3 反熔絲FPGA布線算法的改進

3.1 成本函數的改進

由于在FPGA布線算法中，能夠在FPGA布線資源上布通電路永遠都處于優先考慮的位置，因此在FPGA時序驅動布線中，我們需要采用延時和擁擠度綜合考慮算法。在算法中通過每種連接的擁擠度與延時折中度來控制節點的選取，而每種連接的擁擠度與延時折中度是由與其關鍵路徑相比的危險程度（critical）來控制的，即關鍵路徑的連接采用盡可能短的延時路徑，即使這種情況會產生其他節點擁擠度問題，而對非關鍵路徑的線網就用長一點卻不會產生擁擠度問題的路徑連接。

考慮時序的布線算法需要對節點Cost進行修改，使Cost中包含節點的時序信息，以便在布線搜索中優先考慮時延小的節點，修改后的代價函數表達式如公式（4）。

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

接下來還要定義一個路徑成本的概念，路徑費用表示已布線資源路徑1到節點n的成本值總和，其表達式如公式（6）：

當每次找到線網的一個sink時，Crit（i，j）和delay（n）都會發生變化，因此當一個sink到達時對于優先隊列中存儲的每個PathCost值都將變得無效，因此不能采用基于布通率中提到的將已布線路徑上節點作為下次擴展的源節點，即將所有路徑上節點Cost設置為0的方法。因為在基于時序驅動的布線算法完成時，即每當一個sink到達時，優先隊列被清空，而不能繼續作為擴展的節點使用，算法需要重新計算每個節點Cost后再進行搜索，這樣會導致搜索速度變慢。因此在時序驅動的布線算法中，我們采用直接搜索算法，在每一次節點擴展時對節點進行評估，減小沒有必要的搜索。

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

其中α表示采用直接搜索的程度，α＝0即變成寬度優先搜索算法。RT（i）：當前處理的線網net（i）中節點n的集合，同時儲存了這些節點的延時信息。

由于燒通后的反熔絲電阻電容相對較大，反熔絲型FPGA的線網通路過的反熔絲不能過多，最好不超過三個反熔絲。雖然反熔絲FPGA所采用的行結構設計已經很大程度上避免了這個問題，但是實際隨著電路規模的增加，線網長度增加還是很有可能出現這種情況的，因此需要修改布線算法，并加以約束。

在改進的反熔絲FPGA布線器中，布線迭代結束的判斷標志不僅是布通與否，也應包括有沒有線網通過超過四個反熔絲。由于布線算法是靠成本函數來控制布線資源節點的選擇，從路徑搜索算法得到的啟發，因此修改也是基于對布線資源節點成本的動態修改來實現的。在原來的成本函數非時序成本上乘一個新的成本因子pass（n），這表明是線網通過反熔絲的個數影響成本。新的成本函數如公式（8）和公式（9）所示。

因為這是一個非延時成本，所以只在非延時項乘了pass（n），該成本函數會實時跟蹤當前線網擴張時通過反熔絲的情況。在每次布線之后，布線器還會記錄每個線網通過的反熔絲數目，下次布線時根據線網通過上次布線的反熔絲數目和歷史記錄線網通過反熔絲數目。公式4-13是pass（n）的表達式，numpass（n）是當前線網通過反熔絲的數目，his_ pass（net）是線網布線通過超過三次的次數，如果線網當前布線擴展通過的反熔絲數目越多則numpass（n）越大，這使得布線器選擇通過反熔絲少的路徑。若上次布線線網通過反熔絲的數目越多則pre_pass（net）越大，pass（n）越小，這樣使得通過反熔絲多的線網使用節點的成本變小。隨著布線迭代，線網反熔絲通過數目超過三個的次數的增加，his_pass（net）會逐漸增加，pass（n）逐漸減小。這樣讓布線器逐步選擇通過反熔絲較多的路徑逐漸占用通過反熔絲少的路徑，即使該路徑很擁擠，以期減少反熔絲的通過量。

通過監控線網路徑通過的反熔絲數目，每次布線迭代時布線器總是尋找通過反熔絲少的路徑。這樣在布線迭代中，布線器會減少盲目的布線擴展，因為通過反熔絲太多的線網是不會被采用的。這在很多情況下會大大提高軟件的布線速度，因為布線擴展是非常耗時的，尤其當FPGA規模很大的時候。

3.2 線網布線順序的改進

根據布線算法的普遍研究和實驗［1］，線網布線順序對布線結果的影響很大。這是因為布線資源節點存在一個重用成本的問題，布線資源節點被線網使用后，成本就會變高。因此將通過反熔絲數目多的線網先布線，會減少通過的反熔絲數目。因此程序必須在每次布線迭代之后都要記錄下每條線網通過的反熔絲數目，并在下一次布線時對線網進行排序。同樣對于存在多扇出的線網，扇出的線網布線順序不同對布線結果也是有影響的，因此改進的布線算法也記錄下了線網的不同扇出所經過的反熔絲。在對每條線網布線時，布線器根據不同扇出所經過的反熔絲數目，對其進行排序，將經過反熔絲數目多的扇出進行優先布線，這也大大減少了線網經過的反熔絲數。

3.3 實驗結果

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

圖2 全加器布線結果

表1 四組測試電路布線結果

4 結束語

首先介紹了學術界流行的FPGA布線算法，包括其主要思想和實現方式，還闡述了成本函數的選擇和關鍵路徑的分析。為了進行時序驅動布線，又對布線結果進行時序分析，提出了反熔絲FPGA的時序模型。根據反熔絲FPGA的特點，對傳統布線算法的成本函數和布線速度進行了修改，以促進布線器盡量減少線網中的反熔絲數目并提高布線速度。最后，在反熔絲FPGA CAD實驗平臺實現了改進布線算法，成功對四組實驗電路進行了布線。實驗結果表明這些改進可以大幅提高布線的效率和電路速度。本文所提出的改進還需要更多的理論和實驗研究來驗證，特別是需要提高實驗FPGA的規模以對更多典型電路進行測試。

［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

總裝“核高基”重大專項：高可靠反熔絲FPGA設計技術研究

楊大為（1977-），男（回族），山東省濟陽縣人，高級工程師，主研方向：集成電路設計。

2013-08-26