Bilkent University
Department of Computer Engineering
MS Thesis Presentation


Parallel Sparse Matrix Vector Multiplication Techniques For Shared Memory Architectures


Mehmet Baaran
MS Student
(Supervisor: Prof. Dr. Cevdet Aykanat)
Computer Engineering Department
Bilkent University

SpMxV (Sparse matrix vector multiplication) is a kernel operation in linear solvers in which a sparse matrix is multiplied with a dense vector repeatedly. Due to random memory access patterns exhibited by SpMxV operation, hardware components such as prefetchers, CPU caches, and built in SIMD units are under-utilized. Consequently, limiting parallelization efficieny. In this study we developed; an adaptive runtime scheduling and load balancing algorithms for shared memory systems, a hybrid storage format to help effectively vectorize sub-matrices, an algorithm to extract proposed hybrid sub-matrix storage format.

Implemented techniques are designed to be used by both preconditioned and spontaneous SpMxV operations. Tests are carried out on Knights Corner (KNC) coprocessor which is an x86 based many-core employing NoC (Network on Chip) communication subsystem. However, proposed techniques can also be implemented for GPUs (graphical processing units).


DATE: 08 September, 2014, Monday @ 10:30