Graph embedding and data communication in a large family of network topologies
Jenshiuh Liu · Michigan State University Libraries · 1992
In a parallel computer or a distributed system the interconnection pattern (network topology, interconnection topology) of the communicating modules is one of the key factors that determine the efficiency, reliability, and applicability of the system. Most previous results in the network design area are about a single kind of interconnection topology; relatively few have considered fault-tolerance. Here we present new results about graph embedding and data communication for a large family of network topologies, which consists of the generalized Fibonacci cube (63, 80) and the Incomplete Hypercube (68). This family includes the hypercube as a special case. However, unlike the hypercube, both the generalized Fibonacci cube and the Incomplete Hypercube are irregular graphs in general. The Incomplete Hypercube offers unrestrictive network size; however, it suffers from a low degree of fault-tolerance under certain situations. On the other hand, the generalized Fibonacci cube offers structural recurrences and also provides a guaranteed degree of fault tolerance. This family of network topologies has two major areas of application: (1) Fault Tolerance--each member network serves as an alternative structure for reconfiguring a hypercube in the presence of faults, and (2) Incremental Expansion--allowing a system to add nodes in small increments, which is an important advantage for systems that evolve with time. To investigate their applications in parallel or distributed systems, we present a collection of provably efficient graph embedding and data communication algorithms for this large family of network topologies. The study of graph embedding is to determine whether these networks can flexibly simulate other common networks. The results can be applied to the emulation of a given network on a family of networks; analysis of these results offers insights about the structural relationships between different networks. On the other hand, the study of common communication primitives provides efficient tools for developing application algorithms for this family of networks; it also offers insights about the relations between forms (structural properties) and functions (algorithms). Specifically, we demonstrate how to embed linear array, ring, mesh, and hypercube on the generalized Fibonacci cube; we also show how to embed linear array and ring on the Incomplete Hypercube. In addition, efficient algorithms for single node broadcasting/accumulation, single node scatter/gather, and multinode broadcasting/accumulation are presented for both the generalized Fibonacci cube and the Incomplete Hypercube. All of these algorithms are carefully analyzed under both the all- and one-port models.