Optimal Parallel Algorithms for Interger Sorting and Graph Connectivity.
Optimal Parallel Algorithms for Interger Sorting and Graph Connectivity.
复制标题
整数排序和图连接的最佳并行算法。
DOI：
--
复制
发表时间：
1985
期刊：
影响因子：
--
通讯作者：
J. Reif
中科院分区：
文献类型：
--
作者：
J. Reif
摘要：本文给出了整数排序和无向图连通性问题（如连通分量和生成森林）的新的并行算法。这些算法仅花费对数时间，并且是第一个已知的最优算法：它们的时间和处理器边界的乘积由输入大小的线性函数限制。所有以前已知的并行算法，这些问题需要至少一个线性数量的处理器，以实现对数的时间界限，因此是非最佳的至少一个对数因子。作者假设了一个并行随机存取机（RAM）模型，它允许全局存储器的并发写和并发读。算法是随机的;允许每个处理器具有独立的随机数生成器;然而，我们所述的资源界限对于随着输入大小增长而具有压倒性可能性的最坏情况输入保持不变。（作者）
Abstract : This document gives new parallel algorithms for integer sorting and undirected graph connectivity problems such as connected components and spanning forest. These algorithms cost only logarithmic time and are the first known that are optimal: the product of their time and processor bounds are bounded by a linear function of the input size. All previous known parallel algorithms for these problems required at least a linear number of processors to achieve logarithmic time bounds, and hence were nonoptimal by at least a logarithmic factor. The author assumes a parallel random access machine (RAM) model which allows both concurrent writes and concurrent reads of global memory. The algorithms are randomized; each processor is allowed an independent random number generator; however our stated resource bounds hold for worst case input with overwhelming likelihood as the input size grows. (Author)