Time-work tradeoffs for parallel algorithms
Time-work tradeoffs for parallel algorithms
复制标题
并行算法的时间与工作权衡
DOI：
10.1145/265910.265923
复制
发表时间：
1997
期刊：
影响因子：
--
通讯作者：
T. Spencer
中科院分区：
文献类型：
--
作者：
T. Spencer
一些并行算法具有以下特性：由于允许它们花费更多时间，因此它们所做的总工作量会减少。本文描述了几种具有这种性质的算法。这些算法解决了有向图上的重要问题，包括广度优先搜索、拓扑排序、强连通性和单源最短路径问题。除强连接算法运行在概率EREW PRAM上外，所有算法都运行在并行计算机的EREW PRAM模型上。
Some parallel algorithms have the property that, as they are allowed to take more time, the total work that they do is reduced. This paper describes several algorithms with this property. These algorithms solve important problems on directed graphs, including breadth-first search, topological sort, strong connectivity, and and the single source shorest path problem. All of the algorithms run on the EREW PRAM model of parallel computer, except the algorithm for strong connectivity, which runs on the probabilistic EREW PRAM.