FPGA的布线资源的布线方法和测试方法

摘要

本申请涉及集成电路测试，公开了一种FPGA的布线资源的布线方法和测试方法。该布线方法具体为按照选定的方向，分别从起始布线单元的各行或各列开始，依次地执行单位步长的布线过程，至布线到结束布线单元的各行或各列为止，并按照与该选定的方向相反的方向，分别从该起始布线单元的各行或各列开始，各执行一次该单位步长的布线过程；该测试方法在该布线方法的基础上对已布的被测线段进行测试。本申请实施方式中能够均衡利用现有的FPGA逻辑资源，在一个测试pat中尽可能多地测试布线线道，减少FPGA布线资源测试所需的测试pat数量，减少FPGA测试时间，减少测试pat开发的时间。

权利要求

1.一种FPGA的布线资源布线方法，其特征在于，包括：按照以下步骤分别对各行、各列进行分别布线：按照选定的方向，分别从起始布线单元的各行或各列开始，依次地执行单位步长的布线过程，至布线到结束布线单元的各行或各列为止，并按照与所述选定的方向相反的方向，分别从所述起始布线单元的各行或各列开始，各执行一次所述单位步长的布线过程；

其中，所述单位步长的布线过程包括子步骤：按照所述选定的方向从所述单位步长所跨的起始PLB到终止PLB进行被测线段的布线，并将该被测线段布入到所述终止PLB中LUT的输入端。

2.根据权利要求1所述的布线方法，其特征在于，所述按照所述选定的方向从所述单位步长所跨的起始PLB到终止PLB进行被测线段的布线，并将该被测线段布入到所述终止PLB中LUT的输入端之前，还包括：

选择被测线段的类型并根据所述被测线段的类型选定单位步长；

所述按照所述选定的方向从所述单位步长所跨的起始PLB到终止PLB进行被测线段的布线，并将该被测线段布入到所述终止PLB中LUT的输入端之后，还包括：以该终止PLB作为所述选定的方向上的下一个相邻的单位步长布线过程的起始PLB，其中，所述起始布线单元和所述结束布线单元均跨所述单位步长。

3.根据权利要求1或2所述的布线方法，其特征在于，所述被测线段的类型包括X1、X2……XL，L为自然数，其中，

X1表示跨过1个PLB步长的被测线段,其中所述X1的所述单位步长为1个PLB步长；

X2表示跨过2个PLB步长的被测线段，其中所述X2的所述单位步长为2个PLB步长；

…

XL表示跨过L个PLB步长的被测线段，其中所述XL的单位步长为L个PLB步长。

4.根据权利要求3所述的布线方法，其特征在于，所述布线方法进一步包括：选择被测线段的类型为X1时，所述选定的方向为东或南时，分别从第1行或列开始，依次重复地执行1个PLB步长的被测线段的布线过程，至布线到第N行或列结束，并分别从第1行或列，向西或北的方向，执行1个PLB步长的被测线段的布线过程；

选择被测线段的类型为X2时，所述选定的方向为东或南时，分别从第1行或列,和第2行或列开始，依次重复地执行2个PLB步长的被测线段的布线过程，至分别布线到N-1行或列,和N行或列结束，并分别从第1行或列，和第2行或列开始，向西或北的方向，执行2个PLB步长的被测线段的布线过程；

……

选择被测线段的类型为XL时，所述选定的方向为东或南时，分别从第1行或列,第2行或列，……，和第L行或列开始，依次重复地执行L个PLB步长的被测线段的布线过程，至分别布线到N-L+1行或列,……，N行或列结束，并分别从第1行或列,第2行或列，……，和第L行或列开始，向西或北的方向，执行L个PLB步长的被测线段的布线过程；

其中，所述第1行或列,所述第2行或列，……，和所述第L行或列位于同一列或行的不同被测线段上,L自然数且1≤L≤N，N是该FPGA的同一行或列的PLB的个数，N>0。

5.一种FPGA的布线资源测试方法，其特征在于，包括：步骤一：根据权利要求1-4任意一项所述的方法进行FPGA的布线资源布线；

步骤二：通过与各被测线段连接的IO模块给每个所述被测线段的起始PLB输入逻辑值，所述逻辑值经过所述被测线段后输入到所述被测线段的终止PLB中LUT的输入端并在所述LUT内进行逻辑运算，并将所有所述逻辑运算的结果输入到与各所述LUT所对应的各D触发器中，将所述各D触发器内所有运算结果移位输出；

步骤三：根据所述移位输出的运算结果判断所述对应的LUT连接的被测线段的连通性。

6.根据权利要求5所述的FPGA的布线资源测试方法，其特征在于，所述逻辑运算为异或运算；

