Packing and Legalization Free Boolean Satisfiability-based Placement Algorithm for Heterogeneous FPGAs

Placement of heterogeneous FPGAs has been a complex problem for large designs. In addition, the extensive use of FPGAs in many applications, they have become very popular since last two decades. Hence, robust but simple steps algorithms are must needed for solving different layout problems for heterogeneous FPGAs. Like other design problems, the placement problem of heterogeneous FPGAs has become very hard with the increasing number of the various components and their inter connections. In addition to that routability-aware placement is a must needed solution, since placement without routability awareness may lead to failure of routing. In this paper, a Boolean satisfiability (SAT)-based packing and legalization free placement algorithm called SatPhF has been introduced for Xilinx UltraScale FPGA architectures. The proposed technique reduces the effort given for packing and legalization in the state-of-the-art placement algorithms. Additionally, the proposed approach takes care of congestion to produce an optimized routability-aware placement solutions in terms of wirelength and congestion. This technique performs a novel placement row selection method for a set of cells connected by a net using 2-SAT formulation which is able to optimize wirelength without use of any expensive analytical optimization framework. A new legalized location finding SAT approach has been introduced to find suitable locations for different cells without performing separate legalization step like other state-of-the-art placement algorithms. Finally, a SAT-based placement refinement procedure is introduced to reduce the congestion and making the placement routable. The proposed technique claims that most of the SAT instances created to formulate the placement problem is 2-SAT. The experimental results obtained by the presented approach show its ability to perform placement reasonably well in terms of wirelength and congestion. The results have been compared with four state-of-the-art techniques and show that SatPhF achieves a reasonably well reduction in total wirelength.