An new representation for interconnection network structures

Abstract

An important theoretic interest is to study the relations between different interconnection networks, and to compare the capability and performance of the network structures. The most popular way to do the investigation is network emulation. Based on the classical voltage graph theory, the authors develop a new representation scheme for interconnection network structures. The new approach is a combination of algebraic methods and combinatorial methods. The results demonstrate that the voltage graph theory is a powerful tool for representing well-known interconnection networks and in implementing optimal network emulation algorithms, and in particular, show that all popular interconnection networks have very simple and intuitive representations under the new scheme. The new representation scheme also offers powerful tools for the study of network routings and emulations. For example, we present very simple constructions for optimal network emulations from the cube-connected cycles networks to the butterfly networks, and from the butterfly networks to the hypercube networks. Compared with the most popular way of network emulation, this new scheme is intuitive and easy to realize, and easy to apply to other network structures.

Keywords

interconnection network / network emulation / parallel computation

References

[1] LeightonF TIntroduction to parallel algorithms and architectures: Aarrays, trees, hypercubes [M], 1992, San Mateo, California, Morgan Kaufmann

[2] AkersB, KrishnamurthyB. A group-theoretic model for symmetric interconnection networks [J]. IEEE Transactions on Computers, 1989, 38(4): 555-566

[3] Annexstein, BaumslagM, RosenbergA L. Group action graphs and parallel architectures [J]. SIAM Journal on Computing, 1990, 19(3): 544-569

[4] GrossJ L. Voltage graphs [J]. Discrete Mathematics, 1974, 9: 239-246

[5] LakshmivarahanS, DhallS K. Ring, torus and hypercube architectures/algorithms for parallel computing [J]. Parallel Computing, 1999, 25: 1877-1906

[6] GuQ P, PengS. Unicast in hypercubes with large number of faulty nodes[J]. IEEE Transactions on Parallel and Distributed Systems, 1999, 10(10): 964-975

[7] LeuY R, KuoS Y. Distributed fault-tolerant ring embedding and reconfiguration in hypercubes[J]. IEEE Transactions on Computers, 1999, 48(1): 81-88

[8] GermaA, HeydemannM C, SotteauD. Cycles in the cube-connected cycles graph [J]. Discrete Applied Mathematics, 1998, 83: 135-155

[9] KlasingR. Improved compressions of cube-connected cycles networks [J]. IEEE Transactions on Parallel and Distributed Systems, 1998, 9(4): 803-812

[10] Avior, CalamoneriT, EvenS, et al.. A tight layout of the butterfly network[J]. Theory of Computing Systems, 1998, 31(4): 475-488

[11] BhattS N, ChungF R, HongJ W, et al.. Optimal emulations by butterfly-like networks[J]. Journal of ACM, 1996, 43(2): 293-330

[12] BermondJ C, DarrotE, DelmasO, et al.. Hamilton cycle decomposition of the butterfly network [J]. Parallel Processing Letters, 1998, 8: 371-385

[13] FeldmanR, UngerW. The cube-connected cycles network is a subgraph of the butterfly network [J]. Parallel Processing Letters, 1992, 2: 13-19

[14] SaadY, SchultzM H. Topological properties of hypercubes [J]. IEEE Transactions on Computers, 1998, 37(7): 867-872

[15] GreenbergD S, HeathL S, RosenbergA L. Optimal embeddings of butterfly-like graphs in the hypercube [J]. Mathematical Systems Theory, 1990, 23(1): 61-77

[16] Chen J E, Liu L H, Chen S Q, et al. An intuitive and effective new representation for interconnection network structures [A]. In: Lecture Notes in Computer Science 1969 [C]. G. Goos, ed. Taipei, Taiwan, 2000.