A Triple Modular Redundancy Voter Insertion Algorithm Utilizing Stagnation-Aware Probabilistic Reordering
-
摘要: 状态同步技术是三模冗余(TMR)抗辐照加固的关键环节，用于故障后保障寄存器同步到正确状态。该文提出一种降低资源开销的三模冗余同步表决器插入算法，算法通过提取数字电路的记忆电路和求解有向图反馈顶点集问题(DFVSP)实现。该文分析了模拟退火算法(SA)解决DFVSP的具体实现，在此基础上提出一种利用停滞感知的概率重排优化方案，方案的重排序过程通过引入优先级的拓扑排序实现，并增加了一种最优邻域策略来提高算法性能，同时设计了该优化SA算法用于三模冗余同步表决器插入的完整流程，证明了算法高效性与完备性。最后使用ISCAS89和ITC'99基准测试电路进行测试，并与基于关键路径的插入算法和最高扇出触发器算法进行了对比，测试结果说明了该文优化方案在算法运行速度、鲁棒性和硬件开销方面更有优势，尤其是硬件开销，在所有测试电路中均得到了最小同步表决器插入数量，对比其他两种算法最高资源的减少量分别达到了78.88%和74.05%，大幅节约了硬件开销。Abstract:
Objective With the rapid development of integrated circuit technology, performance degradation and failure of electronic devices in high-energy particle radiation environments become increasingly prominent. High reliability is required in applications such as aerospace, the nuclear industry, petroleum exploration, and deep-sea detection. Among the available reliability enhancement techniques, Triple Modular Redundancy (TMR) is widely regarded as one of the most effective methods. In TMR, three identical copies of a digital circuit operate in parallel with the same input, and the correct output is obtained through majority voting when one copy fails. Common implementation methods include fine-grained TMR, system-level partitioning, and state synchronization. State synchronization is a key step in TMR-based radiation hardening because it restores registers to the correct state after a fault. This process is achieved by inserting synchronization voters, but the resulting resource overhead is often high. This study proposes a new synchronization voter insertion algorithm to reduce hardware cost. The objective is to develop and validate an algorithm that avoids exponential runtime complexity and, relative to existing methods, reduces the number of required synchronization voters. Methods After circuit preprocessing, the synchronization voter insertion task is formulated as a Feedback Vertex Set Problem (FVSP). The memory circuit is first extracted from the digital circuit to exclude nodes outside the candidate range and reduce circuit size. A Feedback Vertex Set (FVS) is then solved to identify the flip-flop nodes at which synchronization voters should be inserted. By inserting voters at the outputs of these flip-flops, all cycles containing memory elements are broken, and state synchronization is ensured. In implementation, a Simulated Annealing (SA) algorithm is used. Topological ordering is adopted to avoid direct loop detection and to reduce the time complexity of cycle checking. To improve search efficiency and solution quality, a Stagnation-Aware Probabilistic Reordering (SAPR) scheme is incorporated into the SA framework. A priority-based mechanism is applied during topological reordering to reduce conflicts and false conflict judgments in critical search steps. The candidate-set update strategy is also refined so that insertion positions with the fewest conflicts are selected in the topological ordering. When the FVS is not improved over multiple iterations, reordering is triggered with a certain probability to balance computational cost and the ability to escape local optima. Results and Discussions The quality of the FVS obtained by the SAPR-SA-FVSP algorithm is evaluated by comparison with three other methods. The proposed method shows higher probabilities of achieving the minimum average, best, and worst values, which indicates better overall solution quality (Table 3). Furthermore, SAPR-SA-FVSP shows a smaller mean standard deviation, which indicates better stability. The average standard deviations over all test graphs are 0.596 34 for SA-FVSP, 0.667 55 for the Nonuniform Neighborhood Sampling (NNS)-based SA method, 0.651 93 for dynamic-threshold reordering, and 0.56217 for SAPR-SA-FVSP, confirming the superior stability of the proposed method (Table 4). Using the ISCAS89 and ITC'99 benchmark circuits, the proposed voter insertion algorithm is further compared with the critical path-based voter insertion algorithm and the highest-fanout flip-flop algorithm. Across all test cases, SAPR-SA-FVSP yields the smallest number of synchronization voters. The maximum reduction reaches 78.88% relative to the critical path-based method and 74.05% relative to the highest-fanout flip-flop algorithm (Table 5). The proposed algorithm also shows better speed and robustness. It runs successfully on all test cases without failure. The average execution times on the circuits for which all three algorithms complete successfully are 9880.19 ms for the critical path-based algorithm, 9 625.04 ms for the highest-fanout flip-flop algorithm, and 3 389.73 ms for the proposed algorithm. Conclusions The proposed SAPR strategy improves the conventional SA-FVSP method and yields better solution quality and greater stability. On this basis, a resource-efficient synchronization voter insertion algorithm is proposed for restoring correct register states in TMR-hardened digital circuits. The algorithm divides the task into memory-circuit extraction and FVSP solving. Its completeness and efficiency are demonstrated theoretically, and substantial reductions in synchronization voter insertion are verified on benchmark circuits relative to the critical path-based and highest-fanout flip-flop methods. The proposed method therefore provides an effective approach for reducing hardware overhead while maintaining high reliability in TMR hardening of digital circuits. -
表 1 实验环境
环境类型 名称 配置或参数 硬件环境 内存 64 GB 硬盘 477 GB CPU Intel(R) Core(TM) i5- 14600 2.70 GHz软件环境 操作系统 Windows 11 26100.4349 编程语言 C++ 
下载: 导出CSV
表 2 参数设置
参数 取值 含义 T0 0.6 初始温度 alpha 0.99 降温系数 maxMv 5×(总节点数-自循环节点数) 单个温度值解更新最大次数 maxFail
runtime50
20最大连续失败次数
每个测试用例运行次数
下载: 导出CSV
表 3 求解反馈顶点集算法结果比较(个)
点数 边数 平均值 最优值 最劣值 SA-
FVSPSA-FVSP-
NNS动态阈
值重排SAPR-SA-
FVSPSA-
FVSPSA-FVSP-
NNS动态阈
值重排SAPR-SA-
FVSPSA-
FVSPSA-FVSP-
NNS动态阈
值重排SAPR-SA-
FVSP100 200 9.00 9.80 9.10 9.00 9 9 9 9 9 10 10 9 100 300 17.00 17.30 17.10 17.00 17 17 17 17 17 18 18 17 100 400 23.05 24.20 23.00 23.00 23 24 23 23 24 25 23 23 100 500 32.15 32.00 32.50 32.00 32 32 32 32 33 32 33 32 100 600 36.85 37.80 37.20 36.80 36 37 36 36 37 38 38 37 100 1000 53.15 53.55 53.05 53.05 53 53 53 53 54 54 54 54 100 1100 54.75 55.00 54.80 54.85 54 55 54 54 55 55 55 55 100 1200 57.00 57.55 57.00 57.05 57 57 57 57 57 58 57 58 100 1300 60.00 60.00 60.00 60.00 60 60 60 60 60 60 60 60 100 1400 61.00 61.00 61.00 61.00 61 61 61 61 61 61 61 61 500 1000 32.00 33.20 36.05 32.05 31 33 35 31 33 34 37 33 500 1500 65.05 66.05 70.55 65.05 64 65 69 64 66 68 72 66 500 2000 104.15 104.80 111.00 103.80 103 103 109 102 107 108 113 105 500 2500 135.35 139.40 143.05 135.20 134 138 141 134 137 141 145 137 500 3000 164.95 167.85 170.20 165.25 164 164 167 164 167 170 172 167 500 5000 239.05 241.80 242.85 239.25 237 239 241 237 242 245 244 241 500 5500 253.95 256.55 258.20 253.75 253 255 257 252 256 258 260 257 500 6000 266.80 268.75 270.05 266.75 264 267 267 264 270 270 273 269 500 6500 279.00 278.90 282.95 279.00 277 277 281 276 281 280 285 281 500 7000 288.60 291.20 292.35 288.35 287 287 290 286 292 295 294 290 平均 111.64 112.84 114.10 111.61 110.80 111.65 112.95 110.60 112.90 114.00 115.20 112.60
下载: 导出CSV
表 4 各测试图运行结果标准差的平均值
算法 SA-FVSP SA-FVSP-NNS 动态阈值重排 SAPR-SA-FVSP 标准差平均值 0.59634 0.66755 0.65193 0.56217
下载: 导出CSV
表 5 表决器插入数量对比
测试电路 触发器总数 算法1 算法2 本文算法 单组同步
表决器数 (个)单组同步
表决器数 (个)单组同步
表决器数 (个)对比算法1减少
百分比(%)对比算法2减少
百分比(%)s38584 1452 1273 - 1115 12.41 - s38584.1 1426 - - 1089 - - s38417 1636 1121 1100 1080 3.66 1.82 s35932 1728 1449 1179 306 78.88 74.05 s15850 597 495 464 441 10.91 4.96 s15850.1 534 433 402 379 12.47 5.72 s13207 669 407 396 310 23.83 21.72 s13207.1 638 382 371 285 25.39 23.18 s9234 228 164 160 152 7.32 5.00 s9234.1 211 149 146 137 8.05 6.16 s6669 239 41 41 41 0.00 0.00 s5378 179 59 93 30 49.15 67.74 s4863 104 40 53 16 60.00 69.81 s3384 183 72 72 72 0.00 0.00 s3330 132 29 29 28 3.45 3.45 s3271 116 110 110 110 0.00 0.00 s1512 57 57 57 57 0.00 0.00 s713 19 15 15 15 0.00 0.00 b22 735 729 729 729 0.00 0.00 b21 490 486 486 486 0.00 0.00 b20 490 486 486 486 0.00 0.00 b20_opt 490 487 486 486 0.21 0.00 b19 6642 - - 6618 - - b18 3320 - - 3308 - - b18_opt 3270 - - 3258 - - b17 1415 - - 1411 - - b17_opt 1414 - - 1410 - - b15 449 449 449 449 0.00 0.00 b14 245 243 243 243 0.00 0.00 b13 53 52 52 51 1.92 1.92 b13_opt 53 52 51 51 1.92 0.00 b12 121 117 119 117 0.00 1.68 b12_opt 121 118 119 117 0.85 1.68 b11 31 31 31 30 3.23 3.23 b11_opt 31 31 31 30 3.23 3.23
下载: 导出CSV
-
[1] 闫爱斌, 李坤, 黄正峰, 等. 两种面向宇航应用的高可靠性抗辐射加固技术静态随机存储器单元[J]. 电子与信息学报, 2024, 46(10): 4072–4080. doi: 10.11999/JEIT240082.YAN Aibin, LI Kun, HUANG Zhengfeng, et al. Two highly reliable radiation hardened by design static random access memory cells for aerospace applications[J]. Journal of Electronics & Information Technology, 2024, 46(10): 4072–4080. doi: 10.11999/JEIT240082. [2] 魏肖彤, 许浩博, 尹春笛, 等. 天基计算芯片: 现状、趋势与关键技术[J]. 电子与信息学报, 2025, 47(9): 2963–2978. doi: 10.11999/JEIT250633.WEI Xiaotong, XU Haobo, YIN Chundi, et al. Space-based computing chips: Current status, trends and key technique[J]. Journal of Electronics & Information Technology, 2025, 47(9): 2963–2978. doi: 10.11999/JEIT250633. [3] 陈雷, 王卓立, 王硕, 等. SRAM型FPGA多层级软错误防护技术研究进展[J]. 北京航空航天大学学报, 2024, 51(11): 3599–3616. doi: 10.13700/j.bh.1001-5965.2023-0587.CHEN Lei, WANG Zhuoli, WANG Shuo, et al. Survey of multi-level soft error mitigation techniques for SRAM-based FPGAs[J]. Journal of Beijing University of Aeronautics and Astronautics, 2024, 51(11): 3599–3616. doi: 10.13700/j.bh.1001-5965.2023-0587. [4] 李炎, 胡岳鸣, 曾晓洋. 面向商业航天卫星成本效益的三模冗余软错误防护技术: 近似计算的实践[J]. 电子与信息学报, 2024, 46(5): 1604–1612. doi: 10.11999/JEIT231288.LI Yan, HU Yueming, and ZENG Xiaoyang. Cost-effective TMR soft error tolerance technique for commercial aerospace: Utilization of approximate computing[J]. Journal of Electronics & Information Technology, 2024, 46(5): 1604–1612. doi: 10.11999/JEIT231288. [5] 谭宜涛, 杨海钢, 黄娟, 等. 基于关键路径的三模冗余表决器插入算法[J]. 电子与信息学报, 2012, 34(2): 487–492. doi: 10.3724/SP.J.1146.2011.00571.TAN Yitao, YANG Haigang, HUANG Juan, et al. Voter insertion algorithm based on critical path for triple module redundancy[J]. Journal of Electronics & Information Technology, 2012, 34(2): 487–492. doi: 10.3724/SP.J.1146.2011.00571. [6] JOHNSON J M and WIRTHLIN M J. Voter insertion algorithms for FPGA designs using triple modular redundancy[C]. The 18th Annual ACM/SIGDA International Symposium on Field Programmable Gate Arrays, Monterey, USA, 2010: 249–258. doi: 10.1145/1723112.1723154. [7] CHAKRADHAR S T, BALAKRISHNAN A, and AGRAWAL V D. An exact algorithm for selecting partial scan flip-flops[C]. The 31st Design Automation Conference, San Diego, USA, 1994: 81–86. doi: 10.1145/196244.196285. [8] ANGRICK S, BALS B, CASEL K, et al. Solving directed feedback vertex set by iterative reduction to vertex cover[C]. The 21st International Symposium on Experimental Algorithms (SEA 2023), Barcelona, Spain, 2023: 10: 1–10: 14. doi: 10.4230/LIPIcs.SEA.2023.10. [9] 白天. 反馈集相关问题的参数与精确算法研究[D]. [博士论文], 电子科技大学, 2024. doi: 10.27005/d.cnki.gdzku.2024.000014.BAI Tian. Investigations concerning parameterized and exact algorithms for the feedback set and related problems[D]. [Ph. D. dissertation], University of Electronic Science and Technology of China, 2024. doi: 10.27005/d.cnki.gdzku.2024.000014. [10] YANNAKAKIS M. Node-and edge-deletion NP-complete problems[C]. The 10th Annual ACM Symposium on Theory of Computing, San Diego, USA, 1978: 253–264. doi: 10.1145/800133.804355. [11] GALINIER P, LEMAMOU E, and BOUZIDI M W. Applying local search to the feedback vertex set problem[J]. Journal of Heuristics, 2013, 19(5): 797–818. doi: 10.1007/s10732-013-9224-z. [12] TANG Zhipeng, FENG Qilong, and ZHONG Ping. Nonuniform neighborhood sampling based simulated annealing for the directed feedback vertex set problem[J]. IEEE Access, 2017, 5: 12353–12363. doi: 10.1109/ACCESS.2017.2724065. [13] RUSSO L M S, CASTRO D, ILIC A, et al. Stochastic simulated annealing for directed feedback vertex set[J]. Applied Soft Computing, 2022, 129: 109607. doi: 10.1016/j.asoc.2022.109607. [14] 杜禹明. 求解有向反馈顶点集问题的多阶段重启模拟退火算法[D]. [硕士论文], 华中科技大学, 2024. doi: 10.27157/d.cnki.ghzku.2024.004564.DU Yuming. A multi-stage re-heating simulated annealing algorithm for directed feedback vertex set problem[D]. [Master dissertation], Huazhong University of Science and Technology, 2024. doi: 10.27157/d.cnki.ghzku.2024.004564. [15] LIN Henming and JOU Jingyang. On computing the minimum feedback vertex set of a directed graph by contraction operations[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2000, 19(3): 295–307. doi: 10.1109/43.833199. [16] 张顺根. 求解反馈顶点集问题的多阶段响应阈值搜索算法[D]. [硕士论文], 华中科技大学, 2023. doi: 10.27157/d.cnki.ghzku.2023.001840.ZHANG Shungen. A multi-stage responsive threshold search for feedback vertex set problem[D]. [Master dissertation], Huazhong University of Science and Technology, 2023. doi: 10.27157/d.cnki.ghzku.2023.001840. [17] CORNO F, REORDA M S, and SQUILLERO G. RT-level ITC'99 benchmarks and first ATPG results[J]. IEEE Design & Test of Computers, 2000, 17(3): 44–53. doi: 10.1109/54.867894. [18] WRIENT. iscas89, 集成电路89基准电路[EB/OL]. https://bbs.eetop.cn/thread-247418-1-1.html, 2025.WRIENT. iscas89, integrated circuit 89 reference circuit[EB/OL]. https://bbs.eetop.cn/thread-247418-1-1.html, 2025. -
图(4) / 表(5)
计量
- 文章访问数: 86
- HTML全文浏览量: 42
- PDF下载量: 30
- 被引次数: 0
下载:
