Simulating a Mesh with Separable Buses

概要

論文の詳細を見る
This paper investigates the problem ofsimulating a mesh with separable buses (MSB) by a mesh with partitioned buses (MPB) and a mesh with restricted separable buses (MRSB). 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 l. The MRSB is a restricted model of the MSB, in which the broadcasting buses are placed only every l rows and l columns, and only those processors located at the crossing point of the broadcasting buses can access to the buses. We show that the MSB of size n×n can be simulated in Θ(n^l/3) time by the MPB of size n×n when l=Θ(n^2/3), and in Θ(l) time by the MRSB of size n×n. These time costs are shown to be optima1 in the worst case.
一般社団法人情報処理学会の論文
1999-10-15