On arrowhead and diamond diameters
Abstract
Arrowhead and diamond form a family of two hierarchical Cayley graphs defined on the triangular grid. In their undirected version, they are isomorphic and merely define two distinct representations of the same graph. This paper gives the expression of their diameter, in the oriented and non–oriented case. It also displays the full distribution of antipodals.
This family could appear as a promising topology for Network–on–Chip architectures.
Keywords
Full Text:
PDFDOI: http://dx.doi.org/10.5614/ejgta.2025.13.1.6
References
D. Désérable, A family of Cayley graphs on the hexavalent grid, Discrete Applied Math. 93(2-3) (1999) 221–241
D. Désérable, Broadcasting in the arrowhead torus, Computers and Artificial Intelligence 16(6) (1997) 545–559
M.C. Heydemann, N. Marlin, S. Pérennes, Complete rotations in Cayley graphs, European J. Combinatorics 22(2) (2001) 179–196
D. Désérable, Systolic dissemination in the arrowhead family, ACRI 2014, J. Was, G. Sirakoulis, S. Bandini, eds., LNCS 8751 (2014) 75–86
D.N. Jayasimha, B. Zafar, Y. Hoskote, On–Chip Interconnection Networks: why they are different and how to compare them, Intel Corporation (2006) 1–11
D.B. Balfour, W.J. Dally, Design tradeoffs for tiled CMP on–chip networks, ICS 2006 – Int. Conf. Supercomp. (2006) 187–198
E. Salminen, A. Kulmala, T.D. Hämäläinen, On network–on–chip comparison, DSD 2007 – Digital System Design: Architectures, Methods and Tools (2007) 503–510
J.C. Bermond, F. Comellas, D.F. Hsu, Distributed loop computer networks: a survey, J. Par. Dist. Comp. 24 (1995) 2–10
A.L. Davis, S.V. Robison, The architecture of the FAIM-1 symbolic multiprocessing system, Proc. 9th Int. Joint. Conf. on Artificial Intelligence (1985) 32–38
A. Davis, Mayfly – a general-purpose, scalable, parallel processing architecture, J. LISP and Symbolic Computation 5 (1992) 7–47
M.S. Chen, K.G. Shin, and D.D. Kandlur, Addressing, routing and broadcasting in hexagonal mesh multiprocessors, IEEE Trans. Comp. 39 (1) (1990) 10–18
C.L. Seitz, The Cosmic Cube, Comm. ACM 28(1) (1985) 22–33
K.P. Huber, Codes over Eisenstein–Jacobi integers, Finite Fields: Theory, Applications & Algorithms, G.L. Mullen, P.J.S. Shiue, eds., Contemporary Math. 168 (1994) 165–179
B. Albader, B. Bose, and M. Flahive, Efficient communication algorithms in hexagonal mesh interconnection networks, IEEE Trans. Par. Dist. Sys. 23 (1) (2012) 69–77
D. Désérable, Versatile topology for two–dimensional cellular automata, Advances in Cellular Automata, A. Adamatzky, G.Ch. Sirakoulis, G.J. Martínez (eds), Emergence, Complexity and Computation 52 (2025) (to appear)
B.B. Mandelbrot, The fractal geometry of nature, Freeman and Cie (1982) D. Désérable, A versatile two-dimensional cellular automata network for granular flow, SIAM J. Applied Math. 62 (4) (2002) 1414–1436
D. Désérable, S. Masson, and J. Martinez, Influence of exclusion rules on flow patterns in a lattice-grain model, Powders & Grains, Kishino, Y. (ed.) Balkema (2001) 421–424
D. Désérable, Propagative mode in a lattice-grain CA: time evolution and timestep synchronization, ACRI 2012 – G. Sirakoulis, S. Bandini, eds., LNCS 7495 (2012) 20–31
D. Désérable, Embedding Kadanoff’s scaling picture into the triangular lattice, Acta Phys. Pol. B Proc. Suppl. 4 (2) (2011) 249–265
P. Ediger, R. Hoffmann, and D. Désérable, Routing in the triangular grid with evolved agents, J. Cellular Automata 7(1) (2012) 47–65
P. Ediger, R. Hoffmann, and D. Désérable, Rectangular vs. triangular routing with evolved agents, J. Cellular Automata 8(1–2) (2013) 73–89
R. Hoffmann, D. Désérable, All-to-All communication with cellular automata agents in 2d Grids – Topologies, streets and performances, J. Supercomp. 69 (1) (2014) 70–80
R. Hoffmann and D. Désérable, Routing by cellular automata agents in the triangular lattice, Robots and Lattice Automata, G.Ch. Sirakoulis, A. Adamatzky (eds), Emergence, Complexity and Computation 13 (2015) 117–147
W.J. Dally and C.L. Seitz, The torus routing chip, Distributed Computing 1 (1986) 187–196 Y. Xiang and I.A. Stewart, Augmented k–ary n–cubes, Information Sci. 181 (1) (2011) 239–256
D. Désérable, Arrowhead and diamond diameters, arXiv.org/abs/2205.00489 (2022) 1–17 W.-H.
Hu, Eun Lee,and N. Bagherzadeh, Dmesh: a diagonally-linked mesh Network-on-Chip architecture, api.semanticscholar.org/CorpusID:17633766
M.H. Furhad and J.-M. Kim, An extended diagonal mesh topology for Network-on-Chip architectures, Int. J. Multimedia and Ubiquitous Eng. 10 (10) (2015) 197–210
Refbacks
- There are currently no refbacks.
ISSN: 2338-2287
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.