1. |
|
|
2. |
|
|
3. |
|
|
4. |
- Johnsson, Lennart
(författare)
-
Cyclic Reduction on a Binary Tree
- 1985
-
Ingår i: Computer Physics Communications. - : Elsevier BV. - 0010-4655 .- 1879-2944. ; 37:1-3, s. 195-203
-
Tidskriftsartikel (refereegranskat)abstract
- Ensembles of large numbers of processors tightly coupled into networks are of increasing interest. Binary tree interconnect has many favourable characteristics from a construction point of view, though the limited communication bandwidth between arbitrary processors poses a potential bottleneck. In this paper we present an algorithm for odd-even cyclic reduction on a binary tree for which the limited bandwidth does not increase the order of the computational complexity, compared to an ideal parallel machine. The complexity is 2 log2N with respect to arithmetic operations, and 3 log2N with respect to communication. The communication complexity compares favourably with the best previously published result, O(log22N). We also show that the benefits of truncated cyclic reduction are much greater for parallel reduction algorithms than for sequential algorithms. A reduction in the computational complexity proportional to the reduction in the number of reduction steps is possible.
|
|