We show that developing an optimal parallelization of the two-list algorithm is much easier than we once thought. All it takes is to observe that the steps of the search phase of the two-list algorithm are closely related to the steps of a merge procedure for merging two sorted lists, and we already know how to parallelize merge efficiently. Armed with this observation, we present an optimal and scalable parallel two-list algorithm that is easy to understand and analyze, while it achieves the best known range of processor-time tradeoffs for this problem. In particular, our algorithm based on a CREW PRAM model takes time O(2~(n/2-α) using 2~α processors, for 0 ≤ α ≤ n/2 - 2 log n + 2.
展开▼
机译：我们证明了开发两列表算法的最佳并行化要比我们曾经想的要容易得多。所有要做的就是观察两列表算法的搜索阶段的步骤与合并两个已排序列表的合并过程的步骤紧密相关，并且我们已经知道如何有效地并行化合并。有了这一观察，我们提出了一种易于理解和分析的最佳且可扩展的并行两列表算法，同时该算法实现了针对此问题的处理器时间权衡的最佳已知范围。特别地，我们的基于CREW PRAM模型的算法使用2〜α处理器花费时间O（2〜（n /2-α），对于0≤α≤n / 2-2 log n + 2。
展开▼
