Change search
ReferencesLink to record
Permanent link

Direct link
Spanning Balanced Trees in Boolean cubes
KTH, School of Computer Science and Communication (CSC), Centres, Centre for High Performance Computing, PDC. (Parallelldatorcentrum)
1989 (English)In: SIAM JOURNAL ON SCIENTIFIC AND STATISTICAL COMPUTING, Vol. 10, no 4, 607-630 p.Article in journal (Refereed) Published
Abstract [en]

A Spanning Balanced$n$-tree (SBnT) in a Boolean $n$-cube is a spanning tree in which the root has fanout $n$, and all the subtrees of the root have $O({{2^n } / n})$ nodes. The number of tree edges in each dimension of the $n$-cube is of order $O({{2^n } / n})$. The spanning balanced n-tree allows for scheduling disciplines that realize lower bound (within a factor of two) one-to-all personalized communication, all-to-all broadcasting, and all-to-all personalized communication on a Boolean $n$-cube [C.-T. Ho and S. L. Johnsson, Proc. 1986 International Conference on Parallel Processing, pp. 640–648, IEEE Computer Society, 1986; Tech. Report YALEU/DCS/RR–483, May 1986], [S. L. Johnsson and C.-T. Ho, Tech. Report YALEU/DCS/RR–610, Dept. of Computer Science, Yale Univ., New Haven, CT, November 1987]. The improvement in data transfer time over the familiar binomial tree routing is a factor of ${n / 2}$ for concurrent communication on all ports and one-to-all personalized communication and all-to-all broadcasting. For all-to-all personalized communication on all ports concurrently, the improvement is of order $O(\sqrt n )$. Distributed routing algorithms defining the spanning balanced $n$-tree are given. The balanced $n$-tree is not unique, and a few definitions of $n$-trees that are effectively edge-disjoint are provided. Some implementation issues are also discussed. Binary numbers obtained from each other through rotation form necklaces that are full if the period is equal to the length of the number; otherwise, they are degenerate. As an intermediary result, it is shown that the ratio between the number of degenerate necklaces and the total number of necklaces with $l$ bits equal to one is at most ${4 / {(4 + n)}}$ for $1 \leqq l < n$

Place, publisher, year, edition, pages
1989. Vol. 10, no 4, 607-630 p.
Keyword [en]
Boolean cubes, balanced trees, spanning trees, personalized communication, routing, shuffles, necklaces, periodicity
National Category
Computer and Information Science
URN: urn:nbn:se:kth:diva-91064DOI: 10.1137/0910038OAI: diva2:507917
NR 20140805Available from: 2012-03-06 Created: 2012-03-06Bibliographically 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
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: 28 hits
ReferencesLink to record
Permanent link

Direct link