首页> 外文OA文献 >Concurrent threads and optimal parallel minimum spanning trees algorithm
【2h】

Concurrent threads and optimal parallel minimum spanning trees algorithm

机译:Concurrent threads and optimal parallel minimum spanning trees algorithm

摘要

This paper resolves a long-standing open problem on whether the concurrent write capability of parallel random access machine (PRAM) is essential for solving fundamental graph problems like connected components and minimum spanning trees in O(log n) time. Specifically, we present a new algorithm to solve these problems in O(log n) time using a linear number of processors on the exclusive-read exclusive-write PRAM. The logarithmic time bound is actually optimal since it is well known that even computing the "OR" of n bits requires Ω(log n) time on the exclusive-write PRAM. The efficiency achieved by the new algorithm is based on a new schedule which can exploit a high degree of parallelism.
机译:本文解决了一个长期存在的开放性问题,即并行随机存取机(PRAM)的并发写入能力是否对于解决基本图形问题(如O(log n)时间内的连通组件和最小生成树)至关重要。具体来说,我们提出了一种新算法来解决在O(log n)时间内使用排他读取专有写入PRAM上的线性处理器数量的这些问题。对数时限实际上是最佳的,因为众所周知,即使计算n位的“或”,在互斥PRAM上也需要Ω(log n)时间。新算法实现的效率基于可以利用高度并行性的新计划。

著录项

  • 作者

    Han Y; Chong KAW; Lam TW;

  • 作者单位
  • 年度 2001
  • 总页数
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类

相似文献

  • 外文文献
  • 中文文献
  • 专利

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号