Creating interconnect topologies by algorithmic edge removal: MOD and SMOD graphs

Marek T. Michalewicz; Łukasz P. Orłowski; Yuefan Deng

doi:10.14529/jsfi150402

Authors

Marek T. Michalewicz A*STAR Computational Resource Centre, Singapore A*STAR Institute of High Performance Computing, Singapore Stony Brook University, Stony Brook
Łukasz P. Orłowski A*STAR Computational Resource Centre, Singapore Stony Brook University, Stony Brook
Yuefan Deng Stony Brook University, Stony Brook

DOI:

https://doi.org/10.14529/jsfi150402

Abstract

We introduce a method of constructing classes of graphs by algorithmic removal of entire groups of edges. Our approach to creating new classes of graphs is to focus entirely on the structure and properties of the adjacency matrix. At an initialisation step of the algorithm we start with a complete (fully connected) graph. In Part I we present MOD and arrested MOD graphs resulting from removal of square blocks of edges at each iteration and substitution of removed blocks with a diagonal matrix with one extra pivotal element along the main diagonal. The MOD graphs possess unique and useful properties. All important graph measures are easily expressed in analytical form and are presented in the paper. Several important properties of MOD graphs compare very favourably with graphs representing common interconnect topologies: hypercube, 3D and 5D tori, TOFU and dragony. This lead us to consider MOD and arrested MOD graphs as interesting candidats for eective supercomputer interconnects.
In Part II, at each iterative step we successively remove triangular shapes from adjacency matrix. This iterative process leads to the nal matrix which has two Sierpinski gaskets aligned along the main diagonal. It will be shown below, that this new class of graphs is not a Sierpinski graph, since it is the adjacency matrix which has a structure of a Sierpinski gasket, and not a graph described by this matrix. We call this new class of graphs Sierpinski-Michalewicz-Or lowski-Deng (SMOD) graphs. The most remarkable property of the SMOD class of graphs, is that irrespective of the graph order, the diameter is constant and equals 2. The size of the graph, or the total number of edges, is about 10% of the size of a complete graph of the same order. We analyse important graph theoretic characte-ristics related to the topology such as diameter as a function of graph order, size, mean path length, ratio of the graph size to the size of a complete graph of the same order, and some spectral properties.

Keywords: supercomputer interconnects, big data, exascale computing, graph theory,
topology of graphs, classes of graphs, graph generation.

References

http://www.infoworld.com/d/computer-hardware/china-building-100-petaflop-

supercomputer-206072. Last accessed: 2014.08.05.

http://www.top500.org/lists/2014/06/. Last accessed: 2014.08.05.

http://www.cray.com/Products/Computing/XK7/Technology.aspx. Last accessed: 2014.08.05.

https://bluewaters.ncsa.illinois.edu/user-guide. Last accessed: 2014.08.05.

https://computing.llnl.gov/tutorials/bgq/#Networks. Last accessed: 2014.08.05.

http://www.nas.nasa.gov/hecc/resources/pleiades.html. Last accessed: 2014.08.05.

http://www.cscs.ch/computers/pizdaint/index.html. Last accessed: 2014.08.05.

Report on the workshop on extreme-scale solvers: Transitions to future architectures. Technical report, Oce of Advanced Scientic Computing Research, U.S. Department of Energy, March 2012. http://science.energy.gov/ascr/news-and-resources/programdocuments/, Last accessed: 2014.08.05.

On advanced scientic computing research exascale mathematics working group (emwg) report for 2014. Technical report, The Department of Energy (DOE) Oce of Science Program, 2014. https://collab.mcs.anl.gov/display/examath/Exascale+Mathematics+Home, Last accessed: 2014.08.05.

Yuichiro Ajima, Shinji Sumimoto, and Toshiyuki Shimizu. Tofu: A 6d mesh/torus interconnect for exascale computers. Computer, 11(42):36--40, 2009.

Richard F Barrett, Courtenay T Vaughan, Simon D Hammond, and D Roweth. Application explorations for future interconnects. In Parallel and Distributed Processing Symposium Workshops & PhD Forum (IPDPSW), 2013 IEEE 27th International, pages 1717--1724.IEEE, 2013.

RB Borie, R Gary Parker, and CA Tovey. 2.4 recursively constructed graphs. Handbook of Graph Theory, page 99, 2004.

J. P. Brown. Hypercubes. Practical Computing, Vol. 5 No. 4, pages 97--99, 1982.

Dragos M Cvetkovic, Peter Rowlinson, and Slobodan Simic. Eigenspaces of graphs. Number 66. Cambridge University Press, 1997.

William James Dally and Brian Patrick Towles. Principles and practices of interconnection networks. Elsevier, 2004.

Greg Faanes, Abdulla Bataineh, Duncan Roweth, Edwin Froese, Bob Alverson, Tim Johnson, Joe Kopnick, Mike Higgins, James Reinhard, et al. Cray cascade: a scalable hpc system based on a dragon y network. In Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis, page 103. IEEE Computer Society Press, 2012.

A Gara, ME Giampapa, P Heidelberger, S Singh, BD Steinmacher-Burow, T Takken, M Tsao, and P Vranas. BlueGene/L torus interconnection network. 2005.

M. Kan. China is building a 100-peta op supercomputer. IDG News Service, infoworld.com (2012-10-31).

John Kim, Wiliam J Dally, Steve Scott, and Dennis Abts. Technology-driven, highly-scalable dragony topology. In ACM SIGARCH Computer Architecture News, volume 36, pages 77--88. IEEE Computer Society, 2008.

F Thomson Leighton. Introduction to parallel algorithms and architectures: Arrays trees hypercubes. Elsevier, 2014.

Matt Knepley Mark F. Adams, Jed Brown. Low-communication techniques for extreme-scale multilevel solvers. https://collab.mcs.anl.gov/display/examath/Submitted+Papers. Last accessed: 2014.08.05.

Richard Otter. The number of trees. Annals of Mathematics, pages 583--599, 1948.

Piet Van Mieghem. Graph spectra for complex networks. Cambridge University Press, 2010.