Algorithms for optimal self-simulation
of some restricted reconfigurable meshes
176.
M. Manzur Murshed and R. P. Brent,
Algorithms for optimal self-simulation
of some restricted reconfigurable meshes,
Proc. Second International Conference on Computational Intelligence and
Multimedia Applications (Monash Univ., 1998),
World Scientific, Singapore, 1998, 734-744.
A longer version appeared as
Technical Report TR-CS-97-16, CSL, ANU, July 1997, 12 pp.
Paper:
ps (71K).
Technical Report:
pdf (206K),
ps (156K).
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 methods.
Comments
Related papers are
[171,
174,
184,
186,
190,
191,
195].
Go to next publication
Return to Richard Brent's index page