1.一种基于松弛法的电路敏感性路径标识方法,其特征在于,所述方法包括以下步骤:步骤1:网表解析及相关量初始化,过程如下:
1.1)读取网表,提取电路的基本单元信息及其互连关系,并构建相对应的完整性链表LC;
1.2)利用基准法计算面向多输入向量的LC中各电路单元的敏感性值;
步骤2:电路单元的拓扑排序,过程如下:
2.1)从LC中提取与电路原始输出端直接互连的单元或输出引线数为0的单元,用u表示,删除单元u的输出引线并将其置入到有序序列S中;
2.2)若LC非空,则转至步骤2.3);否则,转至步骤3;
2.3)提取与单元u直接互连的单元,并置入到序列T中,且执行k=1;
2.4)若k≤|T|,则提取T中的第k个单元tk,然后在LC中删除tk与u直接互连的引线,并转至步骤2.5);否则,从LC中删除单元u并释放序列T,然后转至步骤2.1);
2.5)执行k=k+1,并转至步骤2.4);
步骤3:基于松弛法在序列S中标识出电路的敏感性路径,过程如下:
3.1)利用步骤1.2)的所得结果给S中各单元赋值,其中若任意两单元间存在互连边,则用排名靠前单元的敏感性值标示该互连边的权重,否则用‘∞’表示;然后执行i=1;
3.2)若i≤|S|,则提取S中的第i个单元ui及其所有直接互连的前序单元并置入到集合V中,并执行j=1且转至步骤3.3);否则,转至步骤3.6);
3.3)若j≤|V|,则提取V中的第j个单元vj,并利用式(1)度量经过单元vj的单元ui到电路原始输出端的敏感性水平t_s(uij),t_s(uij)=w(vj→ui)+s(vj), (1)执行j=j+1,并转至步骤3.3);否则,转到步骤3.4);
3.4)利用式(2)从步骤3.3)的结果中提取单元ui到电路原始输出端的敏感性水平s(ui);
s(ui)=min{t_u(ui1),t_u(ui2),…,t_u(ui|V|)}, (2)
3.5)执行i=i+1,并转至步骤3.2);
3.6)提取S中从电路原始输出端到电路原始输入端敏感性值最低所对应的互连电路单元并输出;
其中,|LC|,|T|,|S|与|V|分别指LC,T,S与V中元素的个数,w(vj→ui)指单元vj与单元ui间互连线的权重,min指提取集合中的最小元素。