1 中国科学院 电子学研究所, 北京 100190
2 中国科学院大学, 北京 100049
随着现场可编程门阵列(FPGA)器件尺寸不断增大, 计算机辅助设计(CAD)工具运行时间成为突出的问题。布线是FPGA的CAD流程中最为耗时的一个阶段, 一种能有效缩短布线时间的方法就是并行布线。本文提出一种减少FPGA时序驱动布线算法运行时间的多线程方法。该算法首先将信号按照线网的扇出数量进行排序, 再将排序后的线网均匀分配到各个线程中, 最后并发执行所有的线程。在布线质量没有受到显著影响的前提下, 即线长增加2.58%, 关键路径延时增加1.78%的情况下, 相对于传统通用布局布线工具(VPR)时序驱动布线算法8线程下的加速比为2.46。
现场可编程门阵列(FPGA) 计算机辅助设计(CAD) 并行布线 时序驱动布线 多线程 Field-Programmable Gate Array(FPGA) Computer-Aided Design(CAD) parallel routing timing-driven routing multithread 太赫兹科学与电子信息学报
2017, 15(6): 1066
1 光纤通信技术和网络国家重点实验室, 武汉430074
2 武汉烽火网络有限责任公司, 武汉430074
为解决在多核处理器平台下路由器报文转发时路由查找速度慢的“瓶颈”问题, 提出了一种基于分割的多分枝Trie树的并行路由查找算法。该算法将一棵多分枝Trie树根据处理器的核数分割成若干子树, 每棵子树又构成一棵单独的多分枝Trie树, 子树中取消了前缀查找, 采取组成一个大中间节点的方式, 在中间节点之间采用固定步长查询, 中间节点内部采用二进制Trie树来表示。实验结果表明, 该算法具有访存次数少、查询速度快、占用存储空间少和更新开销小等特点, 同时适用于IPv4和IPv6地址。
并行路由查找算法 Trie树 多核处理器 前缀匹配 parallel routing lookup algorithm trie multi-core processor prefix match
