Abstract
The Mcube network has been proposed in [11] as a highly recursive and symmetrical interconnection network based on twisted links [1]. The Mcube topology has been developed and defined in terms of the structural constraints between components to enforce structural symmetry instead of specifying edges between node pairs. Mcubes have almost half the diameter of a comparable hypercube, a lower average internode distance than most other twisted networks and an uniform spatial node distribution. Unlike most twisted cube-based networks, randomly destined traffic results in uniform traffic flow through every node in the Mcube and links in the Mcube saturate more slowly than hypercubes. The Mcube is recursively partitionable and allows several parallel algorithms to execute as fast as or faster than on a hypercube. We establish the node distribution for the Mcubes to be uniform with the internode distance. Based on the constraints imposed by the construction and the routing algorithm, we derive an expression for the average internode distance for Mcubes. We also introduce an efficient broadcasting algorithm for the Mcube interconnection and show how Mcubes can be reconfigured into hypercubes. Finally, we show how representative parallel algorithms can be directly implemented on the Mcube topology.
Chapter PDF
References
S. Abraham and K. Padmanabhan, “An Analysis of the twisted Cube Topology,” Proc. 1989 International Conference on Parallel Processing, Vol. 1, pp.116–120.
N. Bhuyan and D. P. Agrawal, “Generalized Hypercube and Hyperbus structures for a Computer Network,” IEEE Trans. on computers, vol. C-33, No. 1, April 1984, pp. 323–333.
P. Cull and S. Larson, “The Mobius Cubes,” Proc. 6th Distributed Memory Computing Conference, April 1991, pp.699–702.
K. Efe, “The Crossed Cube,” IEEE Trans. on parallel and distributed systems. Vol. 3. No. 5, September 1992, pp. 513–524.
K. Ghose and K. R. Desai, “The Design and Evaluation of the Hierarchical Cubic Network,” Proc. 1990 International Conference on Parallel Processing, Vol. 1, pp. 355–362.
P. A. J. Hilbers, M. R. J. Koopman and J. L. A. van de Snepscheut. “The Twisted Cube,” Parallel Architectures and Languages Europe, June 1987, pp. 152–159.
K. Hwang and J. Ghosh, “Hypernet: A Communication Efficient Architecture for Constructing Massively Parallel Computers,” IEEE Trans. on Computers, Vol. C-36, No. 12, Dec 1987, pp. 1450–1466.
S. Lakshmivarahan and S. K. Dhall, “A New Hierarchy of Hypercube Interconnection Schemes for Parallel Computers,” Journal of Supercomputing, Vol. 2, 1988, pp. 81–108.
F. P. Preparata and J. Vuillemin, “The Cube-Connected Cycles: A Versatile Network for Parallel Computation,” Comm. ACM, Vol. 24, No. 5, May 1981, pp. 300–309.
N. K. Singhvi and K. Ghose, “A Detailed Study of the Mcube Interconnection Topology,” Technical Report No.CS-TR-93-14, Dept. of Computer Science, SUNY Binghamton, 1993.
N. K. Singhvi and K. Ghose, “The Mcube: A Symmetrical Cube Based Network with Twisted Links,” Proc. 9th International Parallel Processing Symposium, 1995, pp. 11–16.
N. K. Singhvi, “The Connection Cubes: Symmetric, Low Diameter Networks with Low Node Degree,” Proc. 1993 International Parallel Processing Symposium, pp. 260–267.
L. D. Wittie, “Communication Structures for Large Networks of Microcomputers,” IEEE Trans on Computers, Vol. C-30, No. 4, April 81, pp. 264–273.
H. Sullivan and T. R. Bashkow, “A Large Scale, Homogeneous, Fully Distributed, Parallel Machine I,” Proc. Fourth International Symposium on Computer Architecture, March 1977, pp. 26–38.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1995 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Singhvi, N.K., Ghose, K. (1995). A formal study of the Mcube interconnection network. In: Haridi, S., Ali, K., Magnusson, P. (eds) EURO-PAR '95 Parallel Processing. Euro-Par 1995. Lecture Notes in Computer Science, vol 966. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0020494
Download citation
DOI: https://doi.org/10.1007/BFb0020494
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-60247-7
Online ISBN: 978-3-540-44769-6
eBook Packages: Springer Book Archive