基于蚁群-遗传混合算法的系统芯片低功耗测试方案
- 格式：pdf
- 大小：121.58 KB
- 文档页数：1
・２０・ 科技论坛 基于蚁群一遗传混合算法的系统芯片低功耗测试方案 张培明’ （１、黑龙江工程学院电气与信息工程学院，黑龙江哈尔滨 商进ｚ李晓龙’ １５００５０ ２、无锡职业技术学院控制技术学院，江苏无锡２１４１２１） 摘要：针对系统芯片测试功耗快速增加的特点，提出了一种有效的低功耗测试方案。该方案将测试向量的海明距离作为测试功耗 优化的目标，将测试功耗优化问题转化为对测试向量进行海明距离排序问题，采用一种改进的蚁群一遗传混合算法对测试向量进行排序， 从而使测试功耗最低。针对ＩＳＣＡＳ ８９部分标准电路实验结果表明，该方案能有效的降低测试功耗。 关键词：系统芯片；蚁群算法；遗传算法；低功耗测试 随着科技的发展，系统芯片的应用越来越广泛，对系统芯片的 测试也越来越重要。针对芯片测试过程中测试功耗较高的问题，近 年来许多降低功耗的测试技术被提出。其中一种重要的方法就是基 于测试向量修改的技术。采用这种技术可以修改测试过程中的施加 的测试向量顺序，这种方法能有效的降低测试过程中的功耗，该方 法的缺点是效率较低，但优点是不需要增加硬件成本，同时移植性 较好，因此在实际测试中效果较好，得到了广泛的应用。 １ ＣＭＯＳ电路功耗模型 公式（１）给出了芯片测试过程中节点电压发生跳变时节点电容 由于充放电所消耗的功耗 的计算公式 ＝ １ ａＣ％， （１） 上式中，Ｖ 是电源电压，节点的负载电容为Ｃ，仅为节点在单 个时钟周期内发生翻转的次数，ｆ是时钟频率。 由公式（１）可知，将两个连续的测试向量（ 一 ， ）输入待测 电路时，在电路所消耗的功耗为 Ｐ（ ，， ）＝＞‘１／２Ｃ 厂 一 … （２） 在目前阶段，降低电路节点总的翻转次数是目前广泛采用的降 低功耗的测试方法。 ２算法原理 由于测试向量的海明距离和测试向量运行时电路节点的翻转 次数成正比，这样在对测试功耗进行优化时优化的目标就变为测试 向量的海明距离，因此通过海明距离重新排序测试向量，使测试向 量之间的海明距离最小，从而达到对测试功耗进行优化的目标。 海明距离排序与经典的旅行商（１’ｓＰ）问题相似，也是ＮＰ完全 问题。旅行商问题属于优化组合问题，指单一旅行者要访问多个城 市时，如何能够获得访问每个城市一次后再回到出发城市的最短路 径，显然，随着城市的增加结果也急剧增大，如果采用枚举法，那么 算出如此之大的总路径，几乎是不可能的。近年来，遗传算法（ＧＡ） 和蚁群算法（ＡＣＯ）都被用于解决这类问题，并取得了很好的效果。 遗传算法的基本原理是把要求问题的参数进行编码，然后再通 过染色体对此优化，由于这个过程并不针对问题参数本身，因此函 数的约束条件不会对此作出限制；另外，为了避免陷入局部最优的 可能，遗传算法具有将并行搜索隐行的特点。它的缺点是对于比较 复杂的组合优化问题，会增加整个过程的搜索时间，同时搜索空间 也会变大，容易出现早熟收敛现象；另外遗传算法也对初始种群很 敏感，其解的质量和算法效率往往会被所选择的初始种群所影响 。 蚁群算法作为一种启发式优化算法，最早是由意大利人Ｄｏｒｉｇｏ 于１９９２年提出的。作为当前启发式算法的研究热点，蚁群算法一经 提出就在国内外学术界得到了广泛关注。蚁群算法在求解旅行商问 题时得到了成功应用。这种算法的原理是蚂蚁在寻找食物过程中会 在走过的路径上留下一种称之为信息素的物质，并能感受到这种物 质的强度，使蚂蚁总是朝着强度最高的方向运动。 蚁群算法和遗传算法具有互补性，二者可以有机的融合在一 起，发挥各自长处，克服各自缺点。Ａｂｂａｔｔｉｓｔａ Ｆ等最早将蚁群算法 和遗传算法有机的互相融合在一起，并利用仿真实验对此进行验 证，证明了方法的可行性，之后不断有学者通过把二者有机的融合 在一起以求解各种组合优化问题，都获得了成功。 ３算法实现 为了实现待测电路的低功耗测试，本文采用了一种改进的蚁群 一遗传混合算法。在这个方法中，低功耗测试问题被看做传统的旅 行商问题，测试向量被看成城市，测试向量之间的海明距离被看成 是城市距离，以其找到一个晟短路径，使测试中电路节点的翻转次 数最少，从而使测试功耗最低。具体步骤如下： Ｓｔｅｐ １初始化参数；Ｓｔｅｐ ２分配每只蚂蚁的初始位置；Ｓｔｅｐ ３ 蚂蚁个体根据状态转移概率公式计算的概率选择城市；Ｓｔｅｐ ４修改 禁忌表指针，移动蚂蚁到新的城市，同时移动该城市到蚂蚁个体的 禁忌表中；Ｓｔｅｐ ５经过ｎ个时刻，蚂蚁ｋ可走完所有的城市，完成一 次循环，计算蚂蚁ｋ走的总路径长度；Ｓｔｅｐ ６若ｋ＜Ｐ，则跳转到 Ｓｔｅｐ ４，否则执行Ｓｔｅｐ ７；Ｓｔｅｐ ７ Ｐ个分配方案进行迭代交换，形成 更多５ｐ的子分配方案，与原分配方案一起共６ｐ个分配方案，选择 新的分配方案；Ｓｔｅｐ ８在Ｓｔｅｐ ６的基础上进行染色体的编码，获得 父代；Ｓｔｅｐ ９根据交叉概率，采用顺序一致交叉法，形成子代，求出 总路径长度；Ｓｔｅｐ １０比较Ｓｔｅｐ ６和Ｓｔｅｐ ９的最好解，取最小值作 为变异的父代；Ｓｔｅｐ １ １随机产生３个交换位置，两两交换位置计算 每次交换后的路径长度，并与变异的父代比较，取最小者作为当前 迭代最好解；Ｓｔｅｐ １２更新信息素的全局和当代最短路径信息素； Ｓｔｅｐ １３判断是否最大迭代次数，满足则输出最优解，否则转入Ｓｔｅｐ ２。 ４实验结果 为了对本文所提方案的有效性进行验证，我们将部分ＩＳＣＡＳ８９ 基准电路采用该方法进行测试，由ＡＴＰＧ工具ＡＴＡＬＡＮＴＡ生成本 次实验所需测试集。在这个方案中，基准电路ｓ９２３４功耗降低效果 最好，为３５．１８％，基准电路ｓ３８４１７功耗降低效果最低为１５．９８％，六 个电路的功耗降低平均为２４．０７％。可见，采用本文所提方案对测试 向量重新排序后，电路的测试功耗均有不同程度的降低。 结束语 针对系统芯片测试功耗较高的问题，本文提出了一种基于蚁群 一遗传算法的低功耗测试方案。该方案利用融合了遗传算法的蚁群 算法对测试过程中施加的测试向量施加顺序进行了修改，不需要对 待测电路的硬件做任何改动，同时也不需了解待测电路的内部结 构，能较好的保护知识产权。基于部分ＩＳＣＡＳ ８９基准电路的实验表 明，该方案能较好的降低测试功耗。 参考文献 【１】熊道勇，肖人岳．遗传算法和蚂蚁算法混合求解旅行商问题［Ｊ１．科 学技术与工程，２００９，９（１９）：５８１７—５８１９． 【２】黄明，王聪，梁旭．改进型遗传蚁群混合算法求解旅行商问题『Ｊ１． 大连交通大学学报，２０１ １，３２（２）：８６—８８． ［３］陈铁梅，罗家祥，胡跃明．基于蚁群一遗传算法的贴片机喂料器分 配优化研究Ⅲ．控制与决策，２０１ １，２６（６）：９２９—９３２． 黑龙江省教育厅科学技术研究项目（１２５３１５６５）。 作者简介：张培明，男，黑龙江工程学院电气与信息工程学院副教授，研究方向为故障诊断与自动化测试。
