๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Link-disjoint embedding of complete binary trees in meshes

โœ Scribed by Lee, Sang-Kyu; Choi, Hyeong-Ah

Publisher
John Wiley and Sons
Year
1997
Tongue
English
Weight
342 KB
Volume
30
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

โœฆ Synopsis

We consider the problem of embedding complete binary trees into meshes with the objective of minimizing the link congestion. Gibbons and Paterson showed that a complete binary tree T p (with 2 p 0 1 nodes) can be embedded into a 2-dimensional mesh of 2 p nodes with link congestion two. Using the dimension-ordered routing, the authors showed that T p can be embedded into a 2-dimensional mesh of (81/64)2 p nodes with link congestion one and mesh of 2 p nodes with link congestion two. This paper shows that the increase of the dimension of a mesh gives a better embedding. In particular, T p can be embedded into a 3-dimensional mesh with 2 p nodes such that the link congestion of each dimension is two, two, and one if the dimension-ordered routing is used and two, one, and one if the dimensionordered routing is not imposed. For a 4-dimensional mesh of 2 p nodes, we show that T p can be embedded with link congestion one in each dimension if p ร… 4k for an integer k.

๐Ÿ“œ SIMILAR VOLUMES

Embedding Large Complete Binary Trees in
Embedding Large Complete Binary Trees in Hypercubes with Load Balancing
โœ Kemal Efe ๐Ÿ“‚ Article ๐Ÿ“… 1996 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 211 KB

In the next section we present basic definitions and notations where the criterion of optimality is defined and related to the concept of ''normal'' algorithms. In Section 3 we present an optimal embedding method that balances the processor loads. In Section 4 we present a nonoptimal embedding metho

Optimal Dynamic Embeddings of Complete B
Optimal Dynamic Embeddings of Complete Binary Trees into Hypercubes
โœ Volker Heun; Ernst W. Mayr ๐Ÿ“‚ Article ๐Ÿ“… 2001 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 242 KB

It is folklore that the double-rooted complete binary tree is a spanning tree of the hypercube of the same size. Unfortunately, the usual construction of an embedding of a double-rooted complete binary tree into a hypercube does not provide any hint on how this embedding can be extended if each leaf

Congestion-free, dilation-2 embedding of
Congestion-free, dilation-2 embedding of complete binary trees into star graphs
โœ Tseng, Yu-Chee; Chen, Yuh-Shyan; Juang, Tong-Ying; Chang, Chiou-Jyu ๐Ÿ“‚ Article ๐Ÿ“… 1999 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 291 KB ๐Ÿ‘ 2 views

Trees are a common structure to represent the intertask communication pattern of a parallel algorithm. In this paper, we consider the embedding of a complete binary tree in a star graph with the objective of minimizing congestion and dilation. We develop two embeddings: (i) a congestion-free, dilati