Emulation of a PRAM on Leveled Networks

There is an interesting class of ICNs, which includes the star graph and the n-way shuffle, for which the network diameter is sub-logarithmic in the network size. This paper presents, for the first time, optimal emulations of the CRCWPRAM on the star graph and the n-way shuffle. These results are special cases of a more general result that gives an optimal emulation of the CRCWPRAM on a large class of nonconstant degree leveled networks. We also present an efficient emulation of the CRCW PRAM on a two-dimensional mesh. Although Ranade’s emulation technique can be applied to the mesh to obtain an asymptotically optimal algorithm for emulation of the PRAM, the underlying constant in the time bound will be very large, say 100, making it uninteresting from a practical point of view. In this paper we provide a better emulation algorithm whose time bound is only 4n + o(n). This algorithm also has some nice ‘locality ’ properties (e.g. if each request for memory access originates within a distance d of the location of the memory, then the algorithm terminates in 6d + o(d) steps). The queue size of this algorithm is O(1)