ANU Computer Science Technical Reports
TR-CS-97-16
M. Manzur Murshed and Richard P. Brent.
Algorithms for optimal self-simulation of some restricted reconfigurable
meshes.
July 1997.
[POSTSCRIPT (158160 bytes)]
Abstract: There has recently been an interest in the
introduction of reconfigurable buses to existing parallel architectures.
Among them the Reconfigurable Mesh (RM) draws much attention because of its
simplicity. However the wide acceptance of RM depends on its scalability
through self-simulation. This paper presents a simple self-simulation
algorithm which can self-simulate the monotonic RM model optimally and the
piecewise-monotonic RM model asymptotically optimally. We claim here that our
algorithm preserves the essence of configurational computation and uses less
broadcasts than simulation by the contraction and linear-connected component
computation methods.
Technical Reports <Technical.Reports@cs.anu.edu.au>
Last modified: Wed Jul 23 13:50:18 EST 1997