| Abstract |
|
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 Theta(n^{1/3}) steps to simulate the MSB of size n \times n on the MPB of size n \times 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.
|
 Additional Information
|
Index Terms- two-dimensional mesh-connected computer, broadcasting, mesh with separable buses, mesh with partitioned buses, simulation algorithm, propagation delay
Citation:
Susumu Matsumae, Nobuki Tokura,
"Simulating a Mesh with Separable Buses by a Mesh with Partitioned Buses,"
ispan,
p. 198,
1999 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '99),
1999
|