所述步骤二进一步包括：通过IO模块给所述被测线段输入的逻辑值发生改变时，都会在各所述LUT内进行逻辑运算，其运算结果输入到各所述LUT所对应的各D触发器中，然后将所述各D触发器内所有运算结果移位输出。

7.根据权利要求5所述的FPGA的布线资源测试方法，其特征在于，所述步骤三进一步包括：如果所述移位输出的运算结果不等于对应的各所述LUT的各输入值异或的结果，则输入到各所述LUT的信号所经过的被测线段存在开路或短路，否则输入各所述LUT的信号所经过的被测线段连通性正常。

8.根据权利要求7所述的FPGA的布线资源测试方法，其特征在于，所述测试方法执行的过程中，最多能够同时进行K种类型的被测线段的布线过程，且所述K种类型的被测线段分别布入到所述LUT的不同输入端并在该LUT中分别进行逻辑运算，其中1≤K≤M，M为每个PLB中所有LUT输入端总数。

9.根据权利要求5-8任意一项所述的FPGA的布线资源测试方法，其特征在于，所述步骤二至步骤三，进一步包括：

复位所有用于测试的各LUT对应的D触发器；

遍历被测线段的所有输入组合，并至少一次执行以下各步骤，直至遍历完所有的输入组合：

将输入组合通过所述IO模块输入到所述被测线段后，进入各LUT中进行比较运算，将所述比较运算的结果输出到所述各LUT对应的D触发器中，将所述对应的D触发器中的所有运算结果移位输出；

根据所述移位输出的运算结果判断被测线段的连通性。

10.一种计算机可读存储介质，其特征在于，所述计算机可读存储介质中存储有计算机可执行指令，所述计算机可执行指令被处理器执行时实现如权利要求5至9中任意一项所述的FPGA的布线资源测试方法中的步骤。

说明书

FPGA的布线资源的布线方法和测试方法

技术领域

[0001] 本申请涉及集成电路测试领域，特别涉及一种FPGA的布线资源的布线技术和测试技术。

背景技术

[0002] 布线资源连通FPGA内部的所有单元，而连线的长度和工艺决定着信号在连线上的驱动能力和传输速度。FPGA芯片内部有着丰富的布线资源，在实际中设计者不需要直接选
择布线资源，布局布线器可自动地根据输入逻辑网表的拓扑结构和约束条件选择布线资源
来连通各个模块单元，布线资源是FPGA的重要组成部分，FPGA的布线资源的连通性直接影
响该FPGA的具体功能，那么FPGA的布线资源的测试显得尤为重要了。

[0003] 现有的FPGA布线资源测试方法的缺点是对FPGA的资源利用率不均衡，这样对布线资源测试所需要的测试pat数量比较多，FPGA布线资源测试时间也就比较长。

发明内容

[0004] 本申请的目的在于提供一种FPGA的布线资源的布线方法和测试方法，能够均衡利用现有的FPGA逻辑资源，在一个测试pat中尽可能多地测试布线线道，减少FPGA布线资源测
试所需的测试pat数量，减少FPGA测试时间，减少测试pat开发的时间。

[0005] 为了解决上述问题，本申请公开了一种FPGA的布线资源布线方法，包括：

[0006] 按照选定的方向，分别从起始布线单元的各行或各列开始，依次地执行单位步长的布线过程，至布线到结束布线单元的各行或各列为止，并按照与该选定的方向相反的方
向，分别从该起始布线单元的各行或各列开始，各执行一次该单位步长的布线过程。

[0007] 在一个优选例中，该单位步长的布线过程进一步包括：选择被测线段的类型并根据该被测线段的类型选定单位步长，按照该选定的方向从该单位步长所跨的起始PLB到终
止PLB进行被测线段的布线，并将该被测线段布入到该终止PLB中LUT的输入端，且以该终止
PLB作为该选定的方向上的下一个相邻的单位步长布线过程的起始PLB，其中，该起始布线
单元和该结束布线单元均跨该单位步长。

[0008] 在一个优选例中，该被测线段的类型包括X1、X2……XL，L为自然数，其中，

[0009] X1表示跨过1个PLB步长的被测线段,其中该X1的该单位步长为1个PLB步长；

[0010] X2表示跨过2个PLB步长的被测线段，其中该X2的该单位步长为2个PLB步长；

[0011] …

[0012] XL表示跨过L个PLB步长的被测线段，其中该XL的单位步长为L个PLB步长。

[0013] 在一个优选例中，该布线方法进一步包括：

