基于二分图极大权值匹配的SoC故障定位算法研究

Research on fault localization algorithm for SoC based on bipartite graph maximum weight matching

针对故障传播给故障定位带来的影响,考虑SoC功能测试系统中的故障源与故障事件之间的不确定性,提出一种基于二分图的故障定位算法。从SoC中抽象出特定的硬件模块,由这些模块构成故障源,结合相应的故障事件组合成二分图,在二分图的基础上生成一种适用于SoC故障定位的故障传播模型(fault propagation model,FPM)。将SoC故障定位的问题转换成二分图极大权值匹配的求解问题,从概率上保证结果的正确性。实验结果表明,故障定位准确率提高了0~21%,误报率下降了0~15%,更加适用于小型系统的故障定位。

Aiming at the fault propagation impact for the fault localization, considering uncertainty between fault sources and events of the function test system of SoC, this paper proposed fault localization algorithm for SoC based on bipartite graph. It firstly abstracted specific hardware modules in order to forming the fault sources. Then fault sources combined with relevant faults events to constitute the bipartite graph, generate the fault propagation model based on the bipartite graph which was suitable for fault localization of SoC. Finally the problem of fault localization translated into how to maximize the weight of bipartite graph, which assured the correctness from a probabilistic perspective. The experiment results show that the true positive of fault localization has increased by 0 -21% and the false positive of fault localization has decreased byO ~ 15% ,which is more suitable for the small system fault localization.