Cyclic Reduction on a Binary Tree
1985 (English)In: Computer Physics Communications, ISSN 0010-4655, E-ISSN 1879-2944, Vol. 37, no 1-3, 195-203 p.Article in journal (Refereed) Published
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.
Place, publisher, year, edition, pages
1985. Vol. 37, no 1-3, 195-203 p.
Computer and Information Science
IdentifiersURN: urn:nbn:se:kth:diva-91121DOI: 10.1016/0010-4655(85)90153-5OAI: oai:DiVA.org:kth-91121DiVA: diva2:508335
NR 201408052012-03-082012-03-08Bibliographically approved