• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International Conference on High Performance Computing and Communications(HPCC 2005); 20050921-23; Sorrento(IT) >Optimal Broadcast for Fully Connected Networks
【24h】

Optimal Broadcast for Fully Connected Networks

机译：全连接网络的最佳广播

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We develop and implement a new optimal broadcast algorithm for fully connected, bidirectional, one-ported networks under a linear communication cost model. For any number of processors p the number of communication rounds required to broadcast N blocks of data is [log p] - 1 + N. For data of size m, assuming that sending and receiving m data units takes time α + βm, the best running time that can be achieved is ((([log p]-1)α)~(1/2))+(βm)~(1/2))~2, meeting the lower bound under the assumption that the m units are sent as N blocks. This is better than previously known (and implemented) results, which achieve this only when p is a power of two (or other special cases), in particular, the algorithm is (theoretically) a factor two better than the commonly used, pipelined binary tree algorithm. The algorithm has a regular communication pattern based on simultaneous binomial-like trees, and when the number of blocks to be broadcast is one, degenerates into a binomial tree broadcast. Thus the same algorithm can be used for all message sizes m. The algorithm has been incorporated into a state-of-the-art MPI (Message Passing Interface) library. We demonstrate significant practical improvements of up to a factor 1.5 over several other, commonly used broadcast algorithms.
机译：我们为线性通信成本模型下的全连接，双向，单端口网络开发并实现了一种新的最佳广播算法。对于任何数量的处理器p，广播N个数据块所需的通信回合数为[log p]-1 +N。对于大小为m的数据，假设发送和接收m个数据单元花费时间α+βm，则最佳可以达到的运行时间为（（（（log p] -1）α）〜（1/2））+（βm）〜（1/2））〜2单位以N个块的形式发送。这比以前的已知结果（和已实现的结果）要好，后者仅在p是2（或其他特殊情况）的幂时才能实现这一点，特别是，该算法（理论上）比常用的流水线二进制代码好2倍。树算法。该算法具有基于同时二叉树式树的规则通信模式，并且当要广播的块数为1时，退化为二叉树广播。因此，相同的算法可以用于所有消息大小m。该算法已合并到最新的MPI（消息传递接口）库中。与其他几种常用的广播算法相比，我们展示了高达1.5倍的实际改进。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号