Parallelizing Simulated Annealing-Based Placement Using GPGPU
Department of Electrical and Computer Engineering, University of Toronto, Toronto, ON, M5S 3G4, Canada
International Conference on Field Programmable Logic and Applications (FPL), 2010
@conference{choong2010parallelizing,
title={Parallelizing simulated annealing-based placement using GPGPU},
author={Choong, A. and Beidas, R. and Zhu, J.},
booktitle={2010 International Conference on Field Programmable Logic and Applications},
pages={31–34},
issn={1946-1488},
year={2010},
organization={IEEE}
}
Simulated annealing has became the de facto standard for FPGA placement engines since it provides high quality solutions and is robust under a wide range of objective functions. However, this method will soon become prohibitive due to its sequential nature and since the performance of single-core processor has stagnated. General purpose computing on graphics processing units (GPGPU) offers a promising solution to improve runtime with only commodity hardware. In this work, we develop a highly parallel approach to simulated annealing-based placement using GPGPU. We identify the challenges posed by the GPU architecture and describe effective solutions. An average speedup of about 10x was achieved over conventional placement within 3% of wirelength.
April 5, 2011 by hgpu
