Simulating a mesh with separable buses by a mesh with partitioned buses

We propose an algorithm that simulates a mesh with separable buses (MSB) by a mesh with partitioned buses (MPB). The MSB and the MPB are the two-dimensional mesh-connected computers which have additional broadcasting buses along every row and column. The broadcasting buses of the MSB can be dynamically sectioned into smaller bus segments of various lengths by the program control, while those of the MPB are statically partitioned in advance by a fixed length. Our algorithm takes Θ(n^1/3) steps to simulate the MSB of size n×n on the MPB of size n×n and this time, cost is shown to be optimal in the worst case. Furthermore, we discuss the advantage of the MPB, considering the influence of propagation delays of the broadcasting buses