Taming irregular EDA applications on GPUs
Tsinghua University, Beijing, China
In Proceedings of the 2009 International Conference on Computer-Aided Design (2009), pp. 539-546
@conference{deng2009taming,
title={Taming irregular EDA applications on GPUs},
author={Deng, Y.S. and Wang, B.D. and Mu, S.},
booktitle={Proceedings of the 2009 International Conference on Computer-Aided Design},
pages={539–546},
year={2009},
organization={ACM}
}
Recently general purpose computing on graphic processing units (GPUs) is rising as an exciting new trend in high-performance computing. Thus it is appealing to study the potential of GPU for Electronic Design Automation (EDA) applications. However, EDA generally involves irregular data structures such as sparse matrix and graph operations, which pose significant challenges for efficient GPU implementations. In this paper, we propose highperformance GPU implementations for two important irregular EDA computing patterns, Sparse-Matrix Vector Product (SMVP) and graph traversal. On a wide range of EDA problem instances, our SMVP implementations outperform all published work and achieve a speedup of one order of magnitude over the CPU baseline. Upon such a basis, both timing analysis and linear system solution can be considerably accelerated. We also introduce a SMVP based formulation for Breadth-First Search and observe considerable speedup on GPU implementations. Our results suggest that the power of GPU computing can be successfully unleashed through designing GPU-friendly algorithms and/or re-organizing computing structures of current algorithms.
January 13, 2011 by hgpu
