Sparse matrix vector multiplication on polymorphic-torus

Abstract

A two-stage algorithm is described for sparse matrix vector multiplication on the polymorphic-torus, a reconfigurable massively parallel fine-grain architecture, to demonstrate how reconfigurability helps to alleviate matching difficulty. The first stage of the algorithm is the structured condensation which converts the irregular sparse matrix into a more uniform and much denser data structure, while the second requires the architecture to reconfigure itself to fit the condensed data structure. The algorithm highly increases the system utilization of the SIMD machines and has a lower bound in the arithmetic operation count.