Change search

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
##### Identifiers
DOI: 10.1137/0910038OAI: oai:DiVA.org:kth-91064DiVA: diva2:507917
##### Note
NR 20140805Available from: 2012-03-06 Created: 2012-03-06Bibliographically approved

#### Open Access in DiVA

No full text

Publisher's full text

#### Search in DiVA

##### By author/editor
Johnsson, Lennart
##### By organisation
Centre for High Performance Computing, PDC
##### On the subject
Computer and Information Science