The tree communication scheme was shown to be very efficient for global operations on data residing in the processors of a hypercube with time complexity of O(log/sub 2/N), where N is the number of processors. This communication scheme is very useful for many parallel algorithms on hypercube multiprocessors. If a problem can be divided into independent subproblems, each subproblem can first be solved by one of the processors. Then, the tree communication scheme is invoked to merge the subresults into the final results. All the algorithms for problems with this property can benefit from the tree communication scheme. We propose a more general and efficient tree communication scheme in this paper. In addition, we also propose fault-tolerant algorithms for the tree communication scheme, by exploiting the unique properties of the tree communication scheme. The computation and communication slowdown is small (>2) under the effect of multiple link and/or node failures.
展开▼
机译：事实表明，树通信方案对于驻留在超多维数据集的处理器中的数据的全局操作非常有效，时间复杂度为O（log / sub 2 / N），其中N是处理器的数量。此通信方案对于超立方体多处理器上的许多并行算法非常有用。如果一个问题可以分为独立的子问题，则每个子问题可以首先由一个处理器解决。然后，调用树通信方案以将子结果合并为最终结果。具有此属性的所有问题算法都可以从树通信方案中受益。在本文中，我们提出了一种更通用，更有效的树通信方案。此外，我们还通过利用树通信方案的独特属性，为树通信方案提出了容错算法。在多个链路和/或节点故障的影响下，计算和通信速度变慢很小（> 2）。
展开▼
