Abstract: 

Galaxies of Supercomputers are defined as very tightly interconnected supercomputing resources with latancies of interconnects limited only by timeofflight of the physical optical fibre infrastructure. With the continual increase of the number of petascale Supercomputers, and with very fast progress of interconnect technologies, such as Longbow(TM) from Obsidan Research cite and Mellanox MetroX cite, allowing (soon) RDMA and message passing across global scale distances, as well as research networks growth to attain Terabits per second bandwidth cite{Terabit}, we may imagine certain classess of applications, which would run well on globally federated resources spanning Supercomputer centres across the globe. In order to build a Galaxy of Supercomputers, an optimal hierarchy of interconnect topologies, spanning from an internode, intrarack, interrack through to a single Supercomputer centre and up to longdistance, interCentres, is needed. We propose a "graph of graphs hierarchy" methodology, and a graph embedding algorithm which may be used to explore colossalscale space of all possible interconnect topologies. We introduce notation: for example, a graph with $N = 8$ and $k = 3$ is denoted as $8k3$ while a composite graph resulting from embedding graph $8k3$ to graph $16k4$ is expressed as $16k4otimes8k3$. Through analysis and computations, we have discovered a series of optimal basic regular graphs for up to $N = 32$ nodes with corresponding node degrees $k = 2, 3, 4, 5$. These optimal graphs minimize the graph average nodetonode hop distances and graph diameters. The number of graphs that satisfy these optimization conditions for each pair of $(N, k)$ can be massive and an adhoc symmetry condition was introduced to prune off a majority of them. After this phase of discovery of basic regular graphs for $N = 2, 3, 4, 8, 16, 32$, we embed them to form hierarchy of graphs with quasioptimal average hop distances, diameters and total number of links. We present several top graphs $8k3otimes8k3$, $8k3otimes8k3otimes8k3$, $8k3otimes8k3otimes8k3otimes8k3$, and $16k3otimes16k3otimes16k3$, $16k4otimes16k4otimes16k4$ and the strategies to obtain them. These top graphs are the best candidates for building Galaxy of Supercomputers connecting tens of millions of processing cores residing at the multiple locations of the globe. We compare our new interconnect topologies with existing topologies: KComputer's TOFU and 5D "torus" of BlueGene/Q which can also be represented as embedded graphs.
Authors Lukasz Orlowski, A*STAR Computational Resource Center; Yuefan Deng, Stony Brook University; Marek Michalewicz, A*Star Computational Resource Center 