[0014] 选择被测线段的类型为X1时，该选定的方向为东或南时，分别从第1行或列开始，依次重复地执行1个PLB步长的被测线段的布线过程，至布线到第N行或列结束，并分别从第
1行或列，向西或北的方向，执行1个PLB步长的被测线段的布线过程；

[0015] 选择被测线段的类型为X2时，该选定的方向为东或南时，分别从第1行或列,和第2行或列开始，依次重复地执行2个PLB步长的被测线段的布线过程，至分别布线到N-1行或
列,和N行或列结束，并分别从第1行或列，和第2行或列开始，向西或北的方向，执行2个PLB
步长的被测线段的布线过程；

[0016] ……

[0017] 选择被测线段的类型为XL时，该选定的方向为东或南时，分别从第1行或列,第2行或列，……，和第L行或列开始，依次重复地执行L个PLB步长的被测线段的布线过程，至分别
布线到N-L+1行或列，……，N行或列结束，并分别从第1行或列,第2行或列，……，和第L行或
列开始，向西或北的方向，执行L个PLB步长的被测线段的布线过程；

[0018] 其中，该第1行或列,该第2行或列，……，和该第L行或列位于同一列或行的不同被测线段上,L自然数且1≤L≤N，N是该FPGA的同一行或列的PLB的个数，N>0。

[0019] 本申请还公开了一种FPGA的布线资源测试方法，包括：

[0020] 步骤一：前文描述方法中的步骤；

[0021] 步骤二：通过连接各该被测线段的IO模块给每个该被测线段的起始PLB输入逻辑值，该逻辑值经过该被测线段后输入到该被测线段的终止PLB中LUT的输入端并在该LUT内
进行特定的逻辑运算，并将所有该逻辑运算的结果输入到与各该LUT所对应的各D触发器
中，该各D触发器将所有运算结果移位输出；

[0022] 步骤三：根据该移位输出的运算结果判断对应的各该LUT连接的被测线段的连通性。

[0023] 在一个优选例中，该特定的逻辑运算为异或运算。

[0024] 在一个优选例中，该步骤二进一步包括：通过IO模块给该被测线段输入的逻辑值发生改变时，都会在各该LUT内进行特定的逻辑运算，其运算结果输入到各该LUT所对应的
各D触发器中，然后该各D触发器将所有运算结果移位输出。

[0025] 在一个优选例中，该步骤三进一步包括：如果该移位输出的运算结果不等于对应的各该LUT的各输入值异或的结果，则输入各该LUT的信号所经过的被测线段存在开路或短
路，否则输入各该LUT的信号所经过的被测线段连通性正常。

[0026] 在一个优选例中，该测试方法执行的过程中，最多能够同时进行K种类型的被测线段的布线过程，且该K种类型的被测线段分别布入到该LUT的不同输入端并在该LUT中分别
进行逻辑运算，其中1≤K≤M，M为每个PLB中所有LUT输入端总数。

[0027] 在一个优选例中，该步骤二至步骤三，进一步包括：

[0028] 复位所有用于测试的各LUT对应的D触发器；

[0029] 遍历被测线段的所有输入组合，并至少一次执行以下各步骤，直至遍历完所有的输入组合：

[0030] 将输入组合通过该IO模块输入到该被测线段后，进入各LUT中进行比较运算，将该比较运算的结果输出到该各LUT对应的D触发器中，将该对应的D触发器中的所有运算结果
移位输出；

[0031] 根据该移位输出的运算结果判断被测线段的连通性。

[0032] 本申请公开了一种计算机可读存储介质，该计算机可读存储介质中存储有计算机可执行指令，该计算机可执行指令被处理器执行时实现如前文描述的方法中的步骤。

[0033] 本申请实施方式中，至少包括以下优点：

[0034] 在执行一个方向(如E)布线过程中，使起始布线单元的LUT被充分利用，将结束布线单元的转向线放到下一个与该方向相反的方向的布线过程中，而起始单元执行一步相反
方向(如W)的布线，达到的有益效果：

[0035] 通过合理排布，优化设置转弯线，使每个布线单元的LUT利用率可以均衡一致；

[0036] 而且，在布线资源可布通的情况下，同一个方向上的布线结果可以比现有的布线方案最多可多布一倍的线道；

[0037] 进一步地，减少了被测线段测试所需的测试pat的数量，缩短FPGA测试时间和测试pat的开发时间。

