SRAM型FPGA抗多位翻轉布線算法

張 碩，伊小素，朱明達，張家銘

（北京航空航天大學 光電技術研究所，北京 100191）

現場可編門陣列（field programmable gate array，FPGA）因其具有信息密度大、性能高、開發成本低、可重復編程等特性，受到航天電子方面設計者青睞，空間運用越來越多［1］。然而在復雜的空間輻射環境中，由于FPGA對輻射的潛在敏感性，易引發單粒子翻轉（SEUs）［2］，甚至可能造成系統失效［3－4］。目前，比較有效的減緩SEUs的方法是采用帶刷新的分層TMR結構［5－6］。在之前的研究中，我們發現這種結構只能增強系統對獨立多位單粒子翻轉（multiple independent upsets，MIUs）的容錯能力，對于 MCUs（單粒子撞擊造成的多位翻轉）無法有效地進行防護。

本文提出一組全新的基于FPGA底層資源的布線條件約束。將這種算法運用到FPGA布局布線中，可以有效地減少MCUs，提高系統的可靠性。

1 多位翻轉效應

FPGA內部為了提高信號傳輸質量和面積利用率，采用了特殊設計的線型和開關矩陣。FPGA內的線型有 Long Lines、Hex Lines、Double Lines、Direct Connection和Fast Connects等，這些互連線通過可編程互聯點（PIPs）和SLICE的輸入輸出緩沖器實現了FPGA內部功能模塊、開關矩陣、IOB等多種資源的高速連接［7］。

FPGA的布線資源按照其可配置性分為固有資源（如各種連接線）和可編程布線資源（如開關矩陣和PIPs，PIPs包括可編程互聯點和開關矩陣的頂點）等。相同邏輯的功能模塊由于可編程布線資源的配置不同，可以有不同的布線實現方法。

每當發生多位翻轉現象時，都影響到多個FPGA的配置存儲單元，這對于防護單個錯誤的冗余設計造成了很大的沖擊。在之前很多學者都對Xilinx FPGA［8］中發生多位翻轉的概率進行了大量的研究工作。實驗證明：98%的多位翻轉發生在FPGA的配置存儲位，并會影響到周圍多個存儲單元，有一些特定因素會增加2到3倍的多位翻轉的敏感性?？紤]到配置存儲單元的排列方式（它是由一個全是配置單元的矩陣組成的），可以通過對一個集簇中的相鄰配置存儲位進行分析來對多位翻轉的影響進行研究，如圖1所示。單粒子可能撞擊到屬于不同FPGA資源的不同邏輯部分，如圖2所示，例如BRAMs（s表示多數，下同），BRAM的互聯點IO Blocks以及CLBs。每個配置位幀控制著一塊資源，這塊資源對應著一列的SRAM FPGA的配置位信息［9］。CLB組成了FPGA的邏輯核心。它們包含一系列的結構元素，每個結構元素都包含一個轉化矩陣和一系列的邏輯元素，如圖3所示。更詳細地說，一個單獨的CLB可以通過編程配置存儲位來實現任何的連續的或是有關聯的邏輯功能，具體能夠實現多少功能是通過可用資源的間隔尺度來確定的。

圖1 多位翻轉發生在臨近的單元里

圖2 FPGA的配置存儲位的普通結構形式

圖3 Virtex－II系列的FPGA詳細的CLB信息

邏輯資源包含在基本的邏輯元素中，主要有LUTs和FFs。他們建立了邏輯元素和轉換矩陣之間的連接，或是轉換矩陣與轉換矩陣之間的連接。配置存儲位控制著可編程邏輯資源，1個CLB由1個矩陣的位數組成，這些位數與一些其他的資源，比如LUTs、FFs、PIPs都有關聯。因此，依靠發生多位翻轉的方向（單個列上，單個行上或是對角線相鄰的元素上），這種多位翻轉效應會同時影響到1個單獨位置或是2個配置存儲位相鄰的位置的資源情況。依賴于FPGA所采取的硬件技術，這種影響多個資源的效應會隨著電路的邏輯進行傳播。在冗余技術中，例如三模冗余（TMR），電路包含多個表決器的部分。表決器存在于邏輯和布線資源中，由幾個表決器之間的結構組成?？紤]到圖4中的電路策略，一個表決器存在于邏輯和布線資源中，屬于域Di（i＝1，2，3），Di存在于表決器Vi和Vi＋1之間。表決器部分可能會帶來多位翻轉效應的故障傳遞。更詳細地說，當發生多位翻轉時，可能會影響2個以上的單元。

（1）多位翻轉產生的錯誤繞過表決器結構繼續向深處傳輸，表決器的輸出對于故障沒有產生屏蔽作用，如圖4所示。

圖4 發生在表決器位置的多位翻轉導致三模冗余TMR失效

（2）當發生錯誤的資源屬于不同的域中時，多位翻轉所產生的錯誤就會被表決器結構所掩蓋，如圖5所示。

