本发明涉及一种基于改进kl算法的选择性三模冗余方法，属于集成电路抗辐射加固。
背景技术：
1、航天器中各种电子设备将不可避免地处于复杂空间辐射环境之中，辐射作用会对电子设备中的集成电路造成不同程度的破坏，使整个电子系统发生故障甚至瘫痪。太空环境下集成电路将面临多种形式的辐射效应，单粒子翻转(single event upset，seu)是其中的一种主要辐射效应。单粒子翻转会造成电路逻辑状态的跳变、存储数据的翻转或者系统的功能中断等一系列错误。因此针对单粒子翻转效应的加固是非常有必要的。
2、缓解单粒子翻转的一种常见方法是三模冗余(triple modular redundancy,tmr)，其基本思想是将节点复制为3份，向所有的冗余节点提供相同的输入，然后使用多数表决器根据少数服从多数的原则来决定正确的输出。tmr不仅能检测错误的存在，而且能够屏蔽错误、输出期望的正确值，但其带来了较大的面积、功耗以及延时开销，对电路性能影响较大。
3、近年来的研究表明，电路中的节点对软错误的敏感性是不同的，有些节点对软错误的敏感性明显高于其他节点。正是存在这种现象，可以对电路中软错误敏感的节点进行加固，忽略那些几乎不发生软错误的节点，虽然可靠性降低了，但是面积开销显著减少了，从而为用较低的面积开销得到较高的可靠性创造了机会。所以选择性加固已经成为容错技术发展的新趋势，可适用于组合逻辑和时序逻辑。
技术实现思路
1、本发明解决的技术问题是：针对目前现有技术中全三模冗余过多的硬件开销问题，提出了一种基于改进kl算法的选择性三模冗余方法。
2、本发明解决上述技术问题是通过如下技术方案予以实现的：
3、一种基于改进kl算法的选择性三模冗余方法，包括：
4、读取电路网表文件以获取电路连接关系，根据拓扑准则预估电路节点的软错误敏感度，将所有电路节点初始分组，分组类别为seu敏感类、seu不敏感类；
5、针对seu敏感节点进行三模冗余并构建三模冗余电路；
6、预设三模冗余电路的各输出端错误阈值及终止条件，并执行故障注入后外部系统的容错分析，判断容错分析结果是否满足终止条件，若满足终止条件则结束优化流程，否则利用改进kl算法优化seu敏感节点并重新构建三模冗余电路直至满足终止条件；
7、完成seu敏感节点优化及三模冗余电路优化。
8、所述拓扑准则包括准则一、准则二、准则三，分别为：
9、准则一为扇入fan-in、扇出fan-out节点选取准则，准则二为目标电路节点影响的外部系统输出数量准则，准则三为目标电路节点的反馈回路数量准则，对各电路节点分别使用三条拓扑准则进行判断，满足其中任一准则时，根据所选准则判断当前电路节点的类别并分组。
10、所述扇入fan-in、扇出fan-out节点选取准则为：
11、设定n×n邻接矩阵(n∈n)，将电路连接关系视为包括n个电路节点的有限有向图，将各非对角线aij视为触发器i与触发器j之间的直接连接，将各对角线aii视为触发器i处的反馈或环路，若连接存在，则将aij或aii赋值为1，若连接不存在，则将aij或aii赋值为0；
12、对各电路节点进行扇入fan-in赋值、扇出fan-out赋值；
13、ri∈reg_set(r)；
14、fan-in(ri)＝length(find(:,ri)＝1)；
15、fan-out(ri)＝length(find(ri,:)＝1)；
16、设定扇入fan-in阈值、扇出fan-out阈值，选取满足低于扇入fan-in阈值且高于扇出fan-out阈值的电路节点作为seu敏感类节点，其余节点作为seu不敏感类节点。
17、所述目标电路节点影响的外部系统输出数量准则为：
18、设定n×n邻接矩阵(n∈n)，改变矩阵边权值，将电路连接关系的无权图模型转换为等价的有权图模型，确定有权图模型中对应的节点i和节点j权值nc为连接节点i和节点j的网线的度，n为节点i和节点j的网线总数；
19、对各目标电路节点ri∈reg_set(r)，确定输出节点oi∈output_set(o)，令count(ri)＝0，通过dijkstra算法用于确定与每个目标节点相关联的输出数量，若(dijkstra(adjacency matrix,ri,oi))<∞，则count(ri)++；
20、当目标节点存在多个输出路径时，选取count值高的目标节点作为seu敏感类节点，其余节点作为seu不敏感类节点。
21、所述目标电路节点的反馈回路数量准则为：
22、设定n×n邻接矩阵(n∈n)，改变矩阵边权值，将电路连接关系的无权图模型转换为等价的有权图模型，确定有权图模型中对应的节点i和节点j权值
23、对各目标电路节点ri∈reg_set(r)，确定反馈输出节点ri′∈r-output(ri)，令back(ri)＝0，通过dijkstra算法用于确定每个目标节点的反馈回路数量，若(dijkstra(adjacency matrix,ri,ri′))<∞，则back(ri)++；
24、选取反馈回路数量back值高于预设阈值时，当前节点作为seu敏感类节点，其余节点作为seu不敏感类节点。
25、所述各输出端错误阈值预先设置为0％、0.5％、1％，具体选择根据三模冗余电路优化任务需求确定；终止条件包括可靠性约束及电路设计面积成本约束，可靠性约束根据三模冗余电路优化任务需求确定，面积成本约束为：
26、设sp1为当前优化后所得面积成本，sp2为上一次优化后所得面积成本，若各输出端结果不超过所需满足的错误阈值且(sp1-sp2)/sp1<0的次数超过n时，满足面积成本约束；
27、当容错分析结果满足终止条件后结束seu敏感节点优化。
28、改进kl算法具体为：
29、对初始分组v1和v2，分别选择每个群组中外边数减去内边数最大的两个节点组成2×2个顶点对；
30、选取顶点对中四种变换中割集规模减少最大或者割集规模增加最少的作为最终交换的顶点对，即四次变换中减少最大或者增加最少，其中γ1(vi)表示节点vi与群组v1中的其它节点之间的连接边数，γ2(vi)表示节点vi与群组v2中的其它节点之间的连接边数；
31、重复进行顶点对优化迭代，迭代过程中已进行变化的电路节点不进行迭代；
32、当任一群组中遍历各电路节点并无法找到待交换的两个电路节点后，结束电路节点的改进优化。
33、所述面积成本约束中，不超过所需满足的错误阈值且满足面积成本判据的次数n，数值根据三模冗余电路对应输出端的优化任务需求确定。
34、所述电路网表文件为待测电路信息源头，通过拓扑准则对待测电路的电路节点进行初始分组，初步判断对seu敏感的电路节点，使初始分组与最终分组接近；利用改进kl算法对电路节点进行优化调整，根据容错分析及终止条件判断结果，在保证可靠性约束的同时减少面积成本开销。
35、本发明与现有技术相比的优点在于：
36、(1)本发明提供的一种基于改进kl算法的选择性三模冗余方法，对电路节点进行拓扑分析和初始分组，再利用改进的kl算法进行分组优化，从而在提高电路抗单粒子可靠性的同时减小了传统三模冗余方式带来的面积开销，其中采用三种拓扑准则对电路节点进行拓扑分析，可以初步判断对seu敏感的电路节点，使得初始分组与最终分组足够接近，大大减少后续启发式优化算法的工作量；
37、(2)本发明采用改进的kl算法作为启发式优化引擎，针对传统kernighan-lin算法效率较低和时间复杂度较大的缺点，在改进算法中，最明显的是选择节点方式发生了改变，分别从两个群组中同时选择两个节点组成2×2轮循环，然后在2×2轮循环中选出使割集规模达到最小的顶点对进行交换，从而大大减小了算法的时间复杂度、提高了执行效率；
38、(3)本发明通过准确的软错误敏感度评估、适当的三模冗余容错技术以及高效的启发式算法选择策略，设计了一种基于改进kl算法的选择性三模冗余方法，在提高电路抗单粒子可靠性的同时减小了传统三模冗余方式带来的面积开销。
1.一种基于改进kl算法的选择性三模冗余方法，其特征在于包括：
2.根据权利要求1所述的一种基于改进kl算法的选择性三模冗余方法，其特征在于：
3.根据权利要求2所述的一种基于改进kl算法的选择性三模冗余方法，其特征在于：
4.根据权利要求2所述的一种基于改进kl算法的选择性三模冗余方法，其特征在于：
5.根据权利要求2所述的一种基于改进kl算法的选择性三模冗余方法，其特征在于：
6.根据权利要求1所述的一种基于改进kl算法的选择性三模冗余方法，其特征在于：
7.根据权利要求1所述的一种基于改进kl算法的选择性三模冗余方法，其特征在于：
8.根据权利要求6所述的一种基于改进kl算法的选择性三模冗余方法，其特征在于：
9.根据权利要求1所述的一种基于改进kl算法的选择性三模冗余方法，其特征在于：
