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

中图分类号: 

• TP311