Superlinear Speedup for Matrix Multiplication in GPU Devices

Springer papers

Authors

Leonid Djinevski , Sasko Ristov and Marjan Gusev

Abstract

Speedup in parallel execution on SIMD architecture according to Amdahl’s Law is finite. Further more, according to Gustrafson’s Law, there are algorithms that can achieve almost linear speedup. However, researchers have found some examples of superlinear speedup for certain types of algorithms executed on specific multiprocessors. In this paper we achieved superlinear speedup for GPU devices, which are also categorized as SIMD. We implement a structure persistent algorithm which efficiently exploits the shared cache memory and avoids cache misses as much as possible. Our theoretical analysis and experimental results show the existence of superlinear speedup for algorithms that run on existing GPU device.

Keywords

Cache memory Matrix Multiplication GPU CUDA HPC Superlinear Speedup