[0038] 本申请的说明书中记载了大量的技术特征，分布在各个技术方案中，如果要罗列出本申请所有可能的技术特征的组合(即技术方案)的话，会使得说明书过于冗长。为了避
免这个问题，本申请上述发明内容中公开的各个技术特征、在下文各个实施方式和例子中
公开的各技术特征、以及附图中公开的各个技术特征，都可以自由地互相组合，从而构成各
种新的技术方案(这些技术方案均因视为在本说明书中已经记载)，除非这种技术特征的组
合在技术上是不可行的。例如，在一个例子中公开了特征A+B+C，在另一个例子中公开了特
征A+B+D+E，而特征C和D是起到相同作用的等同技术手段，技术上只要择一使用即可，不可
能同时采用，特征E技术上可以与特征C相组合，则，A+B+C+D的方案因技术不可行而应当不
被视为已经记载，而A+B+C+E的方案应当视为已经被记载。

附图说明

[0039] 图1是根据本申请第一实施方式的FPGA的布线资源的布线方法流程示意图

[0040] 图2是根据本申请第二实施方式的FPGA的布线资源的测试方法流程示意图

[0041] 图3是一种FPGA布线资源中类型为X2的被测线段的布线方法示意图

[0042] 图4是根据本申请第一实施方式的FPGA布线资源中类型为X2的被测线段的布线方法示意图

[0043] 图5是根据本申请FPGA基于PLB的总体布局示意图

[0044] 图6是根据本申请FPGA各PLB之间的互连结构示意图

[0045] 图7是根据本申请FPGA中PLB的结构示意图

[0046] 图8是根据本申请PLB中SLICE的结构示意图

[0047] 图9是根据本申请第一实施方法的布线单元的规划示意图

[0048] 图10根据第二实施方式中的步骤二至步骤三的一个具体实施例流程图

具体实施方式

[0049] 在以下的叙述中，为了使读者更好地理解本申请而提出了许多技术细节。但是，本领域的普通技术人员可以理解，即使没有这些技术细节和基于以下各实施方式的种种变化
和修改，也可以实现本申请所要求保护的技术方案。

[0050] 部分概念的说明：

[0051] 1.FPGA：Field Programmable Gate Array，现场可编程逻辑阵列。它是作为专用集成电路领域中的一种半定制电路而出现的，既解决了全定制电路的不足，又克服了原有
可编程逻辑器件门电路数有限的缺点。

[0052] 2.PLB：Programmable Logic Block，可编程逻辑模块。是FPGA的基本单元，如图7所示，它包括一个布线开关阵列RSB和一个逻辑单元PFB。

[0053] 3.RSB：Routing Switch Box。是FPGA的布线开关阵列，在这里许多布线互连从这里发出，也从这里结束，通过这个逻辑块连接到下一个PLB或PIB和自己PLB内部互连。

[0054] 4.PFB：Programmable Function Block，可编程功能块。

[0055] 5.SLICE:FPGA中，逻辑片一个SLICE中包括两个LUT和两个对应的D触发器。

[0056] 6.LUT：Lookup Table，查找表。在计算机科学中，查找表是用简单的查询操作替换运行时计算的数组或者关联数组这样的数据结构。

[0057] 7.Register,寄存器。是中央处理器内的其中组成部分，寄存器是有限存贮容量的高速存贮部件，它们可用来暂存指令、数据和地址。

[0058] 8.BRAM：Block Random Access Memory，块随机存取存储器。主要应用于构造数据高速缓冲存储器、深的FIFO和缓冲器等。

[0059] 9.IO模块，Input and Output block，输入输出模块。FPGA中各IO模块与各PLB连接。

[0060] 10.测试PAT：用于测试FPGA资源的特殊逻辑设计，例如被测线段是一种布线线段：被测线段为测试主体，FPGA内现有的LUT和D触发器及别的连接单元构成该被测线段的信号
输入主体和计算主体，最终该被测线段、作为运算器的LUT、作为移位寄存器的D触发器，三
者就组成了一种特殊的测试线路，就称为FPGA的一个测试pat。该测试pat为测试FPGA中LUT
而专门设计的测试线路，被称为测试LUT的PAT。一般来讲，一个测试pat只能测试FPGA的一
种资源的一部分。FPGA是由多种资源组成的，所以FPGA的测试PAT有很多。

[0061] 11.布线单元：所选用被测线段所跨PLB的单元数，该跨度根据所选择的被测线段的类型确定。例如如果所选择的被测线段的类型为X2，则这个布线类型的所跨2个PLB。

[0062] 12.起始布线单元和结束布线单元：即互连布线的起始位置和互连布线的结束位置：同一方向的布线过程由互连布线的起始位置开始到结束位置结束。如图3所示，如果被
测线段的类型为X2且向东布线时，第一组第一段被测线段从位置(0，0)开始，到位置(2，0)
结束。然后从位置(2，0)开始，到位置(4，0)结束。以此类推直到结束。第二组第一段被测线
段从位置(1，0)开始，到位置(3,0)结束。然后从位置(3，0)开始，到位置(5，0)结束。

