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