An Efficient Scaling-Simulation Algorithm of Reconfigurable Meshes by Meshes with Statically Partitioned Buses(<Special Section>Foundations of Computer Science)

概要

論文の詳細を見る
This paper presents an efficient scaling-simulation algorithm that simulates operations of the reconfigurable mesh (RM) of size n × n using the mesh with multiple partitioned buses (MMPB) of size m × m (m < n). The RM and the MMPB are the two-dimensional mesh-connected computers equipped with broadcasting buses. The broadcasting buses of the RM can be used to dynamically obtain various interconnection patterns among the processors during the execution of programs, while those of the MMPB are placed only to every row and column and are statically partitioned in advance by a fixed length. We show that the RM of size n × n can be simulated in O (n/m (n/m + m^<1/(2L+1)) log n log m) steps by the MMPB of size m × m (m < n), where L is the number of broadcasting buses in each row/column of the simulating MMPB. Although the time-complexity of our algorithm is less efficient than that of the fastest RM scaling-simulation algorithm, the simulating model of our algorithm is the MMPB model where the bus-reconfiguration is not allowed.
社団法人電子情報通信学会の論文
2005-01-01