[0063] 为使本申请的目的、技术方案和优点更加清楚，下面将结合附图对本申请的实施方式作进一步地详细描述。

[0064] 本申请的第一实施方式涉及一种FPGA的布线资源的布线方法，其流程如图1所示，该布线方法包括以下步骤：

[0065] 开始，执行步骤101：按照选定的方向，分别从起始布线单元的各行或各列开始，依次地执行单位步长的布线过程，至布线到结束布线单元的各行或各列为止；

[0066] 之后，执行步骤102：按照与该选定的方向相反的方向，分别从该起始布线单元的各行或各列开始，各执行一次该单位步长的布线过程。

[0067] 可选地，该单位步长的布线过程进一步包括：选择被测线段的类型并根据该被测线段的类型选定单位步长，按照该选定的方向从该单位步长所跨的起始PLB到终止PLB进行
被测线段的布线，并将该被测线段布入到该终止PLB中LUT的输入端，且以该终止PLB作为该
选定的方向上的下一个相邻的单位步长布线过程的起始PLB，其中，该起始布线单元和该结
束布线单元均跨该单位步长。

[0068] 可选地，该被测线段的类型包括X1、X2……XL，L为自然数，其中，

[0069] X1表示跨过1个PLB步长的被测线段,其中该X1的该单位步长为1个PLB步长；

[0070] X2表示跨过2个PLB步长的被测线段，其中该X2的该单位步长为2个PLB步长；

[0071] …

[0072] XL表示跨过L个PLB步长的被测线段，其中该XL的单位步长为L个PLB步长。

[0073] 可选地，根据所选择的被测线段的类型，该布线方法进一步包括：

[0074] 1)选择被测线段的类型为X1时，该选定的方向为东或南时，分别从第1行或列开始，依次重复地执行1个PLB步长的被测线段的布线过程，至布线到第N行或列结束，并分别
从第1行或列，向西或北的方向，执行1个PLB步长的被测线段的布线过程；

[0075] 2)选择被测线段的类型为X2时，该选定的方向为东或南时，分别从第1行或列,和第2行或列开始，依次重复地执行2个PLB步长的被测线段的布线过程，至分别布线到N-1行
或列,和N行或列结束，并分别从第1行或列，和第2行或列开始，向西或北的方向，执行2个
PLB步长的被测线段的布线过程；

[0076] ……

[0077] L)选择被测线段的类型为XL时，该选定的方向为东或南时，分别从第1行或列,第2行或列，……，和第L行或列开始，依次重复地执行L个PLB步长的被测线段的布线过程，至分
别布线到N-L+1行或列,……，N行或列结束，并分别从第1行或列,第2行或列，……，和第L行
或列开始，向西或北的方向，执行L个PLB步长的被测线段的布线过程；其中，该第1行或列,
该第2行或列，……，和该第L行或列位于同一列或行的不同被测线段上,L自然数且1≤L≤
N，N是该FPGA的同一行或列的PLB的个数，N>0。

[0078] 该布线方法执行的过程中，能够同时进行一种或多种类型的被测线段的布线过程；优选地，该测试方法执行的过程中同时进行一种类型的被测线段的布线过程；可选地，
该测试方法执行的过程中同时进行多种类型的被测线段的布线过程，具体的，同时进行K种
类型的被测线段的布线过程，且该K种类型的被测线段分别布入到该LUT的不同输入端并在
该LUT中分别进行逻辑运算，其中1≤K≤M，M为每个PLB中所有LUT输入端总数。

[0079] 需要说明的是：对于同一FPGA，如果完成所有布线资源的被测线段的布线，需要多次执行本实施方式的布线方法的布线过程(包括对每种被测线段的类型都进行布线和分别
选定四个方向进行布线等)，其中一般情况下，执行一次该布线方法只在同一个方向上进
行。

[0080] 需要说明的是：步骤101和步骤102的执行过程无先后顺序，可以先执行步骤101后执行步骤102，可以先执行步骤102后执行步骤101，或者可以同时执行步骤101和步骤102。

[0081] 本申请的第二实施方式涉及一种FPGA的布线资源的测试方法，其流程如图2所示，该测试方法包括以下步骤：

[0082] 开始，执行步骤201：本申请第一实施方式涉及的一种FPGA的布线资源的布线方法的步骤。

[0083] 需要说明的是，第一实施方式是本实施方式的步骤201相同的方法实施方式，第一实施方式中的技术细节可以应用于本实施方式的步骤201。

