The search functionality is under construction.

The search functionality is under construction.

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 *n**n* time-optimally in θ(*n*) time on a MWMB of size *n**n*, and 2) an algorithm that simulates a RM of size *n**n* in θ(log^{2} *n*) time on a HV-RM of size *n**n*. Both algorithms use a constant number of storage in each processor. Furthermore, we show that a RM of size *n**n* can be simulated in θ((*n*/*m*)^{2} log *n* log *m*) time on a HV-RM of size *m**m*, in θ ((*n*/*m*)^{2} *m* log *n* log *m*) time on a MWMB of size *m**m* (*m* < *n*). These simulations use θ((*n*/*m*)^{2}) storage in each processor, which is optimal.

- Publication
- IEICE TRANSACTIONS on Information Vol.E82-D No.10 pp.1324-1337

- Publication Date
- 1999/10/25

- Publicized

- Online ISSN

- DOI

- Type of Manuscript
- PAPER

- Category
- Algorithm and Computational Complexity

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

Copy

Susumu MATSUMAE, Nobuki TOKURA, "Simulation Algorithms among Enhanced Mesh Models" in IEICE TRANSACTIONS on Information,
vol. E82-D, no. 10, pp. 1324-1337, October 1999, doi: .

Abstract: 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 *n**n* time-optimally in θ(*n*) time on a MWMB of size *n**n*, and 2) an algorithm that simulates a RM of size *n**n* in θ(log^{2} *n*) time on a HV-RM of size *n**n*. Both algorithms use a constant number of storage in each processor. Furthermore, we show that a RM of size *n**n* can be simulated in θ((*n*/*m*)^{2} log *n* log *m*) time on a HV-RM of size *m**m*, in θ ((*n*/*m*)^{2} *m* log *n* log *m*) time on a MWMB of size *m**m* (*m* < *n*). These simulations use θ((*n*/*m*)^{2}) storage in each processor, which is optimal.

URL: https://global.ieice.org/en_transactions/information/10.1587/e82-d_10_1324/_p

Copy

@ARTICLE{e82-d_10_1324,

author={Susumu MATSUMAE, Nobuki TOKURA, },

journal={IEICE TRANSACTIONS on Information},

title={Simulation Algorithms among Enhanced Mesh Models},

year={1999},

volume={E82-D},

number={10},

pages={1324-1337},

abstract={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 *n**n* time-optimally in θ(*n*) time on a MWMB of size *n**n*, and 2) an algorithm that simulates a RM of size *n**n* in θ(log^{2} *n*) time on a HV-RM of size *n**n*. Both algorithms use a constant number of storage in each processor. Furthermore, we show that a RM of size *n**n* can be simulated in θ((*n*/*m*)^{2} log *n* log *m*) time on a HV-RM of size *m**m*, in θ ((*n*/*m*)^{2} *m* log *n* log *m*) time on a MWMB of size *m**m* (*m* < *n*). These simulations use θ((*n*/*m*)^{2}) storage in each processor, which is optimal.

keywords={},

doi={},

ISSN={},

month={October},}

Copy

TY - JOUR

TI - Simulation Algorithms among Enhanced Mesh Models

T2 - IEICE TRANSACTIONS on Information

SP - 1324

EP - 1337

AU - Susumu MATSUMAE

AU - Nobuki TOKURA

PY - 1999

DO -

JO - IEICE TRANSACTIONS on Information

SN -

VL - E82-D

IS - 10

JA - IEICE TRANSACTIONS on Information

Y1 - October 1999

AB - 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 *n**n* time-optimally in θ(*n*) time on a MWMB of size *n**n*, and 2) an algorithm that simulates a RM of size *n**n* in θ(log^{2} *n*) time on a HV-RM of size *n**n*. Both algorithms use a constant number of storage in each processor. Furthermore, we show that a RM of size *n**n* can be simulated in θ((*n*/*m*)^{2} log *n* log *m*) time on a HV-RM of size *m**m*, in θ ((*n*/*m*)^{2} *m* log *n* log *m*) time on a MWMB of size *m**m* (*m* < *n*). These simulations use θ((*n*/*m*)^{2}) storage in each processor, which is optimal.

ER -