差分进化算法改进及其在2.5D集成电路测试中的应用

发布时间：2020-11-21 06:25

　　 优化问题在科学研究和工程应用中无处不在,与此相关的众多研究人员需要性能强大的优化算法解决这些对他们的日常工作生活至关重要的问题。对自然科学和计算机学科的交叉研究衍生了一些智能优化算法,差分进化算法作为一种较新的全局优化算法,其种群进化过程充分体现了达尔文进化论中“物竞天择,适者生存”的核心思想。自1995年被提出以来,差分进化算法以其鲁棒性强原理简单有效等优点愈发受到人工智能领域研究人员的青睐。作为本文改进算法的实际应用对象,基于插入层的2.5维集成电路采用硅通孔等结构有效克服了当前集成电路中内连线延时和功耗等制约芯片性能提升的问题,利用优化算法对其进行可测性设计及解决测试成本问题是保证2.5维集成电路可靠性及广泛应用的重要保障。本文在介绍了差分进化算法基本结构和原理的基础上,针对其控制参数、变异过程和交叉过程优缺点,进行了算法改进研究,并将改进算法应用于2.5维集成电路测试优化方案设计中。本文的主要研究内容如下:(1)在分析经典差分进化算法二项交叉种群多样性差,优化效率低等固有缺陷的基础上,本文提出“基于多角度搜寻旋转交叉策略的改进自适应差分进化算法”。该方法通过引入旋转控制向量将交叉操作中的搜索范围扩大到变异个体和父代目标个体圆周范围内,从而大大增加种群多样性,并随种群进化缩小搜索范围。为了平衡算法的搜索速率和种群多样性,完整的交叉操作结合了本文所提旋转交叉算子和经典二项交叉算子。在CEC2013标准测试集上的实验表明,结合本交叉算子之后的改进算法对于提升原始算法优化性能和收敛速率具有较好的效果,优化性能提升了57%~96%。(2)针对差分进化算法经典变异操作中变异因子参数选择敏感以及差分操作随机偏差扰动搜索步进较大的缺陷,从增强算法局部搜索能力的角度提出一种基于个体适应值和距离差异的自适应变异操作取代原有变异因子及差分操作,增强局部搜索能力的同时,消除了参数选择对优化效果的影响。同时,基于亲密度传播的聚类算法种群自动归类划分操作,使得各个子种群之间可以并行操作,增加了种群的优化速度。在CEC2013测试集上的实验表明,结合该变异算子的优化算法相比于原有算法,优化效率有大幅提升,优化性能提升50%~88%。此外,本文将所提两种改进算法结合进行实验验证,实验结果显示结合后的算法效果优于原有算法,从而证明这两种算法的普适性和有效性。(3)最后,本文进行了2.5维SOC测试资源优化技术研究。根据各IP核和晶片的排布位置及其相关测试信息,并将测试功耗和测试硬件开销等约束条件结合在内,建立2.5维SOC的测试调度及扫描链平衡设计数学模型,并采用本文所提改进差分进化算法对其进行求解,从而确定IP核内扫描链封装情况及晶片测试顺序和分组。在ITC’02标准测试集和商业芯片数据集上的实验表明,在测试功耗等约束条件的限制下,本文所提出的基于改进DE算法的测试调度方法能够有效减小2.5维SOC的测试总开销。同时,采用改进差分进化算法进行扫描链平衡设计,可以实现测试时间成本和硬件成本的折中方案,并获得更加平衡的测试封装扫描链。
【学位单位】：哈尔滨工业大学
【学位级别】：硕士
【学位年份】：2018
【中图分类】：TP18;TN407
【部分图文】：

- 48 -c） DE/ctb/1/bin 对比结果图 3-6 三种 DE 算法与改进算法结果对比同时，为了观察本文所提算子对于原有算法收敛速度和优化性能的改善，分在单峰函数，多峰函数以及组合函数中抽取了四个测试函数进行实验分析，如3-7所示。其中，红色、绿色和黑色曲线分别代表DE/rand/1、DE/best/1和DE/c-t-b/1种算法，为了区分未结合 DPDE 变异策略和结合该变异策略之后的算法，用不的标记来区分，“*”、“+”和五角星分别代表三种算法分别和 DPDE 结合之后的进算法。

