计算机工程

• 体系结构与软件技术 • 上一篇    下一篇

FPGA并行时序驱动布局算法

张家齐,沈剑良,朱珂   

  1. (国家数字交换系统工程技术研究中心,郑州 450002)
  • 收稿日期:2015-11-23 出版日期:2017-02-15 发布日期:2017-02-15
  • 作者简介:张家齐(1993—),男,硕士,主研方向为数字集成电路设计与分析;沈剑良,助理研究员、博士;朱珂,副教授、博士。
  • 基金项目:
    国家“863”计划重大项目(2014AA01A704);国家自然科学基金(61572520)。

Parallel Timing-driven Placement Algorithm for FPGA

ZHANG Jiaqi,SHEN Jianliang,ZHU Ke   

  1. (National Digital Switching System Engineering and Technological Research Center,Zhengzhou 450002,China)
  • Received:2015-11-23 Online:2017-02-15 Published:2017-02-15

摘要: 传统的基于模拟退火的现场可编程门阵列(FPGA)时序驱动布局算法在时延代价的计算上存在一定误差,已有的时序优化算法能够改善布局质量,但增加了时耗。针对上述问题,提出一种基于事务内存(TM)的并行FPGA时序布局算法TM_DCP。将退火过程分发至多线程执行,利用TM机制保证共享内存访问的合法性,并将改进的时序优化算法嵌入到事务中并发执行。测试结果表明,与通用布局布线工具相比,8线程下的TM_DCP算法在总线长仅有轻微增加的情况下,关键路径时延平均降低了4.2%,同时获得了1.7倍的加速,且其执行速度随线程数的增加具有较好的可扩展性。

关键词: 现场可编程门阵列, 模拟退火算法, 并行算法, 事务内存, 时序驱动布局

Abstract: Traditional timing-driven Field Programmable Gate Array(FPGA) placement algorithm has some degree of error when calculating timing cost.Some timing-driven algorithms achieve better placement quality with a sacrifice of time.To deal with this problem,this paper proposes a timing-driven parallel algorithm TM_DCP based on transactional memory.TM_DCP distributes block swaps into multiple threads,and then uses Transactional Memory (TM) mechanism to ensure the legality of shared memory accesses.An improved timing-driven algorithm is also added in transactions.Experimental results show that compared with Versatile Place and Route(VPR),TM_DCP with 8 threads decreases the Critical Path Delay(CPD) by 4.2% on average with relatively small increase of total wire length.It also achieves 1.7 times speedup,and scales well with the increasing of threads.

Key words: Field Programmable Gate Array(FPGA), simulated annealing algorithm, parallel algorithm, Transactional Memory(TM), timing-driven placement

中图分类号: