''Degree of Scalability:
Scalable Reconfigurable Mesh Algorithms for Multiple Addition
and Matrix-Vector Multiplication''
Ramachandran Vaidyanathan
Jerry L. Trahan
Chun-ming Lu
Parallel Computing, vol. 29, no. 1, pp. 95-109, 2003
Abstract:
The usual concern when scaling an algorithm on a parallel model
of computation is preserving efficiency while increasing or decreasing
the number of processors.
Many algorithms for reconfigurable models, however, attain
constant time at the expense of an inefficient algorithm.
For these algorithms, scaling down the number of processors
while preserving inefficiency is no benefit once constant time
execution is lost.
In fact, one can often accelerate the efficiency of these algorithms
while reducing the number of processors.
To quantify this improvement in efficiency, this paper introduces
the measure of degree of scalability to complement the
insight obtained from efficiency for such algorithms.
Demonstrating the utility of this measure, we present
new reconfigurable mesh (R-Mesh) algorithms for
multiple addition and matrix-vector multiplication,
improving both the number of processors
and the degree of scalability compared to previous algorithms.
We also extend these results to floating point number operands,
which have previously received little attention on the R-Mesh.
This work was supported in part by
the National Science Foundation under grant numbers CCR-9503882
and CCR-0073429
and the Louisiana Board of Regents through the
Louisiana Education Quality Support Fund
under contract number LEQSF(1994-96)-RD-A-07.