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

第40 卷 第3 期 计 算 机 工 程 2014 年3 月 Computer Engineering March 2014 Vol.40 No.3 文献标识码文献标识码：：A TP301.6 文献标识码文献标识码：： 中图分类号中图分类号：： 文章编号文章编号：：1000--3428(2014)03--0287--07 中图分类号中图分类号：： ·开发研究与工程应用·开发研究与工程应用·· 文章编号文章编号：： -- -- -- ··开发研究与工程应用开发研究与工程应用·· 一种基于线网划分的并行一种基于线网划分的并行 布线算法布线算法 一种基于线网划分的并行一种基于线网划分的并行FPGA 布线算法布线算法 朱朱 春，春，来金梅来金梅 朱朱 春春，，来金梅来金梅 (复旦大学专用集成电路与系统国家重点实验室，上海 201203) 摘摘 要：要：针对在现场可编程门阵列(FPGA)软件系统中大规模电路设计布线时间较长的问题，提出一种基于线网引脚位置划分且具 摘摘 要要：： 有平台独立性的多线程 FPGA 布线算法。对高扇出线网采用将单根线网拆分成子线网并同时布线的方法，对低扇出线网采用选择 若干位置不相交叠的线网进行同时布线的方法，给出线网边界框图的数据结构来缩短选择若干低扇出线网的时间，采取负载平衡 机制和同步措施，分别提高布线效率和保证布线结果的确定性。实验结果证明，在Intel 4 核处理器平台上，与单线程VP 算法相 比，该并行算法的平均布线效率提高了90%，平均布线质量下降不超过2.3%，并能够得到确定的布线结果，在EDA 方面具有重 要的理论与实用价值。 关键词关键词：现场可编程门阵列： ；多线程；布线；高扇出线网；低扇出线网；边界框图；确定性 关键词关键词：：