Relations between concurrent-write models of parallel computation
Relations between concurrent-write models of parallel computation
复制标题
DOI：
10.1145/800222.806745
复制
发表时间：
1984-08
期刊：
影响因子：
--
通讯作者：
Faith Ellen;P. Ragde;A. Wigderson
中科院分区：
文献类型：
--
作者：
Faith Ellen;P. Ragde;A. Wigderson
平行计算的共享模型（例如，平行杆）非常自然，并且已经广泛用于并行算法设计。这些模型对于理解并行计算的力量很重要。对于n尺寸n的实例，可以在o（1）时间上解决的问题，该问题可以在n处理器的婴儿身上进行，该计划允许简单写入（分别读取）访问共享内存，但需要ω（log n）时间禁止简单的写入（分别读取）访问权限，无论允许简单的写入访问权限时，模型都必须包括写入冲突的解决方案。在这里研究它们的相对力量。为此目的开发了模型之间的分离结果，从而部分回答了Vishkin [V]的开放问题。
Shared-memory models for parallel computation (e.g. parallel RAMs) are very natural and already widely used for parallel algorithm design. The various models differ from each other mainly in the way they restrict simultaneous processor access to a shared memory cell. Understanding the relative power of these models is important for understanding the power of parallel computation. Two recent pioneering works shed some light in this question. Cook and Dwork [CD] (resp. Snir [S]) present problems that, for instances of size n, can be solved in O(1) time on an n-processor PRAM that allows simultaneous write (resp. read) access to shared memory, but require Ω(log n) time on a PRAM that forbids simultaneous write (resp. read) access, regardless of the number of processors. When allowing simultaneous write access, the model must include a write-conflict resolution scheme. Three such schemes were suggested in the literature, and in this paper we study their relative power. Here the situation is more sensitive, as a small increase in the number of processors allows constant time simulation of the strongest by the weakest. By fixing the number of processors and parametrizing the number of shared memory cells, we obtain tight separation results between the models, thereby partially answering open questions of Vishkin [V]. New lower bounds techniques are developed for this purpose.