SC Conference - Activity Details

Pattern-based Code Generation for SMVM Kernels

Mehmet Belgin  (Virginia Tech)
Godmar Back  (Virginia Tech)
Calvin J. Ribbens  (Virginia Tech)
Posters Session
Tuesday,  05:15PM - 07:00PM
Room Rotunda Lobby
Pattern-based Representation (PBR) is a sparse matrix representation to improve the performance of SMVM kernels. Unlike existing methods, PBR requires neither detection of dense blocks nor zero filling, which makes it particularly advantageous for matrices that lack dense nonzero concentrations. Motivated by our observation that most blocks in matrices share a small number of distinct patterns, we generate custom multiplication kernels for frequently recurring block patterns. We use autotuning to detect optimal blocksizes. PBR encodes the structure of each block in a bitvector and needs only one pair of indices to keep track of all nonzeros in a block, which reduces memory bandwidth usage. Our initial results indicate that PBR can yield speedups of up to 1.39 and 1.88 on PentiumIV and Opteron architectures. For many matrices, PBR performs faster than OSKI. Some matrices do not benefit, because of the altered cache access patterns caused by PBR.
   IEEE Computer Society  /  ACM     2 0   Y E A R S   -   U N L E A S H I N G   T H E   P O W E R   O F   H P C