一种基于线网划分的并行FPGA布线算法

摘要：

针对在现场可编程门阵列(FPGA)软件系统中大规模电路设计布线时间较长的问题，提出一种基于线网引脚位置划分且具有平台独立性的多线程 FPGA 布线算法。对高扇出线网采用将单根线网拆分成子线网并同时布线的方法，对低扇出线网采用选择若干位置不相交叠的线网进行同时布线的方法，给出线网边界框图的数据结构来缩短选择若干低扇出线网的时间，采取负载平衡机制和同步措施，分别提高布线效率和保证布线结果的确定性。实验结果证明，在Intel 4核处理器平台上，与单线程VPR算法相比，该并行算法的平均布线效率提高了90%，平均布线质量下降不超过2.3%，并能够得到确定的布线结果，在EDA方面具有重要的理论与实用价值。

关键词：现场可编程门阵列、多线程、布线、高扇出线网、低扇出线网、边界框图、确定性

分类号：TP301.6(计算技术、计算机技术)

资助基金：国家“863”计划基金资助项目2012AA012001。

在线出版日期：2014-04-15（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：287-293