MCM基板互连测试的单探针路径优化研究
第 1O卷 第 1期
2005年 2 月
电路与系统学报
JOURNAL OF CⅡ CUITS AND SYSTEM S
V01．1O NO．1
February， 2005
文章编 号 ：1007．0249(2005)01．Ol35．O5
MCM基板互连测试 的单探针路径优化研究
许川佩 2， 许君华 2， 莫玮 2， 李智 2
(1．西 安电子 科技 大学 机 电工 程学 院， 陕西 西 安 710071：2．桂林 电子工业 学 院 电子 工程 系，广 西 桂 林 541004)
摘耍 ：针对 MCM 基板 互连测试所采用 的单探针技术 ，本文提 出一种基 于蚁群算法 的单探针路径优化算法 ，通过
设定合 适的规则 ，引导探 针的移动 ，缩 短探针移动 的距 离 ，达到减少测 试时间提 高 MCM 生产效 率的 目的 。从基 于
MCM 标准电路的仿 真结果看，采 用蚁群算法得 到的探针测试路径长度远远优 于其它算法所得到 的。
关复词 ：MCM 基板；互连测试 ：单探针 ；蚁群算法
中圈分类号 ：TP274；TN407 文献标识码 ：A
1 引言
目前 多芯 片组 件 (Multi—Chip Module，MCM )基 板互 连 测试 通 常采用 单 探针 或 双探 针 法进 行 短路
和断路故障测试 。
这 种探 针 测试 是在 飞 针测 试床 上进 行 的 ，测试 的时 间主要 花 费在 探针 的移 动上 ，为 了减少 移 动 定
位 时 间， 除 了提 高探 针 移动 速 度外 ，减 小探 针 移 动 的总距 离 是一 种有 效 的方 法 。对 于 MCM 基 板 ，其
表 面焊 区 的布局 及 网络 分布 总存 在 一条 使探 针 移 动最 短 的路径 。如何 根据 MCM 基 板焊 区 和 网络 的分
布情 况求 解 出探 针运 动 的最 短 或较 短路 径 是探 针测 试 (飞 针测 试 )技 术 的关键 。本 文将 围绕 单 探针 测
试 提 出一 种探 针移 动路 径 优化 的新方法 。
已有 学 者采 用传 统求 解 货 郎担 问题 (Traveling Salesman Problem，TSP)的算 法 来解 决探 针 测试 路
径的优化问题Il 】，但这些算法 的求解过程只限于小规模 的模拟，通常采用 的实验对象是几十个 网络
的电路，而 MCM 的发展速度很快 ，高密度 、大规模已经是 MCM 发展的趋势。此外，已有 的探针测
试路 径优 化 算法 在 寻找路 径 的 时候 ，主 要是 基 于对 局部 优 化 的考虑 而进 行 寻优 工 作 的 ，这就 使 得算 法
在全 局优 化 方面 表现 出 一定 的局 限性 ，为 了能 够得 到较 优 的探 针测 试路 径 ，算 法 必须 进行 遍 历方 式 的
试 探 工作 ，以此 来寻 找较 好 的焊 区序 列 ，最 终减 少 测试 路径 的长度 ，这 就 使得 算法 的运行 时 间会 随 着
MCM 规模 的增大急剧增加 。基于对算法运行时间和生成路径长度的考虑，本文提 出一种采用蚁群算
法 来解 决探 针 测试路 径 优化 问题 的方法 。
2 蚁群 算法求解单探针路 径的数学模 型
求解探针测试的路径就是在待测焊区集合 中寻找一个序列，使得测试路径 的总距离最短 。虽然最
短路径 是 必然 存在 的，但 实 际寻 找到 的路 径 往往 不 是一 条最 短 的路径 ，而 是一 条较 短路 径 。求 解 探针
路径时首先由 CAD软件提供 的电路 网表 (netlist)得到 MCM 基板的网络互连 以及各焊区的坐标数据 ，
这样 就 可 以求 得两个 焊 区 间 的欧几 里距 离 (Euclidean Distance)一 探 针 在 两个 焊 区 间移 动 的距离 。令 ：
I={，1'I ，??，， }是 MCM 基板互连网络的集合，每个互连网络I (1≤i≤JⅣ)包含一个焊区集合
= ，P2，?一， }，其中n 是，。的焊区数，JⅣ是MCM基板网络的个数。探针路径优化问题的解就是
一 组 焊 区 的序列 ( ，t，，? 一t )，其 中 tf∈Pi， i=1?N ， J=1?，l，。探 针 需要 移 动 的距 离 是 ：
Ⅳ一1
C=∑8(t t+】) (1) 其中 (f t+】)是t 到t 的欧几里距离。
收稿 日期 ：2004．07．23 修订 日期 ：2004．10．10
基金项 目：国家 自然科 学基 金资助项 目 (60266001)
维普资讯 http://www.cqvip.com
电路与系统学报 第 l0卷
2．1 定 义
本 文 为 了叙述 的需要 ，给 出求解 单 探针 路 径所 涉 及 的名 词 以及 求解 过 程 的定 义 ：边 是 两个焊 区 间
的连线 ，其长度就是两个焊区的欧几里距离；路径是一组边 的有序集合 ；完整路径是蚂蚁在访问完所
有 焊 区后 得 到 的焊 区 结点 序列 ；子路 径是 蚂蚁 在 没有 得 到完 整路 径 之前 访 问过 的焊 区 结 点序 列 ：待访
问焊 区集 合 是蚂蚁 还 没有 访 问过 的焊 区 节 点集合 。
单探针路径的求解过程定义如下：设V={c1，c ，?，c }是一组焊区的集合，A=I(r， )：，．， V}是一组
边的集合，5(r， )是 ，．、 两点的欧几里距离。该问题的已知条件是各个焊区的坐标，求解的目标是得
到 一 条 最 短 的 路 径 序 列 ， 该 序 列 中 包 含 了每 一 个 焊 区 。 本 文 研 究 的 对 象 属 于 对 称 性 TSP， 即
6(r， )=6(s，，．)。
蚂蚁算法求解探针路径时，除了从已知条件中求得的 (，．， )外，还有一个重要的因子f(，．， )一信息
素，f(，．， )在算法运行时被蚂蚁更新。对于对称性TSP，有r(r， )=f( ，，．)。
2．2 蚂蚁算法 (AS)求解单探针路径的数学模型
蚂 蚁 算 法 J是 模 拟 自然 界 蚂 蚁 寻 找 食 物 时 在 所 经 过 的路 径 上 留下 一 种 挥 发 性 的物 质 (称 为信 息
素 )，从而 引导后 续蚂 蚁走 最 短路 径提 出的一种 算 法 。
蚂 蚁算 法 (Ant System，AS)求解 单 探针 路径 的过程 【5 J如下 ：每 只 蚂蚁 采用 基 于概 率 的状 态 转移
规 则 来选 择下 一步 要 访 问 的焊区 ，直 至走 完 一条 完 整路 径 。 当所 有 的蚂 蚁 都走 完 了一 条 完整 路径 后 ，
算法将采用全局信息素更新规则来更新现有路径上的信息素。在这个过程中，有一小部分信息素挥发，
而 有蚂 蚁经 过 的路 径上 就 会有 新 的信 息素 增加 。在 下 一次 蚂蚁 选 择路 径 时 ，更 新后 的信 息 素将 会 影 响
蚂蚁选择该边的概率，使得全局较短路径上走过的蚂蚁增多 。不断地重复这两个过程，最终蚂蚁将寻
找 到一 条合适 的路 径 。
状 态转 移规 则 如式 (2)所 示 ，等 式给 出 了蚂 蚁 七在焊 区 ，．时选 择 焊 区 S的概 率 。
，
)= 如果 )
(2)
否则
其中，r是信息素，rl(r， )=llS(r， )， (，．，“)=l16(r，“)， )是蚂蚁七在焊区，．时待访问焊区集合， 是
决定信息素与距离两个因子重要程度 的参数 。通过 (2)式，可以使得距 离较短而信息素较高的路径被
选 择 的机 会增 大 ， 该状态 转移 规 则兼顾 了全局 路径 长度 和 当前 要选 择 的边 的长 度 。
在 蚂蚁 算法 中 ，全 局更 新规 则按 照 (3)式定义 ：
r(r， ) (1-a)·r(r， )+∑ ( )
其中， ， )：』 ， 如果(r， ) ， 是第七只蚂蚁走过的边的集合，
【0， 否则
完整路径 的长度 ，m是蚂蚁数，0<口<1，是信息素挥发因子。
(3)
是第 七只蚂 蚁 访 问过 的
2．3 蚁群算法 (ACS)求解单探针路径的数学模型
针 对MCM基板 互联 的复杂 程度 ，本 文在 求解 探 针路 径 时 ，借鉴 了Dorigo Marco【6J提 出的蚁群 (Ant
Colony System，ACS)算 法 。这 是一 种分 布 式算 法 ，利 用一 组相 互 协作 的主体 (即蚂 蚁 )并 行寻 优 ，
通 过信 息 素 实现 间接协 作 和 全局 通 讯 。ACS与AS的不 同之 处 主要 有三 ： 1)状 态 转 移规 则 为进 行 新
路 径搜 索和 依据 已有 的信 息搜 索之 间提供 了一 种 平衡 方法 ；2)全 局更 新 规 则仅用 于最优 路 径 的边 ；3)
当蚂 蚁 寻找 路径 时 使用 局部 更新 规 则 。
采 用ACS算法 求 解探 针路 径 的过 程如 下 ：首 先初 始 化 m只 蚂蚁 到 个焊 区上 ，’作 为路 径 的起 始 点 。
一
，
维普资讯 http://www.cqvip.com
第 1期 许川佩等：MCM 基板互连测试的单探针路径优化研究
接下来每只蚂蚁重复使用状态转移规则，寻找下一步要走过的焊 区，在 已经走过的子路径上，蚂蚁根
据局部信息素更新规则释放信息素。当全部蚂蚁都走完了全部焊区后 ，采用全局信息素更新规则来更
新 路 径上 的信 息素 。ACS算 法 所采 用 的状 态 转移 规 则 、全 局信 息 素更 新规 则 以及 局 部信 息 素更 新 规则
的定义 如 下 。
2_3．1 ACS状 态 转移 规 则
ACS状态 转移 规 则如 式 (4)所 示 ：
．
：
』max ．，七(，){ (r， )I·【，7(r， )】 j， 女口果鼋 鼋。 (4)
IS， 否则
在式 (4) 中， S是蚂 蚁 k在 焊 区 r处将选 择 的焊 区 ， 鼋是 【0，l】中均匀 分 布 的随机 数 ，而 是一 常
数 (0
伪随机概率规则，这种规则通常会让距离较短而且信 息素较大 的路径 以更大 的概率被选 中。参数口。决
定了是搜索新路径还是依据信息作选择，当 q q 时，蚂蚁将直接选择信 息素和距离 因素之积最好的
边 ，否则仍按照式 (2)来选择将要访问的焊区。这种做法在 降低了算法求 出要访 问的边所花费的运算
时间 的 同时 ，与AS相 比 ，也可 以避 免 因局 部优 化 而影 响全 局优 化 的结 果 。
2_3．2 ACS全局 信息 素更 新 规则
在ACS中，只有获得全局最优路径 的蚂蚁释放信 息素 ，再与状态转移规则结合 ，使得搜索更加直
接 ：蚁群在算法当前的迭代中是在最好路径的相邻范围内进行搜索 。全局信息素更新规则如式 (5)：
r(r， ) (1--a)·r(r， )+口·Av(r， ) (5)
其中， (，．， )：J 驴JI ，如果(r， )∈全局最好路径 ，0<口<1，是信息素挥发因子，它决定信息素挥 【
0， 否则
发的速度，￡ 是蚂蚁在一次完整的路径寻找过程中寻找到的最短路径 的距离 ，即全局最优路径的长度 。
在AS中 ，全 局更 新 规则倾 向于 给 较短 的路 径 与 更 多 的信 息 素 ，而 式 (5)只 允许 走 出最 好 路 径 的蚂蚁
留下信 息 素 ，这使 得蚂 蚁 能排 除其 它信 息 素 的干扰 而更 快地 找到距 离较 短 的路径 。
2_3．3 ACS局部更 新 规则
更 新规 则 如式 (6)所 示 ：
r(r， ) (1-p)·r(r， )+P·Av(r， ) (6)
其中0
息 素 。
经过大量的实验表 明，在对MCM基板焊区进行路径优化时，各种规则中参数的取值如下 ： =2，
q。=0．99，口=P=0．1，ro= · )～，其中，2是网络数，而厶 是采用最临近法则求得的最短完整路径
长度 。对 于 网络 数 小于 1000的探针 测试 路径 优 化 ，蚂 蚁数 m取 l0时 的结 果较 好 ，而 当网络 数 大于 1000
时 ，考 虑到算 法 的复 杂度 ， m取5比较 合适 。
r__
3 参数选取仿真 试验 ‘
● 二
在设定单探针的优化规则后，单探针测试路径优化包括下面三个步 I
骤 ：首 先从 CAD 软件 中取得 电路 网表 (netlist)，并 对 网表进 行 编译 。 一
接着计算 出每个焊区的坐标及相互间的距离。最后采用蚁群算法来寻找 一
并优 化单 探针 的测 试 路径 。
5 6
lO
17
1
I89
图 1 单探针测试的路径
针对 图 1所示电路 ，采用 ACS算法来进行寻找和优化基于单探针 的测试路径实验，在实验过程中，
程序 每 次运行 时都 连 续进 行 l0 次路 径 搜索 ，设定 a=0．1，调 整蚂 蚁 的数 量 m进 行 了若 干 次实 验 ，实
验 结果 如表 1所 示 。
维普资讯 http://www.cqvip.com
l38 电路与系统学报 第 l0卷
表 1 当 =0．1时的优 化结 果 mnl
l 248．86
2 203．79
5 2l6．55
lO l87I35
2O l84．22
244．28
232．23
l81．43
l84．22
l79．37
图 2中分 别 给 出 了当蚂 蚁数 量 为 1、5、10、20时 的路 径优 化 舍 10
过程的曲线，曲线的横轴是算法取得完整路径的次数，而纵轴是 轰260
所得到优化路径的长度。比较m=10和m=20时的结果发现，并 差：40
不是增多蚂蚁数就一定能提高优化结果。这表明，蚂蚁 留下的信 娄 200
息素可以传递距离信息，同时也存在一定的干扰性，使得算法难 ：8 0
以寻 找到 较好 的路 径 ，这 种干 扰 性 随着蚂 蚁 数 的增大 而 加剧 。另
外 ，不管蚂蚁的数量为多少，每条优化 曲线都出现 了一定的波动
性 ，这 种波 动性 随着蚂 蚁 数 的增 多而 降低 。 由于 干扰 性 和波 动性
从表 1看到，蚂蚁
数 与 优化 结 果有 着 明显
的 因果关 系 ， 当蚂 蚁 数
增 多 时 ，优化 结果 就 会
向着更 好 的趋 势发 展 ，
且 收敛 速度 加 快 ，这种
变化 过 程 如 图 2所 示 。
算法取得 完整路径的次数
图 2 蚂蚁数量 与优化 结果
的相互制约使得蚂蚁数量的选取有 了一定的限制，本文将蚂蚁数设定为 5到 10只，具体数量的设定根
据 MCM 基板互联 的复杂度来确定。在此次实验 中，蚁群算法求得 的最优路径如图 3虚线所示 ，矢量
-4
3
●一
【三
l
●-一
图 3
5 6 15 16T 2—0 表 示为 【5，6，10，11，12，9，13，8，14，18】，这也 是 该 问题 的最优 解 。
lO
蚂蚁算法优化 的测试路径
下 面讨 论优 化 结果 与 口的关 系 ，作 为信 息 素 的挥 发 系 数 ， 口是蚂 蚁
算法中最重要的参数之一，它将影响蚁群算法 的收敛 、波动性与干扰性 ，
直 至影 响最 后 的优 化结 果 。由于 口所 产 生 的影 响是 和其 他 参数 共 同作 用
产 生的 ，而且 随着 优化 目标 的不 同而 不 同 ，所 以很 难确 定 口的最 终取 值 。
下面进行一组实验来说明 口的取值与优化结果 的关系 。在本次实验中，
m=10固定不变，而通过改变 口来求得优化结果的 曲线 ，如图4所示。虽
然无法真正地确 定口对优化结果的影响函数，但从 图中仍能看 出各次测量 曲线受 口影响的变化趋势，
当 口增大 时 ，优 化 结 果就 出现 较大 的波 动 ，这 是 由于蚂 蚁在 寻 找路 径 时更注 重 局部 优化 而 产生 的，而
当 0．05<口<0．1时 ，优 化结 果 的波动 性 减 小 ，并 且收 敛趋 势 明显 。口所 引起 的波 动性 是 和其 他 参数 共 同
作用产生的，所 以本文将蚁群算法的波动性函数定义为： —?
= f ，m，n，Pn J (7) 呈23o卜 A～ 。 l
其中， 是波动性函数，m是蚂蚁数，而，l和 分别是网络数与焊 警 nL 一一，、 ^ {＼ ／ ／
譬 喜 善 竺 茬 呈 震 美 蓁1：7 0} 呈 出 的详细内容，但在对其性质了解的基础上，人们已经可以取得萎 = ，i
一 些经验值来设定 口，并且取得 了较好的效果。
4 基于蚁群 算法的单探针测试 路径优化仿 真 图4 口与优化结果的关系
采用 以 ACS算法为核心 的探针测试路径优化方法对 mcc1—75 MCM 基板互连 的探针测试路径进行
表 2 优化结果比较 优化 试验 ，mcc1—75是 MCNC组 织建 立 的 MCM 基 准 电路 ，该 电
算法 路共 有 806个 网络 ，1946个焊 区 。试 验所 用 的计 算机 硬件 配 置 为 ：
PⅣ 1．8G／512M D 。
采 用ACS算 法 生成 mcc1—75的单 探 针 测 试 路 径 后 ， 将 其 与
Pendurkar R[11等人采用线性方法进行试验的数据进行 比较，结果详
见表2。Pendurkar R等人 的算法是在SUN Ultra一2 SPARC工作站上进
行运算的。从运行结果可以看到采用蚁群算法得到的测试路径长度
6 7 3 2 2 O 8 4 2 2
7 3 ● 4 4 9 4 8 8 8
2 2
7 8 4 4 2
3 2 ● 5 2
8 5 2 O 4
2 8 O 9 8
2 l 2 l l
6 4 4 8 3 O 8 6 2 4
7 4 O 5 ● 9 ● ● 8 8 2 2 2 ● ●
9 5 3 8 7
6 3 4 2 3
4 7 ● 5 9 3 8 8 8 7
8 6 4 3 7
2 8 ● O 3
4 8 2 8 9 4 4 O 7 7 2 2 2 ● ●
2 3 4 8 7
l 5 l 2 3
7 7 2 5 9
5 3 O 8 7 2 2 2 ● ●
j
4 强
9 ● 2 8 7 6 2 2 2 3
4 5 4 5 9
3 6 8 8 7
2 2 _ _ _
维普资讯 http://www.cqvip.com
第 1期 许川佩等：MCM 基板互连测试的单探针路径优化研究 l39
要 远远 短 于其 它算法 所 得到 的，所得 到 的测 试距 离 比移 动法 的短30％， 比插入 法 的 短59％。
5 结论
本 文提 出 了基 于蚁 群 算 法 的MCM基 板测 试 单探 针 路 径优 化 模 型 。 当ACS算 法用 于MCM基 板 互联
测试 的探针路径优化时 ，蚂蚁之 间通过一种简单的传递信息的方式一信 息素来完成寻优工作，本文将
该算 法 与单探 针 测试 的规则 相 结合 ，针 对MCM基 板互 联 测试 的特 点，得 到 了一种 新 颖 的路 径优 化算 法 ，
并针 对MCM基 准 电路metl一75 等作 了仿 真实 验 。从得 到 的结 果看 ，探 针测 试 路径 长度 远 小于 其 它传 统
算法 得 到 的结果 。
参考文献 ：
【I】 Rajesh Pendurkar，et a1．Single—Probe Traversal Optimization for Testing of MCM Substrate Interconnections? ．IEEE Transactions on
Computer-Aided Design of Integrated Circuits and Systems，I 999，8(I 8)：I I 78一I I 9 I．
【2】 Kim Bruce C，et a1．Probe Scheduling Algorithm for MCM substrates【A】．IEEE International Test Conference(TC)【C】．1999．3 I一37．
【3】 Chou Nan—Chi，et a1．Dynamic Probe Scheduling Optimization for MCM Substrate Test【J】．IEEE Tr ans．Components，1 994，5(I 7)：I 82一I 89．
【4】 Goss S，Aron S，Deneubourg J L，et a1．Self_organized shortcuts in the argentine ant? ．Naturwissenschaften，I989，76：579—58I．
【5】 Dorigo M ，Maniezzo V，Colorni A．The ant system：Optimization by a colony of cooperating agents【J】．IEEE Trans．Syst，Man，Cybern．B，
I996，26：29—4I．
【6】 Dorigo M ，et a1．Ant Colony System：A Cooperative Learning Approach to the Traveling Salesman Problem ? ．IEEE Tr ansa ctions on
Evolutionary Computation，I 997，4(I)：53—66．
作 者简 介 ；许川■ (1968一)，女，副教授，博士生，主要研究方向为集成电路测试理论与技术；许君华 (1978一)，男，
硕士 ，主要研究方 向为计算机辅助测试 ；莫玮 (1956一)，男，教授 ，博士生导师，现为 中国电子技术标准化研 究所所
长 ，主要研究方 向为 自动测试总线与系统 、IP核测试 技术 、集成电路测试理论与技术；李智 (1965一)，男，教授 ，主
要研究方 向为 自动测试总线与系统 、集成 电路测试理 论与技术 。
Research on single-probe traversal optim ization
for testing of M CM substrate interc0nnecti0ns
XU Chuan．pei '-， XU Jun．hua ， M O W ei ， LI Zhi
( 1．School of Mechano—Electronic Engineering，Xidian University，Xi’an 710071，China；
2．Dept．of Electronic Engineering Guilin University of Electronic Technology，Guilin 541004，China)
Abstract：For the single—probe technology used for testing of MCM substrate interconnections，this paper presente a
single—probe Traversal Optim ization approach based on ant colony system algorithm ．By finding suitable rules to pilot the
probe to move。it can minimize the total distance traveled，so as to decrease the test time and to increase the M CM test
throughput finally．Experiments on benchmark M CM netlists with single probe traversal confirm that our traversal
optimization algorithm based on ACS has an increasing advantage over other algorithms in the total distance traveled．
Key words：MCM substrate；interconnection test；single—probe；ant colony system algorithm
维普资讯 http://www.cqvip.com
MCM基板互连测试的单探针路径优化研究.pdf