圖5 多位翻轉錯誤被三模冗余TMR掩蓋

2 減少MCUs有效的約束條件

單粒子效應故障在FPGA各類功能模塊中的分布情況如表1所示。

表1 XCVIOOO各類模塊的單粒子效應截面比例

從翻轉的比例來看，配置存儲器所占的比例最大，其次為LUT型的RAM、BRAM和觸發器?？梢?，FPGA單粒子效應故障絕大多數是由配置存儲器的翻轉引起的，配置存儲器的翻轉是FPGA單粒子效應故障的最主要表現形式。配置存儲器的內容決定了FPGA設計中各功能模塊的功能與狀態。配置存儲器中布線資源約占78%～84.8%，控制位和查找表位約占15%～21%，其他資源所占的比重不超過2%。由此可見，配置存儲器出現故障主要引起布線資源的錯誤；也就是說，在布局布線中，使用的布線資源越多，它所對應的配置存儲器的信息就越多，若發生多位翻轉，存儲器真正有意義的存儲位出現錯誤的概率就越高。因此，布局布線中盡量少地使用布線資源是減少配置存儲器錯誤的有效方法。

（1）措施一：較少使用布線資源的最直接方法是減少布線的長度，即使布線資源中連接線網源端和漏端的路徑最短（整體成本最低）。同時，可以通過多次布線迭代來解決布線資源的競爭。布線的路徑的長短體現在信號在路徑上的延時。在布線中，每次拆除重布點的一條線網，就成為一次布線迭代。在第一次布線迭代中，每條連線均以最小延時的目標進行布線，試試是否會導致布線資源的擁擠或重用。重用布線資源的電路布線是無效的，例如，1根線段被2個不同的線網所使用。因此，如果在一次布線迭代后存在重用，那么一定要再執行一次（或者更多）布線迭代才解決擁擠問題。在每次布線迭代之后，都要增加重用布線資源的成本，從而提高解決擁擠問題的可能性。每次布線迭代后，可能得到無效的布線結果。因此，能從這次布線中確定線網的延時，并且進行完整的時序分析、計算各源點和漏點之間的延時裕量。在下一輪布線迭代中，這些裕量就用于控制減少連線延時或避免擁擠。

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

式中，tmac是電路關鍵路徑的延時，slack（i，j）是在不影響電路關機路徑前提下的延時裕量。因此Crit（i，j）的值介于0和1之間。

把布線資源節點n作為（i，j）的部分連接的成本是

式中：第1項是延時項，關鍵度Crit（i，j）乘以該結點的自身延時delay（n）；第2項是擁擠度項。第2項中：b（n）是結點n的基本成本；h（n）是結點n的歷史擁擠度，每次結點n被重用，h（n）就增加，并且布線器會保存“擁擠記錄”；p（n）是結點n的當前擁擠度成本，如果使用這個結點對當前連接布線不會造成任何重用，p（n）就為1，它隨著結點重用次數的增加而增加，p（n）也是已運行的布線迭代次數的函數。

（2）措施二：出現MCUs的根源在于兩個重要模塊超越了安全的集合布線間隔，致使單個單粒子故障在空間上表現為相鄰功能模塊的同時故障［10－11］。針對這個問題研究解決方法。設：

V為可編程布線單元的集合，Vi表示可編程的布線資源，即開關矩陣和PIPs的集合，且Vc滿足：?bc∈B，存在Vc∈V，為bc布線所需的可編程布線資源的集合，且：

SMc和PIPc分別是功能模塊b對應的開關矩陣和PIPs的集合，其元素個數分別為KSMc和KPIPc，即：

布線抑制算法的目標是使關鍵功能模塊集B對應的可編程布線資源集V滿足：

其中符號‖·‖表示PIPc、PIPd在布線時的最小幾何間隔，‖·‖＞1表示兩者布線完成之后幾何域上不相鄰。

式（6）和（7）從較輕松的程度限定了關鍵模塊集B中的任2個元素在布線時的策略，即開關矩陣（SM）不能共用，可編程互聯點（PIPs）不能相鄰。

3 減緩多位翻轉布線算法

（1）針對方法一提出的約束，算法如下：

在算法結束之后，路徑搜索已經完成。

（2）針對措施二提出的約束，算法如下：

／＊根據約束條件建立狀態數據集合ST，用以標識SM和PIPs的相鄰狀態＊／

for（c＝0；c＜K；c＋＋）｛

分析V是否滿足要求，如果V不滿足要求

如果V滿足要求：保存狀態，退出。

4 實驗分析

算法的好壞和有效性通過對電路的最終布線情況進行分析來評估。主要包括2個方面：一是布線的時間，時間越短，說明傳輸延遲越小，且布線時所用線長越短，布線資源使用的就越少，因此就越能夠減少MCUs發生的可能性；二是對CLB之間的連接盒（Switch Box）進行分析。在Switch Box上的布線，在每個連接點（多條連線相交的點）上連線的間隔是衡量MCUs的一個重要指標，當離子撞擊到連接點時，多個布線之間夾角的角度越大，發生MCUs的可能性就越低。