[0084] 之后，执行步骤202：通过连接各该被测线段的IO模块给每个该被测线段的起始PLB端输入逻辑值，该逻辑值经过该被测线段后输入到该被测线段的终止PLB中LUT的输入
端并在该LUT内进行特定的逻辑运算，并将所有该逻辑运算的结果输入到与各LUT所对应的
各D触发器中，该各D触发器将所有运算结果移位输出。

[0085] 该特定的逻辑运算可以通过设置改变的，可选地，该逻辑运算可以是异或运算；可选地，该逻辑运算可以是比较运算；等等。

[0086] 可选地，步骤202进一步包括：通过IO模块给该被测线段输入的逻辑值发生改变时，都会在各该LUT内进行特定的逻辑运算，其运算结果输入到各该LUT所对应的各D触发器
中，然后该各D触发器将所有运算结果移位输出。

[0087] 最后，执行步骤203：根据步骤202中移位输出的运算结果判断该对应的LUT连接的被测线段的连通性。

[0088] 可选地，步骤203进一步包括：如果该移位输出的运算结果不等于该对应的LUT的各输入值异或的结果，则输入各该LUT的信号所经过的被测线段存在开路或短路，否则输入
各该LUT的信号所经过的被测线段连通性正常。

[0089] 本申请第二实施方式的测试方法执行的过程中，能够同时进行一种或多种类型的被测线段的布线过程；优选地，该测试方法执行的过程中同时进行一种类型的被测线段的
布线过程；可选地，该测试方法执行的过程中同时进行多种类型的被测线段的布线过程，具
体的，同时进行K种类型的被测线段的布线过程，且该K种类型的被测线段分别布入到该LUT
的不同输入端并在该LUT中分别进行逻辑运算，其中1≤K≤M，M为每个PLB中所有LUT输入端
总数。

[0090] 可选地，本实施方式中的步骤二至步骤三，进一步可以包括以下步骤：

[0091] 开始执行A，复位所有用于测试的各LUT对应的D触发器；

[0092] 之后执行B,遍历被测线段的所有输入组合，并至少一次执行B1到B2，直至遍历完所有的输入组合：

[0093] B1将输入组合通过所述IO模块输入到所述被测线段后，进入各LUT中进行比较运算，将所述比较运算的结果输出到所述各LUT对应的D触发器中，将所述对应的D触发器中的
所有运算结果移位输出；

[0094] B2根据所述移位输出的运算结果判断被测线段的连通性。

[0095] 图10根据第二实施方式中的步骤二至步骤三的一个具体实施例流程图。

[0096] 需要说明的是，本实施方式涉及的测试方法可以是通过步骤一执行完所有类型的被测线段的布线过程之后，执行步骤二和步骤三的测试过程，直至测试完所有类型的被测
线段；也可以是选择性的完成一种类型或多种的被测线段的布线过程之后，执行步骤二和
步骤三的测试过程，然后再执行未进行布线的其他类型的被测线段的布线过程，然后再执
行步骤二和步骤三的测试过程，直至完成所有类型的被测线段的布线和测试过程。

[0097] 为了能够更好地理解本申请的技术方案，下面结合一个具体的例子来进行说明，该例子中罗列的细节主要是为了便于理解，不作为对本申请保护范围的限制。

[0098] FPGA布线资源的测试是利用FPGA内部LUT资源做逻辑比较判断的。一般来讲一个FPGA单元只有8个逻辑单元，有可能会更少。本例是行20×列22的FPGA布局(在行列布局形
成的格都看作一个PLB(基本单元))，以被测线段为X2线E2方向为例：

[0099] 图3为一种FPGA布线资源中类型为X2的被测线段的布线方法。从图上可以看出，该布线方法的缺点是：第0，1列是起始布线单元，该两列没有进行逻辑比较，该两列的LUT的利
用率比较低；第21，22列(最后两列)是结束布线单元，该两列需要两倍的逻辑单元比较直向
和转向的各被测线段，该两列的LUT的利用率比较高，两倍于其他(除第0，1列和第21，22列)
的LUT单元，导致LUT利用率不均衡。

[0100] 图4为根据本申请第一实施方式的FPGA布线资源中类型为X2的被测线段的布线方法。从图上可以看出，该方法的关键在于在测试同一个方向(E)的被测线段时，也在起始布
线单元的两列分别向反方向(W)进行一次被测线段的测试；与图3所述的一般方法相比，该
方法的优点是：在根据图4的布线方法的测试过程中，起始布线单元的各列(第0，1列)中LUT
也能被充分利用，从而使每个布线单元的各列(PLB)中LUT利用率达到均衡一致，且用这种
方法在布线资源可布通的情况下，一次可以比图3的方法多布一倍的线道；需要补充说明的
是：在根据图4的布线方法的测试过程中，虽然结束布线单元的各列(第21，22列)中LUT没有
被利用，但可以在下次的反方向(西)的测试中作为起始布线单元时被测试。

