互联结构模型化方法和互联资源配置向量自动生成方法

摘要

互联结构模型化方法和互联资源配置向量自动生成方法，属于FPGA技术。本发明的互联结构模型化方法包括下述步骤：首先对芯片中的金属线进行分类，同一类的金属线统称为一个layer，两条金属线之间只有通过开关盒中的可编程配置点PIP才能建立连接，同类金属线之间的PIP称为intra-PIP，而不同类金属线之间的PIP称为inter-PIP；然后以所有的layer为点，PIP的连接关系为边，建立图形。本发明能够自动生成测试配置，测试效率高。本发明对互联资源测试覆盖率高，尤其对PIP的覆盖。本发明不针对具体某一种型号的FPGA，能够用于SRAM型的FPGA测试，通用性好，方便移植。本发明能够做到更精确的故障定位和诊断。

主权项

互联资源配置向量自动生成方法，其特征在于，包括下述步骤：1)根据具体FPGA芯片的开关盒结构，建立该FPGA的互联资源模型：首先对芯片中的金属线进行分类，同一类的金属线统称为一个layer，两条金属线之间只有通过开关盒中的可编程配置点PIP才能建立连接，同类金属线之间的PIP称为intra‑PIP，而不同类金属线之间的PIP称为inter‑PIP；每一个layer为点，所有的layer构成了点集V，PIP的连接关系为边，建立IR模型；2)将上述的IR模型转换为邻接矩阵A，矩阵A中的每一个元素都对应了IR模型中环或有向边；3)根据矩阵A寻找一组最优的可布通路径，每一条可布通路径都对应了一组相同类型的测试配置；4)将步骤3)中的得到的每一条路径转化为有向图Gp，路径中的每一个layer的每根线表示为Gp中的点，路径中包含的每一个PIP表示为Gp中的边；5)从有向图Gp中得到节点不相交路径，采用基于局部最优解的边着色算法对Gp进行边着色，获得最优或者近似最优的解；同一颜色的边组成一组NDP，一组NDP即对应了一次测试配置，NDP的数目等于测试配置次数；6)重复步骤4)和步骤5)，直到计算出所有路径对应的NDP，得到该FPGA芯片的测试配置集合。