
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Simulation Algorithms among Enhanced Mesh Models
Susumu MATSUMAE Nobuki TOKURA
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E82D
No.10
pp.13241337 Publication Date: 1999/10/25 Online ISSN:
DOI: Print ISSN: 09168532 Type of Manuscript: PAPER Category: Algorithm and Computational Complexity Keyword: parallel algorithm, simulation, reconfigurable mesh, mesh with multiple broadcasting, connected component labeling,
Full Text: PDF>>
Summary:
In this paper, we present simulation algorithms among enhanced mesh models. The enhanced mesh models here include reconfigurable mesh and mesh with multiple broadcasting. A reconfigurable mesh (RM) is a processor array that consists of processors arranged to a 2dimensional grid with a reconfigurable bus system. The bus system can be used to dynamically obtain various interconnection patterns among the processors during the execution of programs. A horizontalvertical RM (HVRM) is obtained from the general RM model, by restricting the network topology it can take to the ones in which each bus segment must be along row or column. A mesh with multiple broadcasting (MWMB) is an enhanced mesh, which has additional broadcasting buses endowed to every row and column. We present two algorithms:1) an algorithm that simulates a HVRM of size nn timeoptimally in θ(n) time on a MWMB of size nn, and 2) an algorithm that simulates a RM of size nn in θ(log^{2} n) time on a HVRM of size nn. Both algorithms use a constant number of storage in each processor. Furthermore, we show that a RM of size nn can be simulated in θ((n/m)^{2} log n log m) time on a HVRM of size mm, in θ ((n/m)^{2} m log n log m) time on a MWMB of size mm (m < n). These simulations use θ((n/m)^{2}) storage in each processor, which is optimal.