[0101] 需要说明的是，本申请涉及的连接包括直接连接和耦合连接。

[0102] 下面是对本申请各实施方式中涉及的部分相关技术的补充说明：

[0103] 图5是根据本申请一个FPGA基于PLB的总体布局示意图。如图5所示，中间部分(如(0,0))是FPGA的一个可编程逻辑单元(PLB)，可理解成一个数组的基本单元。外围是可编程
IO模块，就是说所有的逻辑信号只有通过IO模块才能送入FPGA的PLB的被测线段，也只有IO
模块才能把FPGA的逻辑信号送出来。

[0104] 图6是根据本申请一个FPGA各PLB之间的通过被测线段互连的结构示意图。在每个PLB里有一个可编程的RSB(Routing Switch Box)，FPGA的PLB之间的连接就是由RSB实现
的。PLB间信号通过水平通道和垂直通道传输，PLB可以直接驱动水平或垂直通道，通道之间
通过通道RSB(routing switch Box)进行切换，通道上传输的信号通过局部RSB进入PFB。

[0105] RSB中包含各种类型的被测线段，以类型X0，X1，X2，X4，X6为例，其中：X0表示PLB到自己本单元的被测线段类型；X1表示跨一个PLB步长的被测线段类型；X2表示跨两个PLB步
长的被测线段类型；X4表示跨四个PLB步长的被测线段类型；X6表示跨六个PLB步长的被测
线段类型。

[0106] FPGA布线资源的布线方向：通常FPGA的被测线段的布线方向包括东西南北四个方向，常用E，W，S，N表示。其中，南北方向的被测线段的互连为垂直通道，东西方向的被测线段
的互连为水平通道。

[0107] 本申请涉及的东、西、南、北的方向是将FPGA布局成图5所示的单元结构后的图上方向。

[0108] 图7是根据本申请一个FPGA中PLB(可编程逻辑块)的结构示意图。如图7所示，在PLB中有RSB(Routing&Switch Box)负责PLB之间的逻辑信号连接，PLB包括PFB(可编程功能
块)，PFB包括四个SLICE；SLICE中包括两个LUT(逻辑查找表)和与之一一对应的两个可编程
D触发器/锁存器。

[0109] 图8是根据本申请PFB中SLICE的结构示意图。如图8所示，每个LUT包含四个输入端，每个LUT的输出端通过组合逻辑输出与之一一对应的D触发器的输入端D。D触发器的Q端
通过RSB可以和别的PLB相连。

[0110] FPGA布线资源的被测线段的起始端(在起始PLB)和终止端(在终止PLB)常用BEG和END表示；例如，一个行为八，列为六的FPGA，以X2类型的被测线段为例，如图9所示，E2BEG0：
代表以起始PLB(x，y)为起点，向东跨两个PLB，到终止PLB(x,y+2)结束；也就是说：(x,y)的
E2BEG0和(x,y+2)的E2END0是连在一起的就是类型为X2的一条被测线段。此X2类型的被测
线段的线道为E2BEG0……E2BEG6,也就是说向东的X2线有0～6个线道。

[0111] FPGA是可编程器件，它由标准的单元阵列(包括逻辑查找单元、寄存器、布线资源)组成。

[0112] FPGA布线资源中，FPGA的每个PLB(如图9的(x,y)基本单元)都有相同的被测线段资源，都要在出厂前进行验证。例如，如果FPGA有X0，X1，X2，X4，X6六种跨度的被测线段。每
种被测线段有E(东)，W(西)，N(南)，S(北)四种方向。每种被测线段有7个线道。则每个基本
单元有：6*4*7＝168根被测线段。整个FPGA有6*8*168＝8064根被测线段要检测其的连通性
能。

[0113] 同上，布线资源的被测线段的种类可以分为X1(只能跨一个基本单元)，X2(只能跨两个基本单元)，X6(只能跨六个基本单元),X0(只能在本基本单元连线)……等等，以X1，
X2，X6，X0等类型的被测线段为例，又分为东西南北四个方向，命名规则如下：

[0114] E{G}BEG{H}，E{G}END{H}表示向东的X{G}被测线段G＝0，1，2，6；

[0115] BEG表示起始，H＝4，8…；

[0116] END表示结束，H＝4，8…；

[0117] W{G}BEG{H}，W{G}END{H}表示向西的X{G}被测线段G＝0，1，2，6；

