· 20
科技论坛
基于蚁群－遗传混合算法的系统芯片低功耗测试方案
张培明1商进2李晓龙
（1、黑龙江工程学院电气与信息工程学院，黑龙江哈尔滨1500502、无锡职业技术学院控制技术学院，江苏无锡214121）
摘要：针对系统芯片测试功耗快建增加的特点，提出了一种有效的低功耗测试方案。该方案将测试向量的海明距离作为测试功耗优化的目标，将测试功耗优化同题转化为对测试向量进行海明距离排序问题，采用一种改进的取群-遗传混合算法对测试向量进行排序，从而使测试功耗最低。针对ISCAS89部分标准电路实验结果表明，该方案能有效的降低测试功耗。
关键词：系统芯片；奴群算法；遗传算法：低功耗测试
和遗传算法有机的互相融合在一起，并利用仿真实验对此进行验
随着科技的发展，系统芯片的应用越来越广泛，对系统芯片的
测试也越来越重要。针对芯片测试过程中测试功耗较高的间题近
证，证明了方法的可行性，之后不断有学者通过把二者有机的融合
年来许多降低功耗的测试技术被提出。其中一种重要的方法就是基
在一起以求解各种组合优化间题，都获得了成功。
于测试向量修改的技术。采用这种技术可以修改测试过程中的施加的测试向量顺序，这种方法能有效的降低测试过程中的功耗，该方
3算法实现
为了实现待测电路的低功耗测试，本文采用了一种改进的数群
法的缺点是效率较低，但优点是不需要增加硬件成本，同时移植性-遗传混合算法。在这个方法中，低功耗测试间题被看做传统的旅较好，因此在实际测试中效果较好，得到了广泛的应用。
行商间题，测试向量被看成城市，测试向量之间的海明距离被看成
1CMOS电路功耗模型
公式(1)给出了芯片测试过程中节点电压发生跳变时节点电容由于充放电所消耗的功耗P。的计算公式
acv
是城市距离，以其找到一个最短路径，使测试中电路节点的翻转次数最少，从面使测试功耗最低。具体步骤如下：
Step1初始化参数;Step2分配每只蚂蚁的初始位置;Step3 蚂蚊个体根据状态转移概率公式计算的概率选择城市；Step4修改
Pa=2
禁忌表指针，移动蚂蚊到新的城市，同时移动该城市到蚂蚊个体的
1）
上式中，V是电源电压，节点的负载电容为C,α为节点在单
禁忌表中；Step5经过n个时刻.蚂蚊k可走完所有的城市，完成一
个时钟周期内发生翻转的次数，是时钟频率。
由公式(1)可知，将两个连续的测试向量（V。-1,V。)输人待测电路时，在电路所消耗的功耗为
P(V-V)=Z1/2C,VBpa,J
(2)
在目前阶段，降低电路节点总的翻转次数是目前广泛采用的降低功耗的测试方法。
2算法原理
由于测试向量的海明距离和测试向量运行时电路节点的翻转次数成正比，这样在对测试功耗进行优化时优化的目标就变为测试
向量的海明距离，因此通过海明距离重新排序测试向量，使测试向量之间的海明距离最小，从而达到对测试功耗进行优化的目标
海明距离排序与经典的旅行商(TSP)间题相似，也是NP完全间题。旅行商间题属于优化组合间题，指单一旅行者要访间多个城市时，如何能够获得访间每个城市一次后再回到出发城市的最短路径，显然，随着城市的增加结果也急剧增大，如果采用枚举法，那么算出如此之大的总路径，几乎是不可能的。近年来，遗传算法(GA) 和蚊群算法(ACO)都被用于解决这类间题，并取得了很好的效果。
遗传算法的基本原理是把要求间题的参数进行编码，然后再通过染色体对此优化，由于这个过程并不针对间题参数本身，因此函数的约束条件不会对此作出限制；另外，为了避免陷人局部最优的可能，遗传算法具有将并行搜索隐行的特点。它的缺点是对于比较复杂的组合优化间题，会增加整个过程的搜索时间，同时搜索空间也会变大，容易出现早熟收敏现象；另外遗传算法也对初始种群很敏感，其解的质量和算法效率往往会被所选择的初始种群所影响。
蚁群算法作为一种启发式优化算法，最早是由意大利人Dorig 于1992年提出的。作为当前启发式算法的研究热点，敏群算法一经提出就在国内外学术界得到了广泛关注。蚁群算法在求解旅行商间题时得到了成功应用。这种算法的原理是蚂蚊在寻找食物过程中会在走过的路径上留下一种称之为信息素的物质，并能感受到这种物质的强度，使蚂蚊息是着强度最高的方向运动。
蚁群算法和遗传算法其有互补性，二者可以有机的融合在一起，发挥各自长处，克服各自缺点。AbbatistaF等最早将群算法
次循环，计算蚂蚊k走的总路径长度；Step6若K 2
4实验结果
为了对本文所提方案的有效性进行验证，我们将部分ISCAS89 基准电路采用该方法进行测试，由ATPG工具ATALANTA生成本次实验所需测试集。在这个方案中，基准电路s9234功耗降低效果最好，为35.18%，基准电路s38417功耗降低效果最低为15.98%，六个电路的功耗降低平均为24.07%。可见.采用本文所提方案对测试向量重新排序后，电路的测试功耗均有不同程度的降低。
结束语
针对系统芯片测试功耗较高的间题，本文提出了一种基于蚁群-遗传算法的低功耗测试方案。该方案利用融合了遗传算法的敏群算法对测试过程中施加的测试向量施加顺序进行了修改，不需要对待测电路的硬件做任何改动，同时也不需了解待测电路的内部结构，能较好的保护知识产权。基于部分ISCAS89基准电路的实验表明，该方案能较好的降低测试功耗。
参考文献
[1]熊道勇，肖人岳.遗传算法和妈奴算法混合求解旅行商问题[J]科学技术与工程,2009.9(19):58175819
[2]黄明，王聪，梁旭.改进型遗传奴群混合算法求解旅行商问题[] 大连交通大学学报,2011.32(2):86-88
[3]陈铁梅，罗家祥，胡跃明.基于蚁释-造传算法的贴片机喂科器分配优化研究[J]控制与决策,2011,26(6):929-932
黑龙江省教育厅科学技术研究项目（12531565）
作者简介：张培明，男，黑龙江工程学院电气与信息工程学院制教投，研究方向为故障诊断与自动化测试，