GPU-based Line Probing Techniques for Mikami Routing Algorithm
Department of Computer Science and Engineering, Yuan Ze University, Taiwan 320, R.O.C.
Workshop on Synthesis And System Integration of Mixed Information Technologies (SASIMI), pp. 340-344, 2012
Graphic processing unit (GPU), which contains hundreds of processing cores, is becoming a popular device for high performance computation in multi-core era. With strictly computation regularity characteristic, specific algorithms are key challenges for performance speed-up. In this paper, we propose a parallel CUDA-Mikami routing algorithm on NVIDIA’s GPU. A 32-bit routing grid encoding is proposed to simplify wire intersection identification and wire direction recognition. Furthermore, thread-level and warp-level line probing techniques are proposed for vertical and horizontal routings, respectively. The experimental results indicate that the run-time efficiency is promising as compared to traditional CPUversion algorithms.
April 7, 2012 by hgpu
