Locality, Communication, and Interconnect Length in Multicomputers

We derive a lower bound on the average interconnect (edge) length in d-dimensional embeddings of arbitrary graphs, expressed in terms of diameter and symmetry. It is optimal for all graph topologies we have examined, including complete graph, star, binary n-cube, cube-connected cycles, complete binary tree, and mesh with wraparound (e.g., torus, ring). The lower bound is technology independent, and shows that many interconnection topologies of today’s multicomputers do not scale well in the physical world $(d = 3)$. The new proof technique is simple, geometrical, and works for wires with zero volume, e.g., for optical (fibre) or photonic (fibreless, laser) communication networks. Apparently, while getting rid of the “von Neumann” bottleneck in the shift from sequential to nonsequential computation, a new communication bottleneck arises because of the interplay between locality of computation, communication, and the number of dimensions of physical space. As a consequence, realistic models for nonsequential computation should charge extra for communication, in terms of time and space.