...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Journal of Parallel and Distributed Computing >Asymptotically optimal dynamic tree evolution by rapidly mixing random walks on regular networks
【24h】

Asymptotically optimal dynamic tree evolution by rapidly mixing random walks on regular networks

机译：通过快速混合规则网络上的随机游动的渐近最优动态树演化

获取原文
获取原文并翻译 | 示例
   

获取外文期刊封面封底 >>

       
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Tree-structured computations are among the most popular and important and powerful computing paradigms in computer science. In many such applications, the size and shape of a tree that represents a parallel computation is dynamic and unpredictable at compile time. The tree evolves gradually during the course of the computation. When such an application is executed on a multicomputer system with a static network, the dynamic tree evolution problem is to distribute the tree nodes to the processors of the network such that all the processors receive roughly the same amount of load and that communicating nodes are assigned to neighboring processors. The main contribution of the paper is to conduct a unified study of dynamic tree evolution on regular networks. Our regular networks include d-dimensional torus networks, d-dimensional lattice networks, complete d-partite networks, and random regular networks. These networks include several fundamental networks such as rings, k-ary d-cubes, complete networks, and hypercubes as special cases. We describe a simple random-walk-based asymptotically optimal dynamic tree evolution algorithm on regular networks and analyze the exponential speed at which the performance ratio converges to the optimal. Our strategy is to prove that the Markov chain of a random walk on a regular network is rapidly mixing in the sense that, starting from any initial distribution, the Markov chain converges to its stationary distribution in a small number of steps. We also show that larger dilation results in better tree node distribution.
机译：树型计算是计算机科学中最流行，最重要和最强大的计算范例之一。在许多此类应用程序中，代表并行计算的树的大小和形状在编译时是动态且不可预测的。该树在计算过程中逐渐演化。当这样的应用程序在具有静态网络的多计算机系统上执行时，动态树演化问题是将树节点分配给网络的处理器，以使所有处理器接收大致相同的负载量并分配通信节点到邻近的处理器。本文的主要贡献是对规则网络上的动态树演化进行了统一研究。我们的常规网络包括d维环面网络，d维晶格网络，完整的d部分网络和随机常规网络。这些网络包括几个基本网络，例如环，k ary d多维数据集，完整网络和超多维数据集（作为特例）。我们在规则网络上描述了一种简单的基于随机行走的渐近最优动态树演化算法，并分析了性能比收敛到最优的指数速度。我们的策略是证明规则网络上随机游动的马尔可夫链正在快速混合，从某种意义上说，从任何初始分布开始，马尔可夫链均会以少量步骤收敛到其静态分布。我们还表明，较大的扩张会导致更好的树节点分布。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号