張 碩，伊小素，朱明達(dá)，張家銘

（北京航空航天大學(xué) 光電技術(shù)研究所，北京 100191）

現(xiàn)場(chǎng)可編門陣列（field programmable gate array，F(xiàn)PGA）因其具有信息密度大、性能高、開(kāi)發(fā)成本低、可重復(fù)編程等特性，受到航天電子方面設(shè)計(jì)者青睞，空間運(yùn)用越來(lái)越多［1］。然而在復(fù)雜的空間輻射環(huán)境中，由于FPGA對(duì)輻射的潛在敏感性，易引發(fā)單粒子翻轉(zhuǎn)（SEUs）［2］，甚至可能造成系統(tǒng)失效［3－4］。目前，比較有效的減緩SEUs的方法是采用帶刷新的分層TMR結(jié)構(gòu)［5－6］。在之前的研究中，我們發(fā)現(xiàn)這種結(jié)構(gòu)只能增強(qiáng)系統(tǒng)對(duì)獨(dú)立多位單粒子翻轉(zhuǎn)（multiple independent upsets，MIUs）的容錯(cuò)能力，對(duì)于 MCUs（單粒子撞擊造成的多位翻轉(zhuǎn)）無(wú)法有效地進(jìn)行防護(hù)。

本文提出一組全新的基于FPGA底層資源的布線條件約束。將這種算法運(yùn)用到FPGA布局布線中，可以有效地減少M(fèi)CUs，提高系統(tǒng)的可靠性。

1 多位翻轉(zhuǎn)效應(yīng)

FPGA內(nèi)部為了提高信號(hào)傳輸質(zhì)量和面積利用率，采用了特殊設(shè)計(jì)的線型和開(kāi)關(guān)矩陣。FPGA內(nèi)的線型有 Long Lines、Hex Lines、Double Lines、Direct Connection和Fast Connects等，這些互連線通過(guò)可編程互聯(lián)點(diǎn)（PIPs）和SLICE的輸入輸出緩沖器實(shí)現(xiàn)了FPGA內(nèi)部功能模塊、開(kāi)關(guān)矩陣、IOB等多種資源的高速連接［7］。

FPGA的布線資源按照其可配置性分為固有資源（如各種連接線）和可編程布線資源（如開(kāi)關(guān)矩陣和PIPs，PIPs包括可編程互聯(lián)點(diǎn)和開(kāi)關(guān)矩陣的頂點(diǎn)）等。相同邏輯的功能模塊由于可編程布線資源的配置不同，可以有不同的布線實(shí)現(xiàn)方法。

每當(dāng)發(fā)生多位翻轉(zhuǎn)現(xiàn)象時(shí)，都影響到多個(gè)FPGA的配置存儲(chǔ)單元，這對(duì)于防護(hù)單個(gè)錯(cuò)誤的冗余設(shè)計(jì)造成了很大的沖擊。在之前很多學(xué)者都對(duì)Xilinx FPGA［8］中發(fā)生多位翻轉(zhuǎn)的概率進(jìn)行了大量的研究工作。實(shí)驗(yàn)證明：98%的多位翻轉(zhuǎn)發(fā)生在FPGA的配置存儲(chǔ)位，并會(huì)影響到周圍多個(gè)存儲(chǔ)單元，有一些特定因素會(huì)增加2到3倍的多位翻轉(zhuǎn)的敏感性。考慮到配置存儲(chǔ)單元的排列方式（它是由一個(gè)全是配置單元的矩陣組成的），可以通過(guò)對(duì)一個(gè)集簇中的相鄰配置存儲(chǔ)位進(jìn)行分析來(lái)對(duì)多位翻轉(zhuǎn)的影響進(jìn)行研究，如圖1所示。單粒子可能撞擊到屬于不同F(xiàn)PGA資源的不同邏輯部分，如圖2所示，例如BRAMs（s表示多數(shù)，下同），BRAM的互聯(lián)點(diǎn)IO Blocks以及CLBs。每個(gè)配置位幀控制著一塊資源，這塊資源對(duì)應(yīng)著一列的SRAM FPGA的配置位信息［9］。CLB組成了FPGA的邏輯核心。它們包含一系列的結(jié)構(gòu)元素，每個(gè)結(jié)構(gòu)元素都包含一個(gè)轉(zhuǎn)化矩陣和一系列的邏輯元素，如圖3所示。更詳細(xì)地說(shuō)，一個(gè)單獨(dú)的CLB可以通過(guò)編程配置存儲(chǔ)位來(lái)實(shí)現(xiàn)任何的連續(xù)的或是有關(guān)聯(lián)的邏輯功能，具體能夠?qū)崿F(xiàn)多少功能是通過(guò)可用資源的間隔尺度來(lái)確定的。

