Ramanujan Graphs and the Spectral Gap of Supercomputing Topologies

arXiv1909.11694MaRDI QIDQ6325983FDOQ6325983

Stephen J. Young, Sinan Aksoy, Paul Bruillard, Mark Raugas

Publication date: 25 September 2019

Abstract: Graph eigenvalues play a fundamental role in controlling structural properties, such as bisection bandwidth, diameter, and fault tolerance, which are critical considerations in the design of supercomputing interconnection networks. This motivates considering graphs with optimal spectral expansion, called Ramanujan graphs, as potential candidates for interconnection networks. In this work, we explore this possibility by comparing Ramanujan graph properties against those of a wide swath of current and proposed supercomputing topologies. We derive analytic expressions for the spectral gap, bisection bandwidth, and diameter of these topologies, some of which were previously unknown. We find the spectral gap of existing topologies are well-separated from the optimal achievable by Ramanujan topologies, suggesting the potential utility of adopting Ramanujan graphs as interconnection networks.

This page was built for publication: Ramanujan Graphs and the Spectral Gap of Supercomputing Topologies

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6325983)