Design and Implementation of a Throughput-Optimized GPU Floorplanning Algorithm

In this article, we propose a novel floorplanning algorithm for GPUs. Floorplanning is an inherently sequential algorithm, far from the typical programs suitable for Single-Instruction Multiple-Thread (SIMT)-style concurrency in a GPU. We propose a fundamentally different approach of exploring the floorplan solution space, where we evaluate concurrent moves on a given floorplan. We illustrate several performance optimization techniques for this algorithm in GPUs. To improve the solution quality, we present a comprehensive exploration of the design space, including various techniques to adapt the annealing approach in a GPU. Compared to the sequential algorithm, our techniques achieve 6-188X speedup for a range of MCNC and GSRC benchmarks, while delivering comparable or better solution quality.