孙 磊，朱 春，梁传增，王 健，来金梅

(复旦大学专用集成电路与系统国家重点实验室，上海 201203)

1 概述

现场可编程门阵列(Field Programmable Gate Array,FPGA)是一种可以快速、反复配置功能的芯片，已被越来越广泛地应用到各个领域。FPGA的互连资源包括互连线段与可编程互连开关(Programmable Interconnect Points, PIPs)，这些互连资源对 FPGA的功能有重要作用，因此，对它们的测试非常重要。FPGA互连测试的通用评价标准是覆盖率以及相应的配置文件数[1]。

目前，工业界对于FPGA互连测试采取半手工的方法实现，为了把配置文件数压缩到最小而精心设计每一个测试配置文件，然而这种方法需要较多的人工参与，自动化程度低[1]。文献[2-4]提出的方法与工业界采取的方法相比，具有更高的自动化程度，但主要是针对简单的互连结构，如Xilinx4000、Virtex等；这些方法都建立在人为把PIPs分为水平、垂直、左斜向、右斜向4种方向的基础上。然而，新型的 FPGA互连结构中存在这4种方向之外的特殊PIPs，如Xilinx Virtex-II、Virtex-4、Virtex-5等，以往提出的测试方法不能覆盖这些特殊PIPs。

本文提出一种改进型深度优先搜索算法，将所有的PIPs完全等价对待，无须对PIPs进行人为的方向区分。

2 背景知识

2.1 互连结构模型

开关盒(Switch Matrix, SM)是FPGA中的重要单元，由PIPs构成；FPGA中水平与垂直通道的互连线段通过开关盒相互连接。图1给出了文献[2-4]讨论的开关盒模型，图中粗线代表PIPs，细线代表互连线段，互连线段按照出现在开关盒四周的方位命名，如 W1是出现在开关盒西面的一根互连线段。PIPs可以按照两端互连线出现在开关盒的方位分为水平、垂直、左斜向、右斜向4种。……