SC Conference - Activity Details

Mehmet Belgin  (Virginia Tech)

Godmar Back  (Virginia Tech)

Calvin J. Ribbens  (Virginia Tech)

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.