## ''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

#### Abstract:

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.