随着后信息时代的到来,工业界集成电路的制造工艺突飞猛进,已经从微米级时代进入到纳米级时代,从而使得超大规模集成电路制造能力日新月异。在工业界集成电路的制造工艺飞速前进的同时,集成电路的设计水平却跟不上制造工艺水平的发展。这便形成了一个矛盾,这个矛盾被称之为“剪刀差”,它已经成为制约集成电路产业发展的一个关键问题。采用模块化设计思想可以解决该关键问题,这种模块化设计被称之为“IP核复用”。IP核复用可以提高设计效率和减小设计的复杂度,它可以大大提高设计人员的设计能力。现代电子产品市场对集成电路的上市时间、低功耗、便携性和测试成本等要求越来越高,因此通过IP核复用的方法可以显著提高产品的开发效率,同时将根据实际需要各种已经验证的IP核由集成开发商集成到一个片上系统(SoC,System on Chip)上。正是由于SoC的可以缩短产品上市时间、实现低功耗和良好的便携性以及日益完善的性能指标,使得SoC广泛的应用到现代电子产品当中,站在国家战略层面上来讲,它已经成为了一种关键的核心部件。IP核复用方法的使用,虽然可以解决制造工艺水平和设计能力之间的矛盾,但与此同时,它也带来测试问题方面的挑战,即测试的难度越来越大,测试成本快速增长,如何通过可测性设计优化方法来减少测试成本成为一个关键问题。本论文旨在采用基于群体智能的方法进行可测性设计的优化,从而减少SoC测试成本,研究内容主要针对扫描链平衡设计、三维wrapper扫描链多目标优化设计和采用硬晶片的三维堆叠SoC测试规划问题。论文围绕国家自然科学基金“基于量子算法的SOC测试规划研究”以及广西自动检测技术与仪器重点实验室基金“三维SoC可测性设计与优化方法研究”等项目的研究任务,针对面向扫描设计的SoC可测性设计优化理论分析与方法进行了研究。课题取得的主要研究成果为:1.对扫描链的平衡设计进行了优化方法研究。确定了扫描链平衡设计的问题描述,分析了BFD(Best Fit Decreasing)方法、MVA(Mean Value Approximation)方法和MVAR(Mean Value Allowance Residue)等主要方法存在的问题。提出了采用BBO(Biogeography Based Optimization)算法的扫描链平衡设计方法,在设置最大迁出速率、最大迁入速率、最大变异概率、种群规模、最大迭代代数,待选解的维数和Wrapper扫描链的条数之后,通过实施迁徙操作和变异操作,在最大迭代次数范围内实现Wrapper扫描链平衡设计,使得Wrapper扫描链均衡化,从而达到IP核测试时间最小化的目的。本算法选取ITC’02(International Test Conference 2002)测试标准电路集中的典型IP核作为实验对象,实验结果表明本算法相比BFD等算法,能够进一步减少最长Wrapper扫描链的长度,从而减少IP核的测试时间。2.研究了一种采用收敛速率的BBO算法复杂度分析方法,并针对wrapper扫描链设计该NP hard问题的首次到达目标子空间的期望下界进行了理论分析。由于BBO方法起源于自然界的生物迁徙等机制,包含了复杂的随机行为,因此其理论分析非常困难,而且严格的理论基础还比较缺乏。证明了BBO算法中的种群序列是吸引马尔科夫链,并对BBO算法的收敛性进行了分析。目前还没有报道BBO算法针对扫描链平衡设计该NP hard问题的复杂度下界的理论分析手段和方法。通过揭示BBO算法的收敛速率与首次到达目标子空间的期望两者之间的相互关系,确定了BBO算法的一种复杂度分析方法,为扫描链平衡设计优化问题提供了理论保障。3.为了减少测试时间,提出了一种OBBO(Opposition-based learning and Biogeography Based Optimization)的随机优化方法。该方法将将OBL(Opposition-Based Learning)算子引入到BBO算法中,通过迁徙算子、OBL算子和变异算子,实现最小化最长Wrapper扫描链,从而达到最小化测试时间的目的。实验结果表明了本算法的有效性。4.对三维IP核测试Wrapper扫描链设计进行了优化研究。建立了三维Wrapper扫描链设计的问题描述。证明了多目标Firefly算法的种群序列是吸引马尔科夫链,并对多目标Firefly算法的收敛性进行了分析。分别提出了采用多目标差分算法和多目标Firefly算法的三维测试Wrapper扫描链设计方法,使得封装扫描链均衡化以及使用TSV(Through Silicon Vias)资源最少,从而达到IP核测试时间最小化和TSV费用最少的目的。本文以ITC’02测试标准电路集中的典型IP核为实验对象,实验结果表明本算法相比NSGAII(Nondominated Sorting Genetic Algorithm II),能够获得更好的Pateto最优解集。5.研究了三维堆叠SoC的测试规划。确定了三维堆叠SoC的测试规划的问题描述。针对GWO(Grey Wolf Optimization)算法在发起攻击行为的时候,容易陷入局部最优而停滞,而DE算法有很强的搜索能力,因此提出一种HGWO(Hibridizing Grey Wolf Optimization)方法,在发起攻击行为的时候将DE算法集成到GWO中,用来更新灰狼Alpha,Beta和Delta的位置,从而使得GWO跳出停滞的局部最优。采用了广泛使用的单峰标准测试函数,多峰标准测试函数以及固定维数多峰标准测试函数共23个标准测试函数对HGWO算法进行测试。建立了三维堆叠SoC的测试规划的数学模型,提出了基于HGWO算法的三维堆叠SoC测试规划方法,实验结果表明了HGWO算法的优越性。