How promising is the k-constrained reconfigurable mesh ?

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

Paper: pdf (77K), ps (82K).


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 [176, 184, 190, 191].

Go to next publication

Return to Richard Brent's index page