Authors

Iain A. Stewart

Abstract

We study an interconnection network that we call 3Torus(m,n) obtained by pruning the 4m ×4n torus (of links) so that the resulting network is regular of degree 3. We show that 3Torus(m,n) retains many of the useful properties of tori (although, of course, there is a price to be paid due to the reduction in links). In particular, we show that 3Torus(m,n) is node-symmetric; we establish closed-form expressions on the length of a shortest path joining any two nodes of the network; we calculate the diameter precisely; we obtain an upper bound on the average inter-node distance; we develop an optimal distributed routing algorithm; we prove that 3Torus(m,n) has connectivity 3 and is Hamiltonian; we obtain a precise expression for (an upper bound on) the wide-diameter; and we derive optimal one-to-all broadcast and personalized one-to-all broadcast algorithms under both a one-port and all-port communication model. We also undertake a preliminary performance evaluation of our routing algorithm. In , we find that 3Torus(m,n) compares very favourably with tori.

Citation

  • Journal: IEEE Transactions on Computers
  • Year: 2014
  • Volume: 63
  • Issue: 10
  • Pages: 2473–2486
  • Publisher: Institute of Electrical and Electronics Engineers (IEEE)
  • DOI: 10.1109/tc.2013.139

BibTeX

@article{Stewart_2014,
  title={{Interconnection Networks of Degree Three Obtained by Pruning Two-Dimensional Tori}},
  volume={63},
  ISSN={2326-3814},
  DOI={10.1109/tc.2013.139},
  number={10},
  journal={IEEE Transactions on Computers},
  publisher={Institute of Electrical and Electronics Engineers (IEEE)},
  author={Stewart, Iain A.},
  year={2014},
  pages={2473--2486}
}

Download the bib file

