An efficient scaling-simulation algorithm of a mesh with separable buses by a mesh with partitioned buses

摘要

This paper presents an efficient scaling-simulation algorithm of a mesh with separable buses (MSB) by a mesh with partitioned buses (MPB). The MSB and the MPB &e the two-dimensional mesh-connected computers equipped with broadcasting buses in every row and column. The broadcasting buses of the MSB can be dynamically sectioned into smaller bus segments by the program control, while those of the MPB are statically partitioned in advance by a fixed length. The difference of the broadcasting capability makes the MSB be a stronger computational model than the MPB. In this paper, we show that the MSB with n x n processors can be simulated in O(n/m(n/m + m{sup}(1/3))) steps by the MPB with m x m processors (m < n), which means that the MPB model is sufficient for the optimal scaling-simulation of the MSB when m≤n{sup}(3/4) holds.