|
|
|
|
|
Hypercubes are a very popular model for parallel computation because of their regularity and their relatively small number of interprocessor connections. Another important property of interconnection networks is their ability to efficiently simulate the communication of parallel algorithms. Thus, it is desirable to find suitable embeddings of graphs representing the communication structure of parallel algorithms into hypercubes representing the interconnection network of a parallel computer.
In this thesis, a general technique for embedding graphs with small extended-edge-bisectors into hypercube derived graphs will be presented. The embedding method essentially consists of two independent stages. First, using the small extended-edge-bisectors, graphs are embedded into an intermediate graph, namely the (k,h,o,l,t)-tree (pronounced cold-tree). This embedding is extended to an embedding into a hypercube like graph. It will be shown that this technique achieves embeddings whose quality is based on the quality of the extended-edge-bisector. For some special graph classes, especially binary trees and graphs with bounded treewidth, embeddings with high quality will be constructed.
It will also be shown that these embeddings can be constructed efficiently on the hypercube itself. The embeddings of binary trees and graphs with constant treewidth and constant degree can be constructed on the hypercube in time O(max{TLR,log2(n)}), where TLR(n) denotes the time complexity for list ranking on the hypercube.
Also, dynamic embeddings of binary trees into the hypercube will be presented. An optimal hypercube algorithm for one-to-one embeddings of complete binary trees into their optimal hypercube with dilation 2 will be constructed. For arbitrary binary trees, a dynamic embedding with dilation of at most 9 and unit load into the hypercube will be given. The amortized running time of this dynamic embedding is O(log2(M)) under the assumption that in each step at most M leaves have been spawned. In both algorithms, migration of tree vertices will be used. It will also be shown that migration is necessary to achieve embeddings of high quality.
Finally, it will be shown that our embeddings can be extended to a wide variety of hypercube derived topologies. The extension of the given embedding is based on the fact that our intermediate graph, namely the (k,h,o,l,t)-tree, can easily be modified to obtain embeddings into other hypercube like networks. Since the (k,h,o,l,t)-tree will be modified only slightly, the first step of the embedding need not really be modified.
Thus, our technique is widely applicable to a large class of guest graphs as well as to a large class of host graphs. Also, the algorithms will benefit from this two stage approach. The performance of our algorithms is basically influenced by the complexity of the extended-edge-bisector used. The second part of the embedding contributes only marginally to the running time.