中文摘要：

传统的基于模拟退火的现场可编程门阵列（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.