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


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.