Ramanujan graphs and the spectral gap of supercomputing topologies

摘要

Graph eigenvalues play a fundamental role in controlling structural properties which are critical considerations in the design of supercomputing interconnection networks, such as bisection bandwidth, diameter, and fault tolerance. 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 is well separated from the optimal achievable by Ramanujan topologies, suggesting the potential utility of adopting Ramanujan graphs as interconnection networks.