S. Matsumae (Japan)
processor array, mesh-connected computer, separable bus, partitioned bus, simulation
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 are 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 pa per, we show that the MSB with n × n processors can be simulated in O( n m ( n m + m1/3 )) steps by the MPB with m × m processors (m < n), which means that the MPB model is sufficient for the optimal scaling-simulation of the MSB when m ≤ n3/4 holds.
Important Links:
Go Back