圖1 多位翻轉(zhuǎn)發(fā)生在臨近的單元里

圖2 FPGA的配置存儲(chǔ)位的普通結(jié)構(gòu)形式

圖3 Virtex－II系列的FPGA詳細(xì)的CLB信息

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

（1）多位翻轉(zhuǎn)產(chǎn)生的錯(cuò)誤繞過(guò)表決器結(jié)構(gòu)繼續(xù)向深處傳輸，表決器的輸出對(duì)于故障沒(méi)有產(chǎn)生屏蔽作用，如圖4所示。

圖4 發(fā)生在表決器位置的多位翻轉(zhuǎn)導(dǎo)致三模冗余TMR失效

（2）當(dāng)發(fā)生錯(cuò)誤的資源屬于不同的域中時(shí)，多位翻轉(zhuǎn)所產(chǎn)生的錯(cuò)誤就會(huì)被表決器結(jié)構(gòu)所掩蓋，如圖5所示。

圖5 多位翻轉(zhuǎn)錯(cuò)誤被三模冗余TMR掩蓋

2 減少M(fèi)CUs有效的約束條件

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

表1 XCVIOOO各類模塊的單粒子效應(yīng)截面比例

從翻轉(zhuǎn)的比例來(lái)看，配置存儲(chǔ)器所占的比例最大，其次為L(zhǎng)UT型的RAM、BRAM和觸發(fā)器。可見(jiàn)，F(xiàn)PGA單粒子效應(yīng)故障絕大多數(shù)是由配置存儲(chǔ)器的翻轉(zhuǎn)引起的，配置存儲(chǔ)器的翻轉(zhuǎn)是FPGA單粒子效應(yīng)故障的最主要表現(xiàn)形式。配置存儲(chǔ)器的內(nèi)容決定了FPGA設(shè)計(jì)中各功能模塊的功能與狀態(tài)。配置存儲(chǔ)器中布線資源約占78%～84.8%，控制位和查找表位約占15%～21%，其他資源所占的比重不超過(guò)2%。由此可見(jiàn)，配置存儲(chǔ)器出現(xiàn)故障主要引起布線資源的錯(cuò)誤；也就是說(shuō)，在布局布線中，使用的布線資源越多，它所對(duì)應(yīng)的配置存儲(chǔ)器的信息就越多，若發(fā)生多位翻轉(zhuǎn)，存儲(chǔ)器真正有意義的存儲(chǔ)位出現(xiàn)錯(cuò)誤的概率就越高。因此，布局布線中盡量少地使用布線資源是減少配置存儲(chǔ)器錯(cuò)誤的有效方法。

（1）措施一：較少使用布線資源的最直接方法是減少布線的長(zhǎng)度，即使布線資源中連接線網(wǎng)源端和漏端的路徑最短（整體成本最低）。同時(shí)，可以通過(guò)多次布線迭代來(lái)解決布線資源的競(jìng)爭(zhēng)。布線的路徑的長(zhǎng)短體現(xiàn)在信號(hào)在路徑上的延時(shí)。在布線中，每次拆除重布點(diǎn)的一條線網(wǎng)，就成為一次布線迭代。在第一次布線迭代中，每條連線均以最小延時(shí)的目標(biāo)進(jìn)行布線，試試是否會(huì)導(dǎo)致布線資源的擁擠或重用。重用布線資源的電路布線是無(wú)效的，例如，1根線段被2個(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)鍵度定義為

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

把布線資源節(jié)點(diǎn)n作為（i，j）的部分連接的成本是

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

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

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

SMc和PIPc分別是功能模塊b對(duì)應(yīng)的開(kāi)關(guān)矩陣和PIPs的集合，其元素個(gè)數(shù)分別為KSMc和KPIPc，即：

