基于差分进化算法聚类的2.5D集成电路小时延缺陷检测方法

基于差分进化算法聚类的2.5d集成电路小时延缺陷检测方法
技术领域
1.本发明涉及一种基于差分进化算法聚类的2.5d集成电路小时延缺陷检测方法，属于集成电路测试优化技术领域。


背景技术：

2.在新一轮科技和产业革命背景下，集成电路面临着日益增长的市场需求，为了使其功能更加强大、性能更加优越，集成电路的规模也越来越大。然而，规模扩大所导致的路径延时长、测试成本高，成为集成电路设计和制造过程中存在的严重问题。当前，一种具有较低制造成本和设计复杂度的2.5d集成电路是集成电路行业发展的主流方向之一。
3.随着2.5d集成电路工艺尺寸的不断缩小和工作频率的不断提高，电路正常工作所允许的时序波动变得越来越小，因此由小时延缺陷所引起的额外延迟将不可忽略。研究表明，当集成电路技术发展到45nm以下时，因延迟而产生的故障大部分是由于小时延缺陷引起的，因此有效检测关键路径上的小时延缺陷是至关重要的。但是2.5d集成电路中存在大量的关键路径，逐一检测将消耗大量的测试时间成本，如何从关键路径中选择出一组具有典型特征的代表性关键路径，是实现对小时延缺陷进行快速检测的关键。
4.代表性关键路径的选择过程本质上就是利用不同关键路的径特征相似性进行聚类的过程。但是常见的聚类算法在执行过程中需要预先设定聚类数量，而且在面对集成电路中大规模的关键路径将产生组合爆炸，聚类效率低，无法有效实现小时延缺陷的快速检测。


技术实现要素：

