A parallel FPGA Placer using GPUs.

Abstract

With the increase in the complexity of circuits and decrease in the time-to-market, there has been a demand for more efficient and faster CAD tools. Placement forms one of the most critical stages in physical design. Simulated Annealing (SA) is widely referred to in the literature as providing the best quality solution to placement. In simulated annealing, millions of random moves are tried that change the location of the logic blocks with the goal of reducing a given metric - wirelength, area or delay - of the circuit. Hence longer execution time is the major drawback of SA. The parallel computing capability of Graphic Processing Units(GPUs), combined with their low cost has made GPUs a favorable choice for a wide range of high performance computing applications. The main challenge in using GPUs is the limited amount of available memory. In this work we propose methods to carry out the random moves of SA in parallel with the help of multiple GPU threads. We show methods to partition the available memory to minimize the interaction between the sub problems thus maintaining the accuracy of the serial algorithm. Our parallel placer is based on Versatile Placer and Router(VPR), an industry standard SA based placer. Our method works for circuits with up to 1500 logic blocks and performs 37% faster compared to VPR with a maximum increase of 17% in the required wirelength.