Change search
ReferencesLink to record
Permanent link

Direct link
Cyclic Reduction on a Binary Tree
KTH, School of Computer Science and Communication (CSC), Centres, Centre for High Performance Computing, PDC. (Parallelldatorcentrum)
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
Abstract [en]

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.
National Category
Computer and Information Science
URN: urn:nbn:se:kth:diva-91121DOI: 10.1016/0010-4655(85)90153-5OAI: diva2:508335
NR 20140805Available from: 2012-03-08 Created: 2012-03-08Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Johnsson, Lennart
By organisation
Centre for High Performance Computing, PDC
In the same journal
Computer Physics Communications
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 17 hits
ReferencesLink to record
Permanent link

Direct link