Parallel algorithms for generating random permutations on a shared memory machine
Parallel algorithms for generating random permutations on a shared memory machine
复制标题
在共享内存机器上生成随机排列的并行算法
DOI：
--
复制
发表时间：
1990
期刊：
影响因子：
--
通讯作者：
Richard J. Anderson
中科院分区：
文献类型：
--
作者：
Richard J. Anderson
在本文中，我们考虑在小型并行机上生成随机排列的问题。我们想到的机器是具有恒定数量处理器的共享内存机器，例如顺序对称机器。我们描述了用于生成随机排列的“洗牌”算法的并行实现。如果硬件以公平的方式运行，该算法会生成完全随机的排列。但是，如果机器以恶意方式解决争用，则该算法不会统一生成排列。我们对对手可以减少随机性的程度给出了几乎严格的限制。我们还讨论了算法中锁定数据的成本，并提出了一种生成随机排列的方法，大大降低了锁定成本。
In this paper we consider the problem of generating random permutations on small parallel machines. The machines that we have in mind are shared memory machines with a constant number of processors such as the Sequent Symmetry. We describe a parallel implementation of the " shuffling " algorithm for generating a random permutation. If the hardware operates in a fair manner, this algorithm generates a fully random permutation. However, if the machine resolves contention in a malicious manner, then the algorithm does not generate permutations uniformly. We give almost tight bounds on the degree that an adversary can reduce the randomness. We also discuss the cost of locking data in the algorithm and present a method of generating random permutations with substantially reduced locking cost.