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, the problem of electronic device performance degradation or failure in high-energy particle radiation environments has become increasingly prominent. In aerospace, nuclear industry, petroleum exploration, and deep-sea detection applications, high reliability of digital circuits is required. Among various reliability enhancement techniques, Triple Modular Redundancy (TMR) is considered to be one of the most effective methods. The basic principle of TMR is to duplicate digital circuits with the same input, and these three copies will work at the same time. When a circuit fails, the correct output can be obtained by a majority vote. Common implementation methods include fine-grained TMR technology, system layering technology, and state synchronization technology. State synchronization is a critical step in the radiation hardening of electronic equipment using TMR, ensuring that registers revert to their correct state after fault recovery. Synchronization voter insertion is employed to achieve this purpose; however, a large amount of resource overhead is incurred. A new synchronization voter insertion algorithm is proposed to address the challenge of reducing such resource consumption. The core objective is to develop and validate an algorithm that avoids exponential runtime complexity and, compared with existing methods, significantly reduces the required number of synchronization voters, thereby conserving valuable hardware resources. Methods The issue of synchronization voter insertion can be modeled as a Feedback Vertex Set Problem (FVSP) in graph theory after circuit processing. The memory circuit is first extracted from the digital circuit to remove nodes outside the selection range and reduce the circuit scale. Subsequently, the Feedback Vertex Set (FVS) is solved to identify a set of flip-flop nodes. All cycles containing memory elements in the circuit are effectively broken by inserting synchronization voters at the outputs of these flip-flops, ensuring state synchronization. In the implementation, a Simulated Annealing (SA) algorithm is employed, which utilizes topological sequences to avoid direct detection of loop existence, thereby reducing the time complexity of loop detection. To enhance the algorithm performance and solution quality, a Stagnation-Aware Probabilistic Reordering (SAPR) optimization scheme is proposed within the SA framework: a priority mechanism is introduced during topological reordering to reduce or prevent conflicts and misjudgments during critical search steps. The candidate set update strategy is optimized to select positions in the topological sequence most likely to be accepted. When the feedback vertex set remains unoptimized for multiple iterations, reordering is triggered with a certain probability to balance computational costs and the ability to escape local optima. Results and Discussions The quality of the feedback vertex set solved by the SAPR-SA-FVSP algorithm is evaluated. This method is compared with the other three methods. The probabilities of achieving the minimum value for the average, the optimal value, and the worst value are all higher, and the quality of the solution is better. ( Table 3 ). Furthermore, the SAPR-SA-FVSP algorithm exhibits a smaller average standard deviation, demonstrating more stable performance. The standard deviation averages for all test graphs are calculated as0.59634 for SA-FVSP,0.66755 for the Nonuniform Neighborhood Sampling (NNS) based SA,0.65193 for dynamic threshold reordering, and0.56217 for SAPR-SA-FVSP, confirming the superior stability of the proposed method. Using standard benchmark circuits (ISCAS89 and ITC'99), the voter insertion algorithm based on SAPR-SA-FVSP is evaluated against critical path-based voter insertion and the highest flip-flop fanout algorithms. Across all test cases, optimal solutions are achieved by SAPR-SA-FVSP, with the number of synchronization voters reduced by up to 78.88% compared to the critical path-based method and by up to 74.05% compared to the highest fanout flip-flop algorithm (Table 4 ). At the same time, improvements in running speed and robustness are also observed. The proposed algorithm is observed to operate normally on all test cases without failures, demonstrating better robustness. The average execution times for algorithms that run successfully on all test circuits are measured as 9880.19ms for the critical path-based algorithm, 9625.04ms for the highest fanout flip-flop algorithm, and only 3389.73ms for the proposed algorithm, representing significant speed improvements.Conclusions The SAPR optimization strategy proposed in this paper is presented as an improvement upon the existing SA-FVSP method, and better solution quality as well as more stable performance are achieved. On this basis, this paper proposes a resource-efficient synchronization voter insertion algorithm based on SAPR-SA-FVSP for restoring correct register states in TMR-hardened spaceborne applications. The algorithm decomposes the core problem into memory circuit extraction and FVSP solving. The completeness and efficiency of the algorithm are demonstrated, and significant reductions in synchronization voter insertion are confirmed by actual circuit testing compared with critical path-based and highest fanout flip-flop algorithms. An effective solution is provided for reducing hardware overhead while high reliability is maintained in TMR hardening of digital circuits. -
表 1 实验环境
环境类型 名称 配置或参数 硬件环境 内存 64GB 硬盘 477GB 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]. Proceedings of 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]. Proceedings of 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]. Proceedings of 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]. Proceedings of 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)
计量
- 文章访问数: 24
- HTML全文浏览量: 5
- PDF下载量: 5
- 被引次数: 0
下载:
