Seminar: Henri Casanova, “Random Network Topologies”

As the scales of parallel applications and platforms increase the negative impact of communication latencies on performance becomes large. Fortunately, modern High Performance Computing (HPC) systems can exploit low-latency topologies of high-radix switches. In this talk I’ll describe the use of random shortcut topologies, which are generated by augmenting classical topologies with random links. Thursday, August 30, 4:30pm, POST 127.

Graph analysis shows that these topologies, when compared to non-random topologies of the same degree, lead to drastically reduced diameter and average shortest path length. The best results are obtained when adding random links to a ring topology, meaning that good random shortcut topologies can easily be generated for arbitrary numbers of switches. Flit-level discrete event simulation shows that random shortcut topologies achieve throughput comparable to and latency lower than that of existing non-random topologies such as hypercubes and tori. Random topologies give rise to several practical challenges, including routing scalability and larger physical cable lengths, which will be discussed.

“Random Network Topologies”, by Henri Casanova, Associate Professor of Information and Computer Sciences, University of Hawaii. Thursday, August 30, 2012. 4:30pm.  POST 127