Understanding the Efficiency of GPU Algorithmsfor MatrixMatrix Multiplication


Kayvon Fatahalian Stanford University 
Jeremy Sugerman Stanford University 
Pat Hanrahan Stanford University 

Presented at Graphics Hardware 2004. 

Abstract:
Utilizing graphics hardware for general purpose numerical computations has become a topic of considerable interest. The implementation of streaming algorithms, typified by highly parallel computations with little reuse of input data, has been widely explored on GPUs. We relax the streaming model's constraint on input reuse and perform an indepth analysis of dense matrixmatrix multiplication, which reuses each element of input matrices O(n) times. Its regular data access pattern, and highly parallel computational requirements suggest matrixmatrix multiplication as an obvious candidate for efficient evaluation on GPUs, but surprisingly we find that even nearoptimal GPU implementations are pronouncedly less efficient than current cacheaware CPU approaches. We find that the key cause of this inefficiency is that the GPU can fetch less data and yet execute more arithmetic operations per clock than the CPU when both are operating out of their closest caches. The lack of high bandwidth access to cached data will impair the performance of GPU implementations of any computation featuring significant input reuse.
Figure 1: Performance of multiplying square matrices on a
3 GHz Pentium 4, NVIDIA GeForceFX 5900 Ultra, prerelease
GeForce 6800XT, ATI Radeon 9800XT, and prerelease
Radeon X800XT.


Paper:
Posted 6/29/2004 