表 4-4 测试封装扫描链分配实验结果内扫描链 Die 内分布DE P1 P2LMaxCost LMaxCost LMaxCostCase1 3203 3221 3224 3242 4439 4457Case2 3191 3209 4636 4642 3718 3736Case3 3186 3204 3511 3517 3794 3812Case4 3194 3212 4153 4159 3453 3471Case5 3184 3202 3223 3229 3424 3442Case6 3194 3212 3336 3342 3910 3928表 4-4 中展示了 6 种不同内扫描链的 Die 归属情况，篇幅所限本文不再体标注。LMax代表封装后最长扫描链长度，Cost 表示综合扫描链长度以及相扫描链封装的硬件消耗后的测试消耗。相比于按顺序进行内扫描链封装和随内扫描链封装的实验结果，改进 DE 可以取得更加平衡的封装结果同时硬件耗较少，从而验证了该测试封装扫描链平衡设计的有效性。图 4-6 和图 4-一步展示了三种平衡方法封装后最长封装链长度以及总开销比较。

图 4-7 三种平衡方法封装后总开销比较4.3.3 结果分析在 ITC’02 标准测试集中 SOC（p93791）的13号 IP 核上的实验显示，改进 DE 算法指导内扫描链封装对于扫描链平衡设计和减少硬件消耗都具显优化效果，相比于随机排列内扫描链和按顺序组合内扫描链优化效率可到 45%。这是因为改进 DE 算法充分考虑了跨 Die 分布的 IP 核的特点，有地设计了封装扫描链的组合方式，从而在扫描链平衡和硬件开销之间做出的折中。RDL 消耗数量的减少在很大程度上提高了芯片的可靠性和稳定性4.4 2.5 维集成电路系统级测试调度方法本节重点对系统级测试调度优化算法展开研究，首先建立了系统级测度的数学模型；然后，将本文所提的基于多角度搜寻旋转交叉策略的改进进化算法和基于动态子种群划分自适应变异策略的改进 DE 算法组合的混进算法应用于解决测试调度数学模型从而实现系统级测试开销最小化，并
【参考文献】

相关期刊论文 前6条

1 费腾;张立毅;;现代智能优化算法研究[J];信息技术;2015年10期

2 王伟;林卓伟;陈田;刘军;方芳;吴玺;;功耗约束下的3D多核芯片芯核级测试调度算法[J];电子测量与仪器学报;2012年07期

3 邓立宝;乔立岩;俞洋;彭喜元;;基于差值二次分配的扫描链平衡算法[J];电子学报;2012年02期

4 俞洋;陈叶富;彭宇;;基于平均值余量的Wrapper扫描链平衡算法[J];仪器仪表学报;2011年10期

5 牛道恒;王红;杨士元;成本茂;靳洋;;Re-Optimization Algorithm for SoC Wrapper-Chain Balance Using Mean-Value Approximation[J];Tsinghua Science and Technology;2007年S1期

6 杨建国,李蓓智,俞蕾;基于免疫遗传算法的优化设计[J];机械设计;2002年09期

相关博士学位论文 前3条

1 常郝;三维集成电路测试关键技术研究[D];合肥工业大学;2015年

2 龚文引;差分演化算法的改进及其在聚类分析中的应用研究[D];中国地质大学;2010年

3 赵光权;基于贪婪策略的微分进化算法及其应用研究[D];哈尔滨工业大学;2007年

相关硕士学位论文 前3条

1 刘华华;多种资源约束下集成电路芯片最终测试生产调度优化方法研究[D];西南交通大学;2015年

2 刘蓓;三维集成电路测试时间的优化方法研究[D];合肥工业大学;2011年

3 张永光;芯片设计中的可测试性设计技术[D];浙江大学;2005年

本文编号：2892672