Implementation of simultaneous memory address access in models that forbid it

Abstract

Models of synchronized parallel computation in which all the processors have access to a common memory are considered. We focus on algorithms in models that allow simultaneous access to the same memory location, for both read and write instructions. Assume that such an algorithm uses p processors, d time units, and s memory space. We present a universal algorithm that implements this algorithm in models that forbid simultaneous access to the same memory location, using p processors, O(dlog2p) time units, and O (s + p) memory space his implementation algorithm is shown to compare favorably with its conventional naive counterpart, as the extra memory space it requires is independent of the implemented algorithm. © 1983.