A Triple Modular Redundancy Voter Insertion Algorithm Utilizing Stagnation-Aware Probabilistic Reordering

LIU Zhaoting; LIU Peng

doi:10.11999/JEIT250825

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2025 >

LIU Zhaoting, LIU Peng. A Triple Modular Redundancy Voter Insertion Algorithm Utilizing Stagnation-Aware Probabilistic Reordering[J]. Journal of Electronics & Information Technology. doi: 10.11999/JEIT250825

Citation:

LIU Zhaoting, LIU Peng. A Triple Modular Redundancy Voter Insertion Algorithm Utilizing Stagnation-Aware Probabilistic Reordering[J]. Journal of Electronics & Information Technology. doi: 10.11999/JEIT250825

Citation:

PDF( 1211 KB)

A Triple Modular Redundancy Voter Insertion Algorithm Utilizing Stagnation-Aware Probabilistic Reordering

doi: 10.11999/JEIT250825 cstr: 32379.14.JEIT250825

LIU Zhaoting,
LIU Peng^,

1.
National Space Science Center, Chinese Academy of Sciences, Beijing 100020, China
2.
University of Chinese Academy of Sciences, Beijing 100020, China

Received Date: 2025-08-29
Accepted Date: 2026-03-16
Rev Recd Date: 2026-03-09

Available Online: 2026-03-30

Abstract

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.
- Triple Modular Redundancy (TMR),
- Synchronization voter,
- Simulated Annealing (SA),
- Feedback Vertex Set (FVS)

FullText(HTML)

References(18)

References

[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.