高级检索
隋文涛, 董社勤, 边计年. 力驱动三维FPGA布局算法[J]. 计算机辅助设计与图形学学报, 2011, 23(10): 1665-1671.
引用本文: 隋文涛, 董社勤, 边计年. 力驱动三维FPGA布局算法[J]. 计算机辅助设计与图形学学报, 2011, 23(10): 1665-1671.
Sui Wentao, Dong Sheqin, Bian Jinian. Wirelength-Driven Force-Directed 3D FPGA Placement[J]. Journal of Computer-Aided Design & Computer Graphics, 2011, 23(10): 1665-1671.
Citation: Sui Wentao, Dong Sheqin, Bian Jinian. Wirelength-Driven Force-Directed 3D FPGA Placement[J]. Journal of Computer-Aided Design & Computer Graphics, 2011, 23(10): 1665-1671.

力驱动三维FPGA布局算法

Wirelength-Driven Force-Directed 3D FPGA Placement

  • 摘要: 三维FPGA布局问题的复杂度与二维情况相比成指数倍增长,布局算法需要花费大量时间,影响了FPGA物理设计效率.为了在保证布局质量的前提下缩短布局时间,提出以线长为优化目标基于力驱动的三维FPGA布局算法——3D-WFP.该算法由整体布局、坐标合法化和层划分、布局优化3个阶段组成,通过力驱动算法快速形成整体布局,为后续2个子过程提供更精确的逻辑单元位置和时延信息.提出三维空间填充曲线,根据位置和时延信息依次对逻辑单元按照三维空间填充曲线进行坐标合法化和层划分;修正了低温模拟退火进行布局优化的解空间,大大加快了低温模拟退火的收敛速度.与已有的三维FPGA布局算法比较,3D-WFP在保证运行时间和时延性能的前提下,有效地缩短了最终布局结果,缩短的总线长达7.38%.

     

    Abstract: The complexity of three-dimensional FPGA placement grows exponentially comparing with the two-dimensional case,which results in more running time of the placement algorithm and affects the efficiency of FPGA physical design.A wirelength-driven force-directed three-dimensional field programmable gate arrays(FPGA) placement algorithm(3D-WFP) is presented for the purpose of guaranteeing quality and shorting the time cost.The algorithm is composed of three stages: overlap permitted 2D force-directed placement,legalization and 3D layer partition.We adjust the two-dimensional force-directed placement algorithm into three-dimensional,which effectively provides the global interconnection and timing information for the next two sub-stages.To legalize the position of the logic block,a 3D space filling curve is adopted.Different from traditional partition-based 3D placers,we adjust the layer partition process after the 2D global placement.A low temperature simulated annealing(SA) is used to determine the blocks final layer,and only blocks with the same horizontal coordinate are permitted to interchange.The speed of the SA is very fast.Compared to recent work on 3D FPGA placement,this algorithm improves the half perimeter wire-length(HPWL) by 7.38%,almost at the same cost of running time and keeps the same timing performance.

     

/

返回文章
返回