Four vector-matrix primitives

Abstract

Abstract : This paper discusses a set of powerful primitive matrix operations which allow easy specification of parallel matrix routines. It demonstrates via the hypercube implementation that the additional expressive power need not reduce performance and can, in fact, improve performance by providing automatic load balancing in the case where there are more matrix elements than processors. Some routines based on these primitives and other simple parallel operations give some timings for the primitives and routines for our implementation on the Connection Machine. One expects to generalize these implementations of the primitives so they work on processor grids whose row and column sizes are not powers of two, and to allow a vector extracted from a row off a matrix to be distributed to or deposited in either a row or column of another matrix. The primitives should be available to higher level languages so that they can be easily used.