我們采用目前最先進的VTR布局布線工具作為電路布局布線的平臺，通過修改其中的布線部分的代碼實現了上述提出的算法。有些采用了標準API程序，具體見文獻［12－15］。

圖6和圖7分別為使用算法前和使用算法后的布線結果，使用算法前后布線延時比較見表2。

MCUs產生的根本原因是由于布線的幾何間隔過小。通過利用本算法進行布線可以明顯看出，使用算法后的布線圖使得連接點之間連線的距離明顯增大，而且每個點的連線數量減少。這主要是因為本算法通過充分利用周圍沒使用的布線資源，使在同一點的連線盡可能地分布到其他的位置，連接點之間幾何間隔增大以及每個連接點上的連線減少從根本上減少了發生MCUs的可能性。

圖6 應用本算法前布線圖

圖7 應用本算法后布線圖

表2 使用算法前和使用算法后的布線延時比較

從表2可知，布線延時從137.0ns減少到54.2ns。由于布線延遲和線長成線性關系，線長與發生MCUs的概率成線性關系，可知，布線延遲減少至54.2ns產生的效果是MCUs的發生概率減少了2.52倍。

5 結論

采用帶刷新分層的TMR技術并不能有效解決MCUs，因此在本文中提出的布線算法主要是針對SEU中的MCUs效應。采用本算法進行布線設計，減少了傳輸延時，增大了布線的集合間隔，使FPGA中的功能模塊分布更加分散。實驗結果表明，本文算法可以從根本上減少MCUs發生的幾率。將此項技術與帶刷新分層的TMR技術結合，可大大減少MCUs發生的可能性。

（References）

［1］Fernanda L K，Luigi C，Ricardo R.Fault－tolerance techniques for SRAM－based FPGAs［M］.Translated by Yang Fengfei，Gong Jian，Wen Liang，et al.Beijing：China’s Space Press，2009：1－8.

［2］Michael Wirthlin，Eric Johnson，Nathan Rollins.The Reliability of FPGA Circuit Designs in the Presence Of Radiation Induced Configuration Upsets［R］／／IEEE Symosiumon Field－Programmable Custom Computing Machines，Napa，CA，USA，2003.

［3］Srour J R，McGarrity J M.Radiation effects on microelectronics in space［J］.proceedings of the IEEE，1988，76（11）：1443－1469.

［4］楊士元.數字系統的故障診斷與可靠性分析［M］.北京：清華大學出版社，2000：246－266.

［5］Philippe Adell，Greg Allen.Assessing and Mitigating Radiation Effects in Xilinx FPGAs［EB／OL］.Jet Propulsion Laboratory，California Institute of Technology，Pasadena，California，2008.http：／／trs－new.jpl.nasa.gov／dspace／bitstream／2014／40763／1／08－09.pdf.

［6］孫吉利，張平.基于FPGA的星載計算機自檢EDAC電路設計［J］.微計算機信息，2009，25（8）：131－133.

［7］Xilinx Inc.Virtex－II Platform FPGAs：Complete Data Sheet（DS031，V3.4）［M］.Xilinx Inc，2005.

［8］Quinn H，Graham P，Krone J，et al.Radiation－Induced Multi－Bit Upsets in SRAM－based FPGAs［J］.IEEE Transactions on Nuclear Science，2005，52（6）：2455－2461.

［9］Bridgford B，Carmichael C，Tseng C W.Correcting Single－Event Upsets in Virtex－II Platform FPGA Configuration Memory［M］.Xilinx Application Notes，XAPP779，2007.

［10］Ceschia M，Violante M，Reorda M S.Identification and Classification of Single－Event Up Sets in the Configuration Memory of SRAM－based FPGAs［J］.IEEE Transactions on Nuclear Science，2000，50（6－1）：2088－2094.

［11］Kastensmidt F L，Sterpone L，Carro L.On the Optimal Design of Triple Modular Redundancy Logic for SRAM－based FPGAs［J］.Automation and Test in Europe，2005（2）：1290－1295.

［12］Xilinx Inc.Virtex－II Platform FPGAs User Guide（UG002v2.0）［M］.Xilinx Inc，2005.

［13］Andres Upegui，Eduardo Sanchez.Evolving Hardware by Dynamically Reconfiguring Xilinx FPGAs［C］／／in International Conference on Evolvable Systems（ICES 05）.Sitges－Spain，2005.

［14］Yana Krasteva E，Didier Joly，E de la Torre，et al.Virtex－II Bitstream Manipulation：Application to Reconfiguration Control Systems［C］／／in 16th IEEE International Conference on Field Programmable Logic and Applications Madrid.Spain，2006.

［15］Violante M，Ceschia M，Sonza R M，et al.Analyzing SEU Effects in SRAM－based FPGAs［C］／／in Proceedings of 9th IEEE International On－Line Testing Symposium（IOLTS 2003）.2003：119－123.