About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Journal of Algorithms
Paper
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.