Simulation Algorithms among Enhanced Mesh Models

Susumu MATSUMAE  Nobuki TOKURA  

IEICE TRANSACTIONS on Information and Systems   Vol.E82-D   No.10   pp.1324-1337
Publication Date: 1999/10/25
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Algorithm and Computational Complexity
parallel algorithm,  simulation,  reconfigurable mesh,  mesh with multiple broadcasting,  connected component labeling,  

Full Text: PDF>>
Buy this Article

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 2-dimensional 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 horizontal-vertical RM (HV-RM) 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 HV-RM of size nn time-optimally in θ(n) time on a MWMB of size nn, and 2) an algorithm that simulates a RM of size nn in θ(log2 n) time on a HV-RM 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 HV-RM 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.