Tight bounds on the simulation of meshes with dynamically reconfigurable row/column buses by meshes with statically partitioned buses

This paper studies the simulation problem of meshes with separable buses (MSB) by meshes with multiple partitioned buses (MMPB). The MSB and the MMPB are the mesh-connected computers with row/column broadcasting buses. The broadcasting buses of the MSB can be dynamically sectioned into smaller bus segments by program control, while those of the MMPB are statically partitioned in advance. In the MSB, each row/column has only one separable bus, while in the MMPB, each row/column has L partitioned buses (L⩾1,L is a fixed constant). Two results are shown: (1) the n×n MMPB can simulate any step of the n×n MSB time-optimally in O(n1/(2L+1)) steps, and (2) the m×m MMPB with L=1 can simulate any step of the n×n MSB in O(n2/m2+n1/3) steps (m⩽n). The latter implies that the MMPB with L=1 can solve the scaling-simulation problem of the MSB time-optimally when m=O(n5/6) holds.