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 > 2026 >

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( 1208 KB)

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

doi: 10.11999/JEIT250825 cstr: 32379.14.JEIT250825

LIU Zhaoting^{1, 2},
LIU Peng^{1, 2
,
,}

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-16

Available Online: 2026-03-30

Abstract

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 as 0.59634 for SA-FVSP, 0.66755 for the Nonuniform Neighborhood Sampling (NNS) based SA, 0.65193 for dynamic threshold reordering, and 0.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.
- 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]. 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. (查阅网上资料,未找到本条文献英文信息,请确认).