Application of multi-core parallel computing in FPGA placement

As the sizes of FPGA device grow, the long run-time of the placement is becoming a great challenge for the FPGA design flow. Simulated annealing is the best-known method applied to this problem due to the good quality of result (QoR), but its computation time seems not satisfactory. In this paper, we propose a parallel placement algorithm named MPP-SA (Multi-core Parallel Placement algorithm based on Simulated Annealing). Our goal is to provide a fast placement algorithm with high QoR. MPP-SA has the same annealing schedule as the traditional simulated annealing, but it uses the parallel approach to move blocks concurrently by multiple threads that are run on different cores of the same processor. To ensure the correctness of the results, MPP-SA also uses synchronization technology and lock mechanism, which brings some overheads. However, experiment results show that these overheads have not seriously affected the performance of our algorithm, especial for large circuits. Compared with the placement algorithm of T_VPlace in VPR5.0, MPP-SA is able to decrease the run-time of 5 different size benchmark circuits by an average of 32%-42% without losing QoR.