Wirelength-Driven Force-Directed 3D FPGA Placement

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.