''Integer and Floating Point Matrix-Vector Multiplication on the Reconfigurable Mesh''

Jerry L. Trahan

Chun-ming Lu

Ramachandran Vaidyanathan

Proc. International Parallel Processing Symposium, (Honolulu, HI, April 1996), pp. 702-706


This paper presents the following results for matrix-vector multiplication on the reconfigurable mesh (R-Mesh). Multiplication of an N x N matrix and an N x 1 vector (each element of which is an integer of w bits) can be performed in O(log w) time on a two-dimensional O(N(w / log w)log^2 N) x O(N(w / log w)log^2 N) R-Mesh or a three-dimensional N x N x (w / log w)log^2 N R-Mesh; in both cases, inputs and outputs are stored as w-bit integers.

A natural extension of this problem is for floating point inputs; floating point numbers have not been handled before on any reconfigurable bus-based model. We show that the above matrix-vector multiplication with floating point inputs can be performed in O(max{loglog N, log w}) time on an N x N x max{sqrt{N / loglog N}, (w / log w)log^2 N} three-dimensional R-Mesh, with the inputs and outputs stored as w-bit floating point numbers. This algorithm can also be converted to run on a two-dimensional R-Mesh.