References

  • System-on-Chip Design and Technologies. doi:10.1201/crcsychdetec – 10.1201/crcsychdetec
  • Rahman, M. M. H., Jiang, X., Masud, Md. S.-A. & Horiguchi, S. Network Performance of Pruned Hierarchical Torus Network. 2009 Sixth IFIP International Conference on Network and Parallel Computing 9–15 (2009) doi:10.1109/npc.2009.11 – 10.1109/npc.2009.11
  • conder, Trivalent symmetric graphs on up to 768 vertices. J Combin Math Combin Comput (2002)
  • Parhami, B. & Kwai, D.-M. Incomplete k-ary n-cube and its derivatives. Journal of Parallel and Distributed Computing 64, 183–190 (2004) – 10.1016/j.jpdc.2003.11.009
  • duato, Interconnection Networks An Engineering Approach (2002)
  • Teng, Y.-H., Tan, J. J. M. & Hsu, L.-H. Honeycomb rectangular disks. Parallel Computing 31, 371–388 (2005) – 10.1016/j.parco.2004.12.002
  • dally, Principles and Practices of Interconnection Networks (2004)
  • Sibai, F. N. A Two-Dimensional Low-Diameter Scalable On-Chip Network for Interconnecting Thousands of Cores. IEEE Trans. Parallel Distrib. Syst. 23, 193–201 (2012) – 10.1109/tpds.2011.160
  • maruši?, Symmetries of hexagonal molecular graphs on the torus. Croatia Chemica ACTA (2000)
  • Malnič, A., Nedela, R. & Škoviera, M. Lifting Graph Automorphisms by Voltage Assignments. European Journal of Combinatorics 21, 927–947 (2000) – 10.1006/eujc.2000.0390
  • Chen, D. et al. The IBM Blue Gene/Q interconnection network and message unit. Proceedings of 2011 International Conference for High Performance Computing, Networking, Storage and Analysis 1–10 (2011) doi:10.1145/2063384.2063419 – 10.1145/2063384.2063419
  • Parhami, B. & Ding-Ming Kwai. A unified formulation of honeycomb and diamond networks. IEEE Trans. Parallel Distrib. Syst. 12, 74–80 (2001) – 10.1109/71.899940
  • Camarero, C., Martinez, C. & Beivide, R. L-Networks: A Topological Model for Regular 2D Interconnection Networks. IEEE Trans. Comput. 62, 1362–1375 (2013) – 10.1109/tc.2012.77
  • Martínez, C., Beivide, R., Stafford, E., Moretó, M. & Gabidulin, E. M. Modeling Toroidal Networks with the Gaussian Integers. IEEE Trans. Comput. 57, 1046–1056 (2008) – 10.1109/tc.2008.57
  • Ashir, Y., Stewart, I. A. & Ahmed, A. Communication algorithms in k-ary n-cube interconnection networks. Information Processing Letters 61, 43–48 (1997) – 10.1016/s0020-0190(96)00188-3
  • abts, High Performance Datacenter Networks Architectures Algorithms and Opportunities (2011)
  • Feng, Y.-Q. & Kwak, J. H. Cubic symmetric graphs of order twice an odd prime-power. J. Aust. Math. Soc. 81, 153–164 (2006) – 10.1017/s1446788700015792
  • Weichsel, P. M. The Kronecker product of graphs. Proc. Amer. Math. Soc. 13, 47–47 (1962) – 10.1090/s0002-9939-1962-0133816-6
  • Feng, Y.-Q., Kwak, J. H. & Wang, K. Classifying cubic symmetric graphs of order 8p or 8p2. European Journal of Combinatorics 26, 1033–1052 (2005) – 10.1016/j.ejc.2004.06.015
  • Touzene, A., Day, K. & Monien, B. Edge-disjoint spanning trees for the generalized butterfly networks and their applications. Journal of Parallel and Distributed Computing 65, 1384–1396 (2005) – 10.1016/j.jpdc.2005.05.009
  • Fragopoulou, P. & Akl, S. G. Efficient algorithms for global data communication on the multidimensional torus network. Proceedings of 9th International Parallel Processing Symposium 324–330 doi:10.1109/ipps.1995.395952 – 10.1109/ipps.1995.395952
  • Flahive, M. & Bose, B. The Topology of Gaussian and Eisenstein-Jacobi Interconnection Networks. IEEE Trans. Parallel Distrib. Syst. 21, 1132–1142 (2010) – 10.1109/tpds.2009.132
  • Jerger, N. E. & Peh, L.-S. On-Chip Networks. Synthesis Lectures on Computer Architecture (Springer International Publishing, 2009). doi:10.1007/978-3-031-01725-4 – 10.1007/978-3-031-01725-4
  • Ishigami, Y. The wide-diameter of then-dimensional toroidal mesh. Networks 27, 257–266 (1996) – 10.1002/(sici)1097-0037(199607)27:4<257::aid-net1>3.0.co;2-f
  • Kutnar, K., Malnič, A. & Marušič, D. Chirality of Toroidal Molecular Graphs. J. Chem. Inf. Model. 45, 1527–1535 (2005) – 10.1021/ci050211t
  • Kao, S.-S. & Hsu, L.-H. Spider web networks: a family of optimal, fault tolerant, hamiltonian bipartite graphs. Applied Mathematics and Computation 160, 269–282 (2005) – 10.1016/j.amc.2003.06.005
  • Hanany, A. & Vegh, D. Quivers, tilings, branes and rhombi. J. High Energy Phys. 2007, 029–029 (2007) – 10.1088/1126-6708/2007/10/029
  • Xu, J. Topological Structure and Analysis of Interconnection Networks. Network Theory and Applications (Springer US, 2001). doi:10.1007/978-1-4757-3387-7 – 10.1007/978-1-4757-3387-7
  • Xiao, W. & Parhami, B. A Group Construction Method with Applications to Deriving Pruned Interconnection Networks. IEEE Trans. Parallel Distrib. Syst. 18, 637–643 (2007) – 10.1109/tpds.2007.1002
  • hsu, Graph Theory and Interconnection Networks (2009)
  • Zhou, S. A New Family of Trivalent Cayley Networks on Wreath Product Z m ≀S n. Jrl Syst Sci & Complex 19, 577–585 (2006) – 10.1007/s11424-006-0577-3
  • Hsu, C.-H. & Tsai, B.-R. Scheduling for atomic broadcast operation in heterogeneous networks with one port model. J Supercomput 50, 269–288 (2009) – 10.1007/s11227-008-0261-6
  • Zhang, Z. Some Properties in Hexagonal Torus as Cayley Graph. Communications in Computer and Information Science 422–428 (2011) doi:10.1007/978-3-642-18134-4_68 – 10.1007/978-3-642-18134-4_68
  • Lämmel, R. Google’s MapReduce programming model — Revisited. Science of Computer Programming 70, 1–30 (2008) – 10.1016/j.scico.2007.07.001
  • Kutnar, K., Borštnik, U., Marušič, D. & Janežič, D. Interconnection networks for parallel molecular dynamics simulation based on hamiltonian cubic symmetric topology. J Math Chem 45, 372–385 (2008) – 10.1007/s10910-008-9412-5
  • Malnič, A. Action graphs and coverings. Discrete Mathematics 244, 299–322 (2002) – 10.1016/s0012-365x(01)00090-5
  • bouwer, The Foster Census R M Foster?s Census of Connected Symmetric Trivalent Graphs (1988)
  • Bose, B., Broeg, B., Younggeun Kwon & Ashir, Y. Lee distance and topological properties of k-ary n-cubes. IEEE Trans. Comput. 44, 1021–1030 (1995) – 10.1109/12.403718
  • cai, Principle of symmetry for network topology with applications to some networks. J Netw (2010)
  • Albader, B., Bose, B. & Flahive, M. Efficient Communication Algorithms in Hexagonal Mesh Interconnection Networks. IEEE Trans. Parallel Distrib. Syst. 23, 69–77 (2012) – 10.1109/tpds.2011.112
  • ajima, Tofu: Interconnect for the K computer. FUJITSU Sci Tech J (2012)
  • Bononi, L. & Concer, N. Simulation and analysis of network on chip architectures: ring, spidergon and 2D mesh. Proceedings of the Design Automation &amp;amp; Test in Europe Conference 6 pp. (2006) doi:10.1109/date.2006.243841 – 10.1109/date.2006.243841
  • Bae, M. M. & Bose, B. Edge disjoint hamiltonian cycles in k-ary n-cubes and hypercubes. IEEE Trans. Comput. 52, 1271–1284 (2003) – 10.1109/tc.2003.1234525
  • Xiao, W. & Parhami, B. Structural properties of Cayley digraphs with applications to mesh and pruned torus interconnection networks. Journal of Computer and System Sciences 73, 1232–1239 (2007) – 10.1016/j.jcss.2007.02.010