GPU accelerated sparse matrix-vector multiplication and sparse matrix-transpose vector multiplication

摘要

Many high performance computing applications require computing both sparse matrix-vector productrn(SMVP) and sparse matrix-transpose vector product (SMTVP) for better overall performance. Under such arncircumstance, it is critical to maintain a similarly high throughput for these two computing patterns with thernunderlying sparse matrix encoded in a single storage format. The compressed sparse block (CSB) formatrnproposed by Buluç et al. allows computing both problems on multi-core CPUs with nearly identical throughputs.rnOn the other hand, a direct porting of CSB to graphics processing units (GPUs), which have beenrnrecently recognized as a powerful general purpose computing platform, turns out to be inefficient. In thisrnwork, we propose a new data structure, designated as expanded CSB (eCSB), to minimize the throughputrngap between SMVP and SMTVP computations on GPUs, while at the same time enable a high computingrnthroughput. We also use a hybrid storage format to store elements in each block, which can be selectedrndynamically at runtime. Experimental results show that the proposed techniques implemented on a KeplerrnGPU delivers similar throughput on both SMVP and SMTVP and the throughput is up to 13 times fasterrnthan that of the CPU-based CSB implementation. In addition, our eCSB procedure outperforms the previousrnGPU results by up to 188% and 914% in computing SMVP and SMTVP, and we validate the effectivenessrnof eCSB by means of wall-clock time of bi-conjugate gradient algorithm; our eCSB is 25% faster thanrnCompressed Sparse Rows (CSR) and 6% faster than HYB, respectively.