Design And Implementation Of Parallel Layout Algorithm For

With a boost in the capacity of Field Programmable Gate Array (FPGA), it takes an increasing amount of time to compile the design. The user constraint also becomes more and more complex. In the design flow, placement is one of the most runtime-expensive steps and also plays an important role in implementing the location constraint and timing constraint.To accelerate the FPGA placement, in this paper we fully investigate the previous efforts in FPGA placement, and propose a novel placement algorithm DPSA (Dynamic Parallel Simulated Annealing) based on parallel simulated annealing. This algorithm employs a mixed framework of synchronous multi-Markov-chain and netlist partition. It uses a two-stage optimization strategy which takes advantage of multi-Markov-chain searching the solution space simultaneously as a global placement and uses the space locality of netlist partition to optimize the placement locally. In the experiments, by using four CPU cores, DPSA is2.9times faster than the serial placement algorithm VPR and simultaneously gets4%improvement on placement quality. Moreover, the acceleration performance of DPSA is scalable with the increase of CPU cores. Finally, the placement result of DPSA is deterministic because it uses synchronization between threads.To make the DPSA algorithm more useful in the real design environment, this paper designs a list of solution for absolute location constraint, relative location constraint, frequency constraint and paths delay constraint. Furthermore, we combine the constraint solution with DPSA algorithm.