[0118] BEG表示起始，H＝4，8…；

[0119] END表示结束，H＝4，8…；

[0120] S{G}BEG{H}，S{G}END{H}，N{G}BEG{H}，N{G}END{H}。

[0121] 转弯线：如果是向东E的被测线段转弯就变成向西W被测线段，向西W的被测线段转弯变成了向东E被测线段，向南S的被测线段转弯就变成向北N被测线段，向北N的被测线段
转弯变成了向南S被测线段,转弯时步长计算转弯自己算一步。

[0122] FPGA的布线资源检测，就是要检查在每个单元的这些被测线段的进出连接是正常的，通常是在每个被测线段的终止PLB进入逻辑单元进行比较检查。一个逻辑单元有6～8个
逻辑运算表，每个运算表可以有4个输入，也就是说每个运算表最多可以检查4根被测线段。
在FPGA中布线资源的测试走线方案决定FPGA测试的覆盖率，测试图形数目及测试时间。

[0123] 现有的FPGA的布线资源的测试方法具体包括以下步骤：

[0124] 开始执行第一步：把每个PLB中被测线段按照一定的互连规则布进PFB的LUT中；

[0125] 之后执行第二步：从IO模块将逻辑信号输入被测线段。保证每个被测线段的逻辑信号和输入信号一致；

[0126] 之后执行第三步：用LUT作为比较器，将由被测线段为输入的LUT的输入信号进行逻辑异或，则相同为0，不同为1；被测线段的信号与输入一致，如果LUT为1，表明有个别被测
线段短和输入不一致，有可能开路或短路；如果LUT为0，说明这个LUT的四个输入端连接的
被测线段连通性正常；

[0127] 之后执行第四步：将LUT的比较结果送入D触发器的输入端；

[0128] 最后执行第五步：将所有存放LUT比较结果的D触发器连成移位寄存器。这样就可以从有限的IO模块上输出每个被测线段的比较结果。

[0129] 本申请第二实施方式的测试方式是根据第一实施方式的布线结果后对该现有测试的优化。

[0130] 本申请实施方式还提供一种计算机可读存储介质，其中存储有计算机可执行指令，该计算机可执行指令被处理器执行时实现本申请的各方法实施方式。计算机可读存储
介质包括永久性和非永久性、可移动和非可移动媒体可以由任何方法或技术来实现信息存
储。信息可以是计算机可读指令、数据结构、程序的模块或其他数据。计算机的存储介质的
例子包括但不限于，相变内存(PRAM)、静态随机存取存储器(SRAM)、动态随机存取存储器
(DRAM)、其他类型的随机存取存储器(RAM)、只读存储器(ROM)、电可擦除可编程只读存储器
(EEPROM)、快闪记忆体或其他内存技术、只读光盘只读存储器(CD-ROM)、数字多功能光盘
(DVD)或其他光学存储、磁盒式磁带，磁带磁磁盘存储或其他磁性存储设备或任何其他非传
输介质，可用于存储可以被计算设备访问的信息。按照本文中的界定，计算机可读存储介质
不包括暂存电脑可读媒体(transitory media)，如调制的数据信号和载波。

[0131] 需要说明的是，在本专利的申请文件中，诸如第一和第二等之类的关系术语仅仅用来将一个实体或者操作与另一个实体或操作区分开来，而不一定要求或者暗示这些实体
或操作之间存在任何这种实际的关系或者顺序。而且，术语“包括”、“包含”或者其任何其他
变体意在涵盖非排他性的包含，从而使得包括一系列要素的过程、方法、物品或者设备不仅
包括那些要素，而且还包括没有明确列出的其他要素，或者是还包括为这种过程、方法、物
品或者设备所固有的要素。在没有更多限制的情况下，由语句“包括一个”限定的要素，并不
排除在包括所述要素的过程、方法、物品或者设备中还存在另外的相同要素。本专利的申请
文件中，如果提到根据某要素执行某行为，则是指至少根据该要素执行该行为的意思，其中
包括了两种情况：仅根据该要素执行该行为、和根据该要素和其它要素执行该行为。多个、
多次、多种等表达包括2个、2次、2种以及2个以上、2次以上、2种以上。

[0132] 在本申请提及的所有文献都被认为是整体性地包括在本申请的公开内容中，以便在必要时可以作为修改的依据。此外应理解，以上所述仅为本说明书的较佳实施例而已，并
非用于限定本说明书的保护范围。凡在本说明书一个或多个实施例的精神和原则之内，所
作的任何修改、等同替换、改进等，均应包含在本说明书一个或多个实施例的保护范围之
内。