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.