一种测试FPGA单长线及连接开关的扩展布线方法

摘要

本发明公开了一种测试FPGA单长线及连接开关的扩展布线方法，步骤包括：设置轮回行并初始化参数，快速分组，线序预估，二次过滤，线序拼接，回退判定，拆除重布，结果扩展，结果验证。其优点是：依据层次式FPGA的结构特点，提出了一种基于布通率的高可靠、高适应性、高效率的布线算法；该算法能快速进行资源配置和有效配置资源图的生成，对单长线及连接开关的资源覆盖率较高，且与具体硬件结构无关；该算法的实施极大地增强了自动化布线和测试能力，有效减少后期布线工作量，节约测试成本，提高测试效率，缩短测试周期，降低开发风险，有一定的应用和参考价值。

主权项

一种测试FPGA单长线及连接开关的扩展布线方法，其特征是，步骤如下：步骤一、设置轮回行并初始化参数：确定轮回行的数目为2，并为后续布线搜索到的链路中间结果准备存储空间，准备完成后进入步骤二；步骤二、快速分组：依据分组算法依次将CLB和单长线进行分组，获取轮回行所有CLB分组和第一组CLB分组对应单长线起始组合点；分组完成后进入步骤三，如果失败则退出算法，返回失败代码；步骤三、线序预估：在选取完第一组CLB分组连接点后，通过获取轮回行所有关键布线CLB分组连接点的方法获取轮回行所有CLB分组的起始连接点，然后分别对这些连接点进行测试验证，测试该分组是否合适，是否可以选出最优线序；测试的方法是：依据宽度优先算法搜索并选取该CLB布线在最大链长下的所有可布通的线网，如能布通则表示该分组暂时可行，并分别记录CLB1、CLB2、CLB3、CLB4可布通的组合序号以便在后续回退时调整该组合序号选出相应线序组合；当预估完成后进入步骤四，否则，如果所有组合测试后均未发现可布通的线序组合则回退至步骤二重新分组；所述CLB1、CLB2、CLB3、CLB4分别指每个CLB分组的第一个CLB、第二个CLB、第三个CLB和第四个CLB；步骤四、二次过滤：经过步骤3预估过滤后，确定了所有关键布线CLB分组的起始连接点和所有可行的线序组合后，再做进一步进行过滤排除：从第一个CLB分组的CLB1和CLB2开始，依次选取相邻下个分组的CLB1和CLB2，在选取CLB1和CLB2的过程中过滤水平六长线的占用，并同时采用线序选优的策略选取最优线序组合，以降低CLB1和CLB2分别对CLB4和CLB3布线线网的影响；在选取CLB1、CLB2、CLB3和CLB4的过程中，考虑相互之间水平六长线和行间单长线的占用影响，当过滤完成后进入步骤五，否则失败回退至步骤二重新分组；步骤五、线序拼接：在完成所有关键布线CLB分组的布线后，需要对相邻关键布线CLB分组的布线进行拼接来完成整个线网的布线，在拼接过程中，依据单个CLB在线序预估阶段选出的可行线序索引进行，当拼接成功则进入步骤八，否则当某个CLB在重试完所有的可行线序索引后均未拼接成功，则进入步骤六进行回退判定；步骤六、回退判定：在线序拼接失败后，进行布线CLB回退位置的选择，首先选择拼接失败CLB的顶部CLB，调整顶部CLB选取的线序组合对底部CLB布线有影响的占用集合，同时测试底部CLB是否可以布通；如果可以则记录该线序索引值，进入步骤七进行拆除重布；如果调整完所有线序索引仍未布通，则回退至该拼接失败CLB的上一相邻关键布线CLB分组内具有相同组内索引的CLB，同样重试该CLB选出的可行线序索引进行，同时测试是否可以布通，如是，则记录该线序索引值，进入步骤七进行拆除重布，如果重试完所有的可行线序索引后仍未布通，则继续按照上述方法循环回退，直至回退位置为首行的首个分组为止；如果仍未成功则回退至步骤二重新分组；步骤七、拆除重布：对已布线网进行部分拆除，拆除部分为布线失败CLB位置至回退CLB位置，拆除这之间所有已布的线网，并在拆除过程中分析造成失败的冲突占用点和线序索引，为回退重布提供依据，拆除完成后根据回退CLB位置记录的可行线序索引值进行资源重建即重布，重建完成则回退至步骤五，从该回退CLB位置开始继续未完成的线序拼接；步骤八、结果扩展：完成拼接后的链路即为完整链路，即已完成了轮回行布线，覆盖了轮回行的所有CLB；此时轮回行以外的CLB部分，将搜索到的链路中间结果按照行奇偶对应的原则扩展至整个芯片，在扩展的过程中严格遵守XDL的描述规则；步骤九、结果验证：扩展完成后，即实现了整个FPGA的布线，将此时的中间结果直接导出为XDL格式文件，然后利用XDL命令，将导出文件转化为NCD网表进行结果验证。