The Power of Collision: Randomized Parallel Algorithms for Chaining and Integer Sorting
The Power of Collision: Randomized Parallel Algorithms for Chaining and Integer Sorting
复制标题
碰撞的力量：用于链接和整数排序的随机并行算法
DOI：
--
复制
发表时间：
1990
期刊：
影响因子：
--
通讯作者：
R. Raman
中科院分区：
文献类型：
--
作者：
R. Raman
我们解决的问题，排序n个整数，每个在范围{0，.，m - 1}并行计算的PRAM模型。我们提出了一个随机算法，该算法在时间O（lg n/lg lg n + lg lg m）中以非常高的概率运行，处理器时间积为O（n lg lg m），在CRCW（碰撞）PRAM上的空间为O（n）。该算法的主要特点是它匹配现有文献[2，10]中算法的运行时间和处理器要求，同时它假设较弱的计算模型并使用线性空间量。所使用的技术扩展到用于链接问题的改进的随机化算法[11，15]，其如下：给定数组x1，...，xn，使得m个位置包含非零元素，以将所有非零元素链接在一起形成链表。我们给随机算法，运行在O（1）的时间使用n个处理器，只要m不是太接近n。我们的研究的一个副产品是一些其他排序算法所需的计算模型的削弱。
We address the problem of sorting n integers each in the range {0, ..., m - 1} in parallel on the PRAM model of computation. We present a randomized algorithm that runs with very high probability in time O(lg n/lg lg n + lg lg m) with a processor-time product of O(n lg lg m) and O(n) space on the CRCW (Collision) PRAM [7]. The main features of this algorithm is that it matches the run-time and processor requirements of the algorithms in the existing literature [2, 10], while it assumes a weaker model of computation and uses a linear amount of space. The techniques used extend to improved randomized algorithms for the problem of chaining [11, 15], which is the following: given an array x1, ..., x n , such that m of the locations contain non-zero elements, to chain together all the non-zero elements into a linked list. We give randomized algorithms that run in O(1) time using n processors, whenever m is not too close to n. A byproduct of our research is the weakening of the model of computation required by some other sorting algorithms.