布線抑制算法的目標(biāo)是使關(guān)鍵功能模塊集B對(duì)應(yīng)的可編程布線資源集V滿足：

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

式（6）和（7）從較輕松的程度限定了關(guān)鍵模塊集B中的任2個(gè)元素在布線時(shí)的策略，即開(kāi)關(guān)矩陣（SM）不能共用，可編程互聯(lián)點(diǎn)（PIPs）不能相鄰。

3 減緩多位翻轉(zhuǎn)布線算法

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

在算法結(jié)束之后，路徑搜索已經(jīng)完成。

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

／＊根據(jù)約束條件建立狀態(tài)數(shù)據(jù)集合ST，用以標(biāo)識(shí)SM和PIPs的相鄰狀態(tài)＊／

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

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

如果V滿足要求：保存狀態(tài)，退出。

4 實(shí)驗(yàn)分析

算法的好壞和有效性通過(guò)對(duì)電路的最終布線情況進(jìn)行分析來(lái)評(píng)估。主要包括2個(gè)方面：一是布線的時(shí)間，時(shí)間越短，說(shuō)明傳輸延遲越小，且布線時(shí)所用線長(zhǎng)越短，布線資源使用的就越少，因此就越能夠減少M(fèi)CUs發(fā)生的可能性；二是對(duì)CLB之間的連接盒（Switch Box）進(jìn)行分析。在Switch Box上的布線，在每個(gè)連接點(diǎn)（多條連線相交的點(diǎn)）上連線的間隔是衡量MCUs的一個(gè)重要指標(biāo)，當(dāng)離子撞擊到連接點(diǎn)時(shí)，多個(gè)布線之間夾角的角度越大，發(fā)生MCUs的可能性就越低。

我們采用目前最先進(jìn)的VTR布局布線工具作為電路布局布線的平臺(tái)，通過(guò)修改其中的布線部分的代碼實(shí)現(xiàn)了上述提出的算法。有些采用了標(biāo)準(zhǔn)API程序，具體見(jiàn)文獻(xiàn)［12－15］。

圖6和圖7分別為使用算法前和使用算法后的布線結(jié)果，使用算法前后布線延時(shí)比較見(jiàn)表2。

MCUs產(chǎn)生的根本原因是由于布線的幾何間隔過(guò)小。通過(guò)利用本算法進(jìn)行布線可以明顯看出，使用算法后的布線圖使得連接點(diǎn)之間連線的距離明顯增大，而且每個(gè)點(diǎn)的連線數(shù)量減少。這主要是因?yàn)楸舅惴ㄍㄟ^(guò)充分利用周圍沒(méi)使用的布線資源，使在同一點(diǎn)的連線盡可能地分布到其他的位置，連接點(diǎn)之間幾何間隔增大以及每個(gè)連接點(diǎn)上的連線減少?gòu)母旧蠝p少了發(fā)生MCUs的可能性。

圖6 應(yīng)用本算法前布線圖

圖7 應(yīng)用本算法后布線圖

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

從表2可知，布線延時(shí)從137.0ns減少到54.2ns。由于布線延遲和線長(zhǎng)成線性關(guān)系，線長(zhǎng)與發(fā)生MCUs的概率成線性關(guān)系，可知，布線延遲減少至54.2ns產(chǎn)生的效果是MCUs的發(fā)生概率減少了2.52倍。

5 結(jié)論

采用帶刷新分層的TMR技術(shù)并不能有效解決MCUs，因此在本文中提出的布線算法主要是針對(duì)SEU中的MCUs效應(yīng)。采用本算法進(jìn)行布線設(shè)計(jì)，減少了傳輸延時(shí)，增大了布線的集合間隔，使FPGA中的功能模塊分布更加分散。實(shí)驗(yàn)結(jié)果表明，本文算法可以從根本上減少M(fèi)CUs發(fā)生的幾率。將此項(xiàng)技術(shù)與帶刷新分層的TMR技術(shù)結(jié)合，可大大減少M(fèi)CUs發(fā)生的可能性。

（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］楊士元.數(shù)字系統(tǒng)的故障診斷與可靠性分析［M］.北京：清華大學(xué)出版社，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的星載計(jì)算機(jī)自檢EDAC電路設(shè)計(jì)［J］.微計(jì)算機(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.