June 22–26, 2014
Leipzig, Germany

Presentation Details

Name: (09a) Galaxies of Supercomputers & Their Underlying Interconnect Topologies Hierarchies
Time: Thursday, June 26, 2014
10:30 am - 11:00 am
Room:   Hall 4
CCL - Congress Center Leipzig
Breaks:10:30 am - 11:00 am Coffee Break
07:30 am - 10:30 am Welcome Coffee
Presenter:   Marek T. Michalewicz, A*STAR
Abstract:   Galaxies of Supercomputers are defined as very tightly interconnected supercomputing resources with latancies of interconnects limited only by time-of-flight of the physical optical fibre infrastructure. With the continual increase of the number of peta-scale 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 inter-node, intra-rack, inter-rack through to a single Supercomputer centre and up to long-distance, inter-Centres, is needed.
We propose a "graph of graphs hierarchy" methodology, and a graph embedding algorithm which may be used to explore colossal-scale 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 node-to-node 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 ad-hoc 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 quasi-optimal 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: K-Computer's TOFU and 5-D "torus" of BlueGene/Q which can also be represented as embedded graphs.

Lukasz Orlowski, A*STAR Computational Resource Center; Yuefan Deng, Stony Brook University; Marek Michalewicz, A*Star Computational Resource Center