5.针对传统2.5d集成电路小时延缺陷检测方法测试成本开销大、测试速度慢的问题，本发明提供一种基于差分进化算法聚类的2.5d集成电路小时延缺陷检测方法。本发明利用差分进化算法进行聚类分析，选择出少量代表性关键路径，并利用时延的相似性，将测量值映射到其他关键路径上；并且该方法无需预先知道待聚类数据，可以在聚类过程中决定数据的最优分簇数量，实现了小时延缺陷的快速检测。
6.本发明所述基于差分进化算法聚类的2.5d集成电路小时延缺陷检测方法，该方法包括以下步骤：
7.步骤一，读取2.5d集成电路关键路径数据作为待聚类数据，并存入待处理的寄存器中；
8.步骤二，使用差分进化算法对寄存器中的待聚类数据进行处理，获取最优聚类方案：
9.首先，对待聚类数据进行初始化形成初始种群，所述初始种群包括k个子类，对初始种群进行评估；
10.然后反复进行变异操作、交叉操作和选择操作来优化聚类过程，直到满足设置的最大迭代次数，获取最优聚类方案；
11.步骤三，根据最优聚类方案选择每个子类中的聚类中心作为代表性关键路径，测量代表性关键路径上的延迟并映射到其他关键路径上，完成检测集成电路关键路径上的小时延缺陷。
12.优选地，待聚类数据为x
×
y的数据集p
x
×y＝{p1,p2,
…
,p
x
}
t
，行向量p
x
,x＝1,2,
…
,x表示数据集中的第x条关键路径，x为关键路径的数量，每条路径都采用y个特性进行编码；p
x,y
表示第x条关键路径的第y,y＝1,2,...,y个特性。
13.优选地，步骤二使用差分进化算法获取最优聚类方案的过程为：
14.s1、种群初始化，初始种群中每一个个体代表一种聚类方案，种群中共含有np个个体，每个个体初始化为一个k
max
+k
max
×
y维的向量：
[0015][0016]
其中，np表示种群中个体的序号，g为迭代次数，x
np,g
为第g次迭代的第np个个体，k
max
表示所允许的最大的聚类数目，在个体编码中，前k
max
个元素a
np,k
,(k＝1,2,
…
,k
max
)为聚类中心的激活标志，为[0,1]之间的随机数，初始化时将其设置为[0.5,1]之间的随机数；剩余元素s
np,k
(k＝1,2,
…
,k
max
)为第k个子类的聚类中心，均为y维的向量，初始化为从x条关键路径中随机选取的k
max
条关键路径；执行过程中，如果a
np,k
≥0.5，那么对应的第k个聚类中心s
np,k
处于激活状态；否则，处于无效状态；
[0017]
s2、评估初始种群，获取初始种群的最优聚类方案；
[0018]
首先，对每个个体进行分类，根据关键路径到聚类中心的欧式距离将聚类方案中的所有关键路径划分到不同的子类里；
[0019]
然后，对初始种群中的每个个体进行适应度值评估，评估指标cs(k)按下式获取：
[0020][0021]
其中，ck表示第k个子类，k＝1,2,...,k，k表示处于激活状态的聚类数量,k≤k
max
；
[0022]
pa,pb为第k个子类中关键路径，a＝1,2,...,nk，b＝1,2,...,nk，且a≠b，nk表示第k个子类中关键路径的数量；
[0023]
d(pa,pb)表示关键路径pa与pb之间的欧氏距离，
[0024]
avk为第k个子类的平均位置，av
k'
为第k'个子类的平均位置，k'＝1,2,...,k，且k≠k'，avk和av
k'
的计算方式相同，其中avk按下式获取：
[0025][0026]
将评估指标cs(k)值最小的个体最为初始种群的最优聚类方案，作为第0次迭代最优个体x
best,0
；
[0027]
s3、差分变异操作；
[0028]
将第g次迭代生成的最优聚类方案进行变异，生成变异个体，第g次迭代第np个个体生成的变异个体v
np,g
为：
[0029][0030]
x
best,g
为第g次迭代生成的最优个体；
[0031]
为第g次迭代时从种群中随机选择的三个当前个体，其中为三个个体中适应度值最优的精英个体；
[0032]
w为过程参数，通过该参数将向量与x
best,g
进行了组合，按下式获取：
[0033]
w＝gp/exp(es)
[0034]
式中，gp＝(g
max-g+1)/g
max
是与迭代次数相关的参数，随着进化过程而递减，g
max
表示允许的最大迭代次数；参数es＝r
*
/np表示精英个体的状态参数，r
*
表示精英个体在整个种群中的适应度值排序值；
[0035]
f1和f2为两个独立的缩放参数，该参数的计算方式如下：
[0036]
f＝wp
·
n(μ,σ2)+(1-wp)
·
es
[0037]
式中，wp＝exp[3
·
(gp-1)]为权重参数，n(μ,σ2)为高斯分布随机数，标准差μ设为0.5，标准差σ设置为0.1，n(μ,σ2)运行两次分别获取f1和f2；
[0038]
s4、交叉操作；
[0039]
交叉操作通过交叉概率参数cr实现了将当前个体x
np,g
与变异个体v
np,g
的交叉混合，产生试验个体u
np,g
，当前个体x
np,g
作为父代个体，具体实现过程如下：
[0040][0041]unp,q,g
表示第np个试验个体的第q维变量，randi(d)是从集合{1,2,
…
,d}中随机选择的一个数，d表示个体维度，保证试验个体u
np,g
中至少有一维是来自变异个体v
np,g
，从而避免与父代个体x
np,g
完全相同；交叉概率参数cr的计算公式如下：
[0042]
cr＝wp
·
n(μ,σ2)+(1-wp)
·
is
[0043]
参数is＝rank
np
/np表示父代个体x
np,g
的排序状态值；
[0044]
s5、选择操作；
[0045]
差分进化算法采用贪婪选择方式进行精英解的保留，按下式对第g次迭代种群中的个体进行选择：
[0046][0047]
其中，f(
·
)表示适应度函数，指每种聚类方案的cs指标函数；
[0048]
更新在第g次迭代过程中找到的最优聚类方案；
[0049]
重复执行步骤s3～s5，直至达到最大迭代次数，获取种群最终的最优聚类方案。
[0050]
优选地，执行步骤s4之后还包括如下解修复步骤：
[0051]
当个体编码中的前k
max
个激活标志参数大于1或者小于0时，分别修复为1或者0；另外，如果所有聚类中心均处于无效状态，则随机选择两个聚类中心，将其激活标志参数在[0.5,1]范围内随机生成，以确保可以将数据至少聚类成2个子类。
[0052]
优选地，步骤三获取2.5d集成电路小时延的过程为：
[0053]
步骤三一、选择最优聚类方案中每个子类的聚类中心作为该子类的代表性关键路
径，从最优聚类方案的k个子类共获取k条代表性关键路径pk＝{p1',p2',
…
,pk',
…
,pk'}
t
；pk'为第k个子类的代表性关键路径；
[0054]
步骤三二、测量k条代表性关键路径的延时dk＝[d1',d'2,
…
,d'k,
…
,d'k]
t
，d'k为第k条代表性关键路径的延时；
[0055]
步骤三三、将代表性关键路径上的延迟并映射到其他关键路径上，获取2.5d集成电路小时延
[0056][0057]
式中，p为所有关键路径组成的数据集p
x
×y。
[0058]
本发明的有益效果：
[0059]
(1)差分进化算法是一种高效的启发式智能优化算法，具有原理简单，控制参数少，优化效率高等优势；
[0060]
(2)采用基于差分进化算法辅助的聚类方法将2.5d集成电路中的关键路径进行分组，选择出少量的代表性关键路径，通过代表性关键路径上的延迟检测，估计出其他关键路径上的延迟，进而实现了小时延缺陷的快速检测，克服了传统方法检测每一条关键路径上的延迟而导致测试成本开销大、测试速度慢的问题。
附图说明
[0061]
图1是个体编码示意图；
[0062]
图2是本发明所述基于差分进化算法聚类的2.5d集成电路小时延缺陷检测方法的流程图。
具体实施方式
[0063]
下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有作出创造性劳动的前提下所获得的所有其它实施例，都属于本发明保护的范围。
[0064]
需要说明的是，在不冲突的情况下，本发明中的实施例及实施例中的特征可以相互组合。
[0065]
下面结合附图和具体实施例对本发明作进一步说明，但不作为本发明的限定。
[0066]
具体实施方式一：下面结合图1和图2说明本实施方式，本实施方式所述基于差分进化算法聚类的2.5d集成电路小时延缺陷检测方法，1、基于差分进化算法聚类的2.5d集成电路小时延缺陷检测方法，其特征在于，该方法包括以下步骤：
[0067]
步骤一，读取2.5d集成电路关键路径数据作为待聚类数据，并存入待处理的寄存器中；
[0068]
步骤二，使用差分进化算法对寄存器中的待聚类数据进行处理，获取最优聚类方案：
[0069]
首先，对待聚类数据进行初始化形成初始种群，所述初始种群包括k个子类，对初始种群进行评估；
[0070]
然后反复进行变异操作、交叉操作和选择操作来优化聚类过程，直到满足设置的
最大迭代次数，获取最优聚类方案；
[0071]
步骤三，根据最优聚类方案选择每个子类中的聚类中心作为代表性关键路径，测量代表性关键路径上的延迟并映射到其他关键路径上，完成检测集成电路关键路径上的小时延缺陷。
[0072]
步骤一中，待聚类数据为x
×
y的数据集p
x
×y＝{p1,p2,
…
,p
x
}
t
，行向量p
x
,x＝1,2,
…
,x表示数据集中的第x条关键路径，x为关键路径的数量，每条路径都采用y个特性进行编码；p
x,y
表示第x条关键路径的第y,y＝1,2,...,y个特性。
[0073]
聚类的目的就是将这x条关键路径分为k个子类λ＝{c1,c2,
…
,ck}，同一子类中关键路径的相似性应尽可能大，而不同子类模式的相似性应尽可能小。聚类需要至少满足以下三个方面：
[0074]
(1)每个子类中至少包含一条关键路径，即：
[0075]
(2)每个子类中不能含有相同条关键路径，即：
[0076]
(3)每条关键路径都应属于一个子类，即：
[0077]
在满足上述条件下，相同的数据集可能存在多种不同的划分方式，因此，聚类问题就是在多种不同的分类方式中，选择出最优的分类方式，数学语言描述为：
[0078][0079]
λ表示对数据集p的一种分类方式，f表示衡量聚类效果的cs指标函数。
[0080]
2.5d集成电路中关键路径上产生的延迟主要由网络结构、工艺变化、温度特性、电压下降和偏置温度不稳定性等特性造成。假设电路中有x条关键路径，每条路径都采用y个特性进行编码，那么可以用x
×
y的矩阵p
x
×y＝{p1,p2,
…
,p
x
}
t
来表示这些路径，每条路径上的延迟d
x
(x＝1,2,
…
,x)将由每个特性所导致的延迟总和所决定，即：d
x
＝p
x
t，t＝{t1,t2,
…
ty}
t
表示每个特性所带来的时间延迟，x条关键路径上的延迟可以表示为：d＝[d1,d2,
…
,d
x
]
t
。从x条关键路径中选择出的r条代表性关键路径可以表示为：pr＝{p1',p2',
…
,pr'}
t
，很显然，并且r＜＜x，那么代表性关键路径上的延迟可以表示为：dr＝[d1',d2',
…
,d'r]
t
，其中dr'＝pr'
·
t,1≤r≤r表示每一条代表性关键路径上的时间延迟。进而，每条关键路径上的延迟便可以采用代表性关键路径上延迟的线性组合来估计，估计出来的延迟可以表示为：
[0081][0082]
据上所述，该过程的核心是代表性关键路径的准确选取，为此，本发明提出了一种基于差分进化算法的聚类过程，该聚类方法无需提前设定子类数量，而是在运行过程中决定最优子类数量，并选取每一个子类的中心作为选择出的代表性关键路径。
[0083]
步骤二使用差分进化算法获取最优聚类方案的过程为：
[0084]
s1、种群初始化，初始种群中每一个个体代表一种聚类方案，种群中共含有np个个体，每个个体初始化为一个k
max
+k
max
×
y维的向量：
[0085][0086]
其中，np表示种群中个体的序号，g为迭代次数，x
np,g
为第g次迭代的第np个个体，kmax
表示所允许的最大的聚类数目，在个体编码中，前k
max
个元素a
np,k
,(k＝1,2,
…
,k
max
)为聚类中心的激活标志，为[0,1]之间的随机数，初始化时将其设置为[0.5,1]之间的随机数；剩余元素s
np,k
(k＝1,2,
…
,k
max
)为第k个子类的聚类中心，均为y维的向量，初始化为从x条关键路径中随机选取的k
max
条关键路径；执行过程中，如果a
np,k
≥0.5，那么对应的第k个聚类中心s
np,k
处于激活状态；否则，处于无效状态；
[0087]
本步骤中初始化种群，初始种群中np个个体(聚类方案)，并用公式(3)进行描述。初始化种群的迭代次数g＝0，初始化种群的个体为x
1,0
,x
2,0
,...,x
np,0
。
[0088]
s2、评估初始种群，获取初始种群的最优聚类方案；
[0089]
首先，对每个个体进行分类，根据关键路径到聚类中心的欧式距离将聚类方案中的所有关键路径划分到不同的子类里；
[0090]
这个分类过程为现有技术，不详述，分类后，每个个体包括子类的数量为k，不同个体之间子类的数量可相同或不同，限定最大为k
max
。
[0091]
然后，对初始种群中的每个个体进行适应度值评估，评估指标cs(k)按下式获取：
[0092][0093]
其中，ck表示第k个子类，k＝1,2,...,k，k表示处于激活状态的聚类数量,k≤k
max
；
[0094]
pa,pb为第k个子类中关键路径，a＝1,2,...,nk，b＝1,2,...,nk，且a≠b，nk表示第k个子类中关键路径的数量；
[0095]
d(pa,pb)表示关键路径pa与pb之间的欧氏距离，
[0096]
avk为第k个子类的平均位置，av
k'
为第k'个子类的平均位置，k'＝1,2,...,k，且k≠k'，avk和av
k'
的计算方式相同，其中avk按下式获取：
[0097][0098]
将评估指标cs(k)值最小的个体最为初始种群的最优聚类方案，作为第0次迭代最优个体x
best,0
；
[0099]
对初始种群每个个体x
1,0
,x
2,0
,...,x
np,0
评估获取的cs指标分别为cs
1,0
,cs
2,0
,...,cs
np,0
，将cs指标值最小的个体最为第0次迭代最优个体x
best,0
。
[0100]
s3、差分变异操作；
[0101]
将第g次迭代生成的最优聚类方案进行变异，生成变异个体，第g次迭代第np个个体生成的变异个体v
np,g
为：g＝0,1,2,
…
,g
max
，g
max
表示允许的最大迭代次数；
[0102][0103]
x
best,g
为第g次迭代生成的最优个体；
[0104]
为第g次迭代时从种群中随机选择的三个当前个体，其中为三个个体中适应度值最优的精英个体；
[0105]
w为过程参数，通过该参数将向量与x
best,g
进行了组合，按下式获取：
[0106]
w＝gp/exp(es)
[0107]
式中，gp＝(g
max-g+1)/g
max
是与迭代次数相关的参数，随着进化过程而递减；参数es＝r
*
/np表示精英个体的状态参数，r
*
表示精英个体在整个种群中的适应度值排序值；
[0108]
f1和f2为两个独立的缩放参数，该参数的计算方式如下：
[0109]
f＝wp
·
n(μ,σ2)+(1-wp)
·
es
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(7)
[0110]
式中，wp＝exp[3
·
(gp-1)]为权重参数，n(μ,σ2)为高斯分布随机数，标准差μ设为0.5，标准差σ设置为0.1，n(μ,σ2)运行两次分别获取f1和f2；
[0111]
本步骤中，以第1次迭代为例进行说明，g＝1，在第1次迭代时当前个体为第0次迭代生成的个体x
1,0
,x
2,0
,...,x
np,0
，按公式(6)生成第1次迭代的变异个体v
1,0
,v
2,0
,...,v
np,0
。
[0112]
s4、交叉操作；
[0113]
交叉操作通过交叉概率参数cr实现了将当前个体x
np,g
与变异个体v
np,g
的交叉混合，产生试验个体u
np,g
，当前个体x
np,g
作为父代个体，具体实现过程如下：
[0114][0115]unp,q,g
表示第np个试验个体的第q维变量，randi(d)是从集合{1,2,
…
,d}中随机选择的一个数，d表示个体维度，保证试验个体u
np,g
中至少有一维是来自变异个体v
np,g
，从而避免与父代个体x
np,g
完全相同；交叉概率参数cr的计算公式如下：
[0116]
cr＝wp
·
n(μ,σ2)+(1-wp)
·
is
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(9)
[0117]
参数is＝rank
np
/np表示父代个体x
np,g
的排序状态值；
[0118]
以第1次迭代为例进行说明，本步骤中将当前个体x
1,0
,x
2,0
,...,x
np,0
与变异个体v
1,0
,v
2,0
,...,v
np,0
进行交叉混合，生成试验个体u
1,0
,u
2,0
,...,u
np,0
。
[0119]
s5、选择操作；
[0120]
差分进化算法采用贪婪选择方式进行精英解的保留，按下式对第g次迭代种群中的个体进行选择：
[0121][0122]
其中，f(
·
)表示适应度函数，指每种聚类方案的cs指标函数；
[0123]
更新在第g次迭代过程中找到的最优聚类方案；
[0124]
以第1次迭代为例进行说明，本步骤中将当前个体x
1,0
,x
2,0
,...,x
np,0
与试验个体u
1,0
,u
2,0
,...,u
np,0
进行一一对比，保护cs指标值小的个体，作为第1次迭代生成的个体，以此结果更新第1次迭代的最优聚类方案。
[0125]
重复执行步骤s3～s5，直至达到最大迭代次数，获取种群最终的最优聚类方案。
[0126]
步骤三获取2.5d集成电路小时延的过程为：
[0127]
步骤三一、选择最优聚类方案中每个子类的聚类中心作为该子类的代表性关键路径，从最优聚类方案的k个子类共获取k条代表性关键路径pk＝{p1',p2',
…
,pk',
…
,pk'}
t
；pk'为第k个子类的代表性关键路径；
[0128]
步骤三二、测量k条代表性关键路径的延时dk＝[d1',d'2,
…
,d'k,
…
,d'k]
t
，d'k为第k条代表性关键路径的延时；
[0129]
步骤三三、将代表性关键路径上的延迟并映射到其他关键路径上，获取2.5d集成电路小时延
[0130][0131]
式中，p为所有关键路径组成的数据集p
x
×y。
[0132]
采用本步骤方法，只需测量有限数量关键路径(代表性关键路径)的延时数据就可以，每个子类测量一次，再利用公式(11)映射出2.5d集成电路中全部关键路径的延时总和，即集成电路的小时延可以在节省大量资源的情况下获取。
[0133]
具体实施方式二：本实施方式对实施方式一作进一步说明，执行步骤s4之后还包括如下解修复步骤：
[0134]
当个体编码中的前k
max
个激活标志参数大于1或者小于0时，分别修复为1或者0；另外，如果所有聚类中心均处于无效状态，则随机选择两个聚类中心，将其激活标志参数在[0.5,1]范围内随机生成，以确保可以将数据至少聚类成2个子类。
[0135]
虽然在本文中参照了特定的实施方式来描述本发明，但是应该理解的是，这些实施例仅仅是本发明的原理和应用的示例。因此应该理解的是，可以对示例性的实施例进行许多修改，并且可以设计出其他的布置，只要不偏离所附权利要求所限定的本发明的精神和范围。应该理解的是，可以通过不同于原始权利要求所描述的方式来结合不同的从属权利要求和本文中所述的特征。还可以理解的是，结合单独实施例所描述的特征可以使用在其它所述实施例中。

技术特征：
1.基于差分进化算法聚类的2.5d集成电路小时延缺陷检测方法，其特征在于，该方法包括以下步骤：步骤一，读取2.5d集成电路关键路径数据作为待聚类数据，并存入待处理的寄存器中；步骤二，使用差分进化算法对寄存器中的待聚类数据进行处理，获取最优聚类方案：首先，对待聚类数据进行初始化形成初始种群，所述初始种群包括k个子类，对初始种群进行评估；然后反复进行变异操作、交叉操作和选择操作来优化聚类过程，直到满足设置的最大迭代次数，获取最优聚类方案；步骤三，根据最优聚类方案选择每个子类中的聚类中心作为代表性关键路径，测量代表性关键路径上的延迟并映射到其他关键路径上，完成检测集成电路关键路径上的小时延缺陷。2.根据权利要求1所述基于差分进化算法聚类的2.5d集成电路小时延缺陷检测方法，其特征在于，待聚类数据为x
×
y的数据集p
x
×
y
＝{p1,p2,
…
,p
x
}
t
，行向量p
x
,x＝1,2,
…
,x表示数据集中的第x条关键路径，x为关键路径的数量，每条路径都采用y个特性进行编码；p
x,y
表示第x条关键路径的第y,y＝1,2,...,y个特性。3.根据权利要求2所述基于差分进化算法聚类的2.5d集成电路小时延缺陷检测方法，其特征在于，步骤二使用差分进化算法获取最优聚类方案的过程为：s1、种群初始化，初始种群中每一个个体代表一种聚类方案，种群中共含有np个个体，每个个体初始化为一个k
max
+k
max
×
y维的向量：其中，np表示种群中个体的序号，g为迭代次数，x
np,g
为第g次迭代的第np个个体，k
max
表示所允许的最大的聚类数目，在个体编码中，前k
max
个元素a
np,k
,(k＝1,2,
…
,k
max
)为聚类中心的激活标志，为[0,1]之间的随机数，初始化时将其设置为[0.5,1]之间的随机数；剩余元素s
np,k
(k＝1,2,
…
,k
max
)为第k个子类的聚类中心，均为y维的向量，初始化为从x条关键路径中随机选取的k
max
条关键路径；执行过程中，如果a
np,k
≥0.5，那么对应的第k个聚类中心s
np,k
处于激活状态；否则，处于无效状态；s2、评估初始种群，获取初始种群的最优聚类方案；首先，对每个个体进行分类，根据关键路径到聚类中心的欧式距离将聚类方案中的所有关键路径划分到不同的子类里；然后，对初始种群中的每个个体进行适应度值评估，评估指标cs(k)按下式获取：其中，c
k
表示第k个子类，k＝1,2,...,k，k表示处于激活状态的聚类数量,k≤k
max
；p
a
,p
b
为第k个子类中关键路径，a＝1,2,...,n
k
，b＝1,2,...,n
k
，且a≠b，n
k
表示第k个子类中关键路径的数量；
d(p
a
,p
b
)表示关键路径p
a
与p
b
之间的欧氏距离，av
k
为第k个子类的平均位置，av
k'
为第k'个子类的平均位置，k'＝1,2,...,k，且k≠k'，av
k
和av
k'
的计算方式相同，其中av
k
按下式获取：将评估指标cs(k)值最小的个体最为初始种群的最优聚类方案，作为第0次迭代最优个体x
best,0
；s3、差分变异操作；将第g次迭代生成的最优聚类方案进行变异，生成变异个体，第g次迭代第np个个体生成的变异个体v
np,g
为：x
best,g
为第g次迭代生成的最优个体；x
r*,g
、为第g次迭代时从种群中随机选择的三个当前个体，其中x
r*,g
为三个个体中适应度值最优的精英个体；w为过程参数，通过该参数将向量x
r*,g
与x
best,g
进行了组合，按下式获取：w＝gp/exp(es)式中，gp＝(g
max-g+1)/g
max
是与迭代次数相关的参数，随着进化过程而递减，g
max
表示允许的最大迭代次数；参数es＝r
*
/np表示精英个体x
r*,g
的状态参数，r
*
表示精英个体x
r*,g
在整个种群中的适应度值排序值；f1和f2为两个独立的缩放参数，该参数的计算方式如下：f＝wp
·
n(μ,σ2)+(1-wp)
·
es式中，wp＝exp[3
·
(gp-1)]为权重参数，n(μ,σ2)为高斯分布随机数，标准差μ设为0.5，标准差σ设置为0.1，n(μ,σ2)运行两次分别获取f1和f2；s4、交叉操作；交叉操作通过交叉概率参数cr实现了将当前个体x
np,g
与变异个体v
np,g
的交叉混合，产生试验个体u
np,g
，当前个体x
np,g
作为父代个体，具体实现过程如下：u
np,q,g
表示第np个试验个体的第q维变量，randi(d)是从集合{1,2,
…
,d}中随机选择的一个数，d表示个体维度，保证试验个体u
np,g
中至少有一维是来自变异个体v
np,g
，从而避免与父代个体x
np,g
完全相同；交叉概率参数cr的计算公式如下：cr＝wp
·
n(μ,σ2)+(1-wp)
·
is参数is＝rank
np
/np表示父代个体x
np,g
的排序状态值；s5、选择操作；差分进化算法采用贪婪选择方式进行精英解的保留，按下式对第g次迭代种群中的个体进行选择：
其中，f(
·
)表示适应度函数，指每种聚类方案的cs指标函数；更新在第g次迭代过程中找到的最优聚类方案；重复执行步骤s3～s5，直至达到最大迭代次数，获取种群最终的最优聚类方案。4.根据权利要求3所述基于差分进化算法聚类的2.5d集成电路小时延缺陷检测方法，其特征在于，执行步骤s4之后还包括如下解修复步骤：当个体编码中的前k
max
个激活标志参数大于1或者小于0时，分别修复为1或者0；另外，如果所有聚类中心均处于无效状态，则随机选择两个聚类中心，将其激活标志参数在[0.5,1]范围内随机生成，以确保可以将数据至少聚类成2个子类。5.根据权利要求1至4任一权利要求所述基于差分进化算法聚类的2.5d集成电路小时延缺陷检测方法，其特征在于，步骤三获取2.5d集成电路小时延的过程为：步骤三一、选择最优聚类方案中每个子类的聚类中心作为该子类的代表性关键路径，从最优聚类方案的k个子类共获取k条代表性关键路径p
k
＝{p
′1,p
′2,
…
,p
′
k
,
…
,p
′
k
}
t
；p
′
k
为第k个子类的代表性关键路径；步骤三二、测量k条代表性关键路径的延时d
k
＝[d
′1,d'2,
…
,d'
k
,
…
,d'
k
]
t
，d'
k
为第k条代表性关键路径的延时；步骤三三、将代表性关键路径上的延迟并映射到其他关键路径上，获取2.5d集成电路小时延小时延式中，p为所有关键路径组成的数据集p
x
×
y
。

技术总结
基于差分进化算法聚类的2.5D集成电路小时延缺陷检测方法，属于集成电路测试优化技术领域，本发明为解决传统2.5D集成电路小时延缺陷检测方法测试成本开销大、测试速度慢的问题。本发明方法包括：步骤一，读取2.5D集成电路关键路径数据作为待聚类数据；步骤二，使用差分进化算法对寄存器中的待聚类数据进行处理，获取最优聚类方案：无需提前设定分组数量，可以在运行过程中确定最佳分组数量，通过变异、交叉和选择等操作实现对聚类过程的优化，确定最佳聚类方案；步骤三，根据最优聚类方案选择每个子类中的聚类中心作为代表性关键路径，测量代表性关键路径上的延迟并映射到其他关键路径上，完成检测集成电路关键路径上的小时延缺陷。缺陷。缺陷。


技术研发人员：邓立宝 李春磊 狄原竹 乔立岩
受保护的技术使用者：哈尔滨工业大学（威海）
技术研发日：2023.07.03
技术公布日：2023/10/6