Abstract
The binary hypercube is a widely used architecture for commercial, message-passing parallel machines. Its popularity is due to its many attractive advantages, such as regular structure, high communication bandwidth, high degree of fault tolerance capabilities. But in some situations (budgetary constraints or node failures), it can be a significant drawback as the number of nodes in the binary hypercubes is restricted to a power of 2. The incomplete hypercube not only overcomes the size restriction of the complete hypercube but also retains its salient advantages. Furthermore, many variations all take the incomplete hypercube as a subgraph. Therefore, among them, incomplete hypercubes show particular importance. Incomplete binary trees and cycles are highly structured topologies frequently demanded by parallel applications. Therefore, it is important to develop efficient embedding techniques that map these two topologies onto the incomplete hypercube. On the other hand, a multiprocessing system may only allocate a part of the whole system for a task. We are therefore motivated to study the problem of how to embed incomplete binary trees and cycles of arbitrary size onto the incomplete hypercube. It has been proved that an incomplete binary tree cannot be embedded onto an incomplete hypercube with both expansion-1 and dilation-1. The existing dilation-1 embedding scheme can not solve the issue of embedding incomplete binary tree of arbitrary size onto an incomplete hypercube. Furthermore, for the quite popular Wormhole routing, the pipelined nature makes the network latency relatively insensitive to path length. And with the increase of multiprocessor nodes, the number of wires needed to interconnect them also increases. We are therefore motivated to release the constraint of dilation-1 and develop another expansion-1 embedding. In the first part of this dissertation, by the aid of some interesting properties of tree in-order traversal, we propose a simple but effective scheme which embeds an incomplete binary tree onto an incomplete hypercube with expansion (N+1)/N, dilation-2 and congestion-2. We also show that for any node in an incomplete hypercube, we can compute its corresponding mapping addresses in constant time, and vice versa. Experimental analysis confirms the effectiveness of our embedding scheme. In the second part of this dissertation, we improve the former result and give an tree embedding scheme with expansion-1, dilation-2 and congestion-2. By combining our expansion-1 scheme with the existing dilation-1 scheme, we have successfully developed an effective way to solve the problem of embedding an incomplete binary tree with arbitrary size onto incomplete hypercubes. In the third part of this dissertation, we investigate the issue of embedding cycles onto incomplete hypercubes. By horizontal decomposition of incomplete hypercubes, we show how to optimally embed a single cycle of arbitrary size onto incomplete hypercubes. It is worth noting that in all cases of dilation-2 embeddings in our algorithm, only one edge in the cycle is embedded in dilation-2. Therefore, the average dilation of our embedding algorithm approaches 1. Finally, we focus on another interesting problem: how do we effectively embed disjoint cycles onto incomplete hypercubes to execute simultaneously on disjoint parts of the network. The same problem has been solved on arrangement graph and star graph. By the aid of generalized Gray codes, we have presented a systematic and simple way to solve this problem. All of the embedding results in this dissertation can also be carried over to various variations of incomplete hypercubes, such as supercube, enhance incomplete hypercube and hamming cube.