The Arrangement Graph: A New Design for Computational Systems

Overview

Supercomputers are computers with extremely high levels of computational capacity. The vast computational power of these devices stems from the number of processors. Whereas most modern home laptops or computers have a central processing unit (CPU) consisting of two cores, supercomputers can have anywhere from a hundred to over 100,000. Due to the large number of processors, the supercomputer “interconnect”, or the connections between processors, is exceedingly important to the overall function. The design of the system topology can be modeled with a graph: the vertices represent processors and edges represent wires. Currently, the hypercube and torus graphs are commonly used for the topology. In this project, the arrangement graph was studied as an alternative. To show that it is a viable design, the resiliency to vertex and edge failure was studied with the property of strong matching preclusion. As supercomputers do often need a perfect or almost perfect matching, this property directly shows if a graph can work or not. The proof that the arrangement graph is optimal with this property utilized induction and case work. Next, with viability proven, the arrangement graph was compared to the currently used graphs in terms of cost, seen in number of edges, and speed, seen by the path lengths of the graph. Arrangement graphs measure up to, and often do better than, the currently used designs.

Competition history

• ISEF 2016 Category not listed · Entry MATH048

Resources

• ISEF abstract page ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.