Optimizing simulated annealing on GPU: A case study with IC floorplanning
Electr. & Comput. Eng., Utah State Univ., Logan, UT, USA
12th International Symposium on Quality Electronic Design (ISQED), 2011
@inproceedings{han2011optimizing,
title={Optimizing simulated annealing on GPU: A case study with IC floorplanning},
author={Han, Y. and Roy, S. and Chakraborty, K.},
booktitle={Quality Electronic Design (ISQED), 2011 12th International Symposium on},
pages={1–7},
organization={IEEE},
year={2011}
}
In this paper, we propose a novel floorplanning algorithm based on simulated annealing on GPUs. Simulated annealing is an inherently sequential algorithm, far from the typical programs suitable for Single Instruction Multiple Data (SIMD) 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 on GPUs. Compared to the sequential algorithm, our techniques achieve 6-160X speedup for a range of MCNC and GSRC benchmarks, while delivering comparable or better solution quality.
June 22, 2011 by hgpu
