## ''Relative Scalability of the Reconfigurable Multiple Bus Machine''

### Jerry L. Trahan

### Ramachandran Vaidyanathan

*Proc. 3rd Workshop on Reconfigurable Architectures and Algorithms*,
(Honolulu, HI, April 1996)

#### Abstract:

A model of computation *M* is said to be *scalable*
if an instance of size *N*_0 of *M* can run any
algorithm designed for an instance of size *N* > *N*_0
of *M* with a factor of
*O*(*N* / *N*_0)
increase in time. This scalability holds importance for flexibility in
algorithm design and for running various algorithms on an available
model of given size.
No reconfigurable bus-based model is known to be scalable
(through a deterministic simulation)
unless its computational power is significantly reduced.
In this paper we study the scalability of the
Reconfigurable Multiple Bus Machine (RMBM).
We introduce two new ideas: relative scalability and separable RMBM
algorithms. A relatively scalable model allows any algorithm designed
for an instance of arbitrary size *N*
to be run on an instance of size *N*_0
(representing an available machine) with a factor
*O*((*N* / *N*_0)
*f*(*N*_0) ) increase in time;
*f*(*N*_0) is independent of the simulated model
size *N*.
Relative scalability captures the ability of a given model
to efficiently adapt to different model (or problem) sizes.
The notion of separable RMBM algorithms places restrictions on
the manner in which an RMBM may operate.

In this paper we prove that every separable RMBM algorithm is
relatively scalable,
thereby extending the use of many existing RMBM algorithms.
We also show that unrestricted (non-separable) RMBM algorithms can
also be scaled with a slightly higher overhead.