Congestion-free, dilation-2 embedding of complete binary trees into star graphs
Yu‐Chee Tseng, Yuh‐Shyan Chen, Tong Ying Juang, Chiou‐Jyu Chang · Networks · 1999
Trees are a common structure to represent the inter-task communication pattern of a parallel algorithm. In this paper, we consider the embedding a complete binary tree in a star graph with the objective of minimizing congestion and dilation. We develop two embeddings: i) a congestion-free, dilation-2, load-1 embedding of a level- p binary tree, and ii) a congestion-free, dilation-2, load-2 k embedding of a level-(p+k) binary tree, into an n-dimensional star graph, where p = \\Sigma n i=2 blog ic = \\Omega\\Gamma n log n) and k is any positive integer. The first result offers a tree of size comparable or superior to existing results, but with less congestion and dilation. The second result provides more flexibility in the embeddable tree sizes compared to existing results. Keywords: Graph embedding, interconnection network, complete binary tree, star graph, parallel processing. This research was supported in part by the National Science Council, R.O.C., under grant numbers NS...