FPGA并行时序驱动布局算法  

Parallel Timing-driven Placement Algorithm for FPGA

作　　者：张家齐[1] 沈剑良[1] 朱珂[1] 

机构地区：[1]国家数字交换系统工程技术研究中心,郑州450002

出　　处：《计算机工程》2017年第2期98-104,共7页Computer Engineering

基　　金：国家"863"计划重大项目(2014AA01A704);国家自然科学基金(61572520)

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

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

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]