How promising is the k-constrained
reconfigurable mesh ?
M. Manzur Murshed and R. P. Brent,
How promising is the k-constrained reconfigurable mesh ?,
Proc. 15th ISCA International Conference on
Computers and their Applications
(New Orleans, March 2000), 9 pp.
The Reconfigurable Mesh (RM) has attracted criticism for its key assumption
that a message can be broadcast in constant time independent of bus length.
To account for this limit, the k-constrained RM model has recently
been proposed, where buses of length at most k segments are allowed
to be configured at any step. Straightforward simulations of
AT2 optimal RM algorithms on this constrained model are
found to be non-optimal but several AT2 optimal algorithms
have already been developed on the model.
In this paper we prove that,
if attaining AT2 optimality is a goal of developing algorithms
on the k-constrained RM, then the k-constrained RM does not
make any difference to the original "unconstrained" RM.
Related papers are
Go to next publication
Return to Richard Brent's index page