GPU-based Line Probing Techniques for Mikami Routing Algorithm

Chiu-Yi Chan, Jiun-Li Lin, Lung-Sheng Chien, Tsung-Yi Ho, Yi-Yu Liu
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


   title={GPU-based Line Probing Techniques for Mikami Routing Algorithm},

   author={Chan, C.Y. and Lin, J.L. and Chien, L.S. and Ho, T.Y. and Liu, Y.Y.},



Download Download (PDF)   View View   Source Source   



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.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: