Simulation Algorithms among Enhanced Mesh Models

概要

論文の詳細を見る
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 x n time-optimally in 〓(√<n>) time on a MWMB of size n x n, and 2) an algorithm that simulates a RM of size n x n in 〓(log^2n) time on a HV-RM of size n x n. Both algorithms use a constant number of storage in each processor. Furthermore, we show that a RM of size n x n can be simulated in 〓((n/m)^2lognlogm) time on a HV-RM of size m x m, in 〓((n/m)^2√<m>lognlogm) time on a MWMB of size m x m (m < n). These simulations use 〓((n/m)^2) storage in each processor, which is optimal.
社団法人電子情報通信学会の論文
1999-10-25