3.6 微处理器测试

英伟达（NVIDIA）是一家计算机技术公司。近年，该公司在测试图形处理器时，也采用了Concorde代码，用来优化测试时使用的集成电路。在设计新型计算机芯片时，制造后的测试步骤在整个生产过程中至关重要，因此TSP的此类应用非常普遍。

为了方便集成电路测试，人们于20世纪80年代引入了扫描链（scan chain）的概念。计算机芯片的元件称为扫描点（scan point）。扫描链是一条连接扫描点的通路，其两端位于芯片边界，分别为输入端和输出端，如图3-11所示。从芯片扫描链的输入端开始，各个扫描点依次加载测试数据，经过一系列测试后，可以在输出端读取并评估数据。

图3-11　扫描链示意图

人们使用TSP来确定测试点的次序，使测试链尽可能短，从而有助于实现许多目的，比如节省宝贵的芯片布线空间，再比如通过加快信号传输速度来节约测试阶段的时间。

绝大多数情况下，芯片制造技术有限，电气连接只能选择水平布置或者垂直布置。这意味着在扫描链的TSP题目中，两点之间的路程不是直线距离，而是连接它们的水平或垂直路径的长度之和，就像走在曼哈顿横平竖直的街道上那样。图3-12给出了一道扫描链TSP的最佳路线。这道题目包含764座城市，原题由太阳微系统公司的Michael Jacobs和Andre Rohe提供，答案则由Concorde程序解出。为了缩短测试所需时间，新型计算机芯片一般都会有多条扫描链。以这道764座城市的TSP为例，它代表一条扫描链，而这条扫描链所在的芯片共有25条扫描链，它只是其中一条。

图3-12　有764座城市的扫描链TSP