Professor Iain Stewart i.a.stewart@durham.ac.uk
Professor
Interconnection networks of degree three obtained by pruning two-dimensional tori
Stewart, I.A.
Authors
Abstract
We study an interconnection network that we call 3Torus(m,n) obtained by pruning the 4m x 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 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 summary, we find that 3Torus(m,n) compares very favourably with tori.
Citation
Stewart, I. (2014). Interconnection networks of degree three obtained by pruning two-dimensional tori. IEEE Transactions on Computers, 63(10), 2473-9340. https://doi.org/10.1109/tc.2013.139
Journal Article Type | Article |
---|---|
Acceptance Date | Jun 22, 2013 |
Online Publication Date | Jul 1, 2013 |
Publication Date | Oct 1, 2014 |
Deposit Date | Jun 27, 2013 |
Publicly Available Date | Jan 28, 2014 |
Journal | IEEE Transactions on Computers |
Print ISSN | 0018-9340 |
Publisher | Institute of Electrical and Electronics Engineers |
Peer Reviewed | Peer Reviewed |
Volume | 63 |
Issue | 10 |
Pages | 2473-9340 |
DOI | https://doi.org/10.1109/tc.2013.139 |
Keywords | Interconnection network, Torus, Degree 3, Shortest paths, Routing, Broadcasting. |
Publisher URL | http://doi.ieeecomputersociety.org/10.1109/TC.2013.139 |
Files
Accepted Journal Article
(407 Kb)
PDF
Copyright Statement
© 2013 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.
You might also like
Payment scheduling in the interval debt model
(2022)
Conference Proceeding
Using semidirect products of groups to build classes of interconnection networks
(2020)
Journal Article
Variational networks of cube-connected cycles are recursive cubes of rings
(2020)
Journal Article
INRFlow: An interconnection networks research flow-level simulation framework
(2019)
Journal Article