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