Generation via Embedding of Quasi-Optimal Networks for Application in High Performance Computing

Overview

Supercomputers have become critical to the advancement of many fields including medical research, big data analysis, and high-energy physics. Given the recent plateau in processor speeds, however, supercomputers are growing in processor count to meet demand. Essentially, because current industry standard interconnection networks are unable to address growing latency in these large networks, it is necessary that new networks be created. We applied simulated annealing, a commonly used heuristic to solving combinatorial optimization problems, with a novel distance recalculation algorithm, applicable in a variety of dynamic systems. The results of this process were optimal graphs that approached a 51% improvement in latency over the hypercube, an industry standard, and an algorithm whose time complexity was significantly lower than standard distance computation algorithms. These solutions, while significantly increasing efficiency, lost applicability as they became too complex to implement. We then identified a new metric, entropy, to approximate the difficulty to implement a given topology and created a second algorithm to embed the generated optimal topologies with small node counts to create larger, quasi-optimal topologies with low entropy. These embedded topologies, created after determining the mathematical advantage of self-similarity over symmetry, yielded an average improvement in entropy of ~42.75% at a negligible cost to the speed improvement over the hypercube. In essence, this work served to provide the first truly viable solution by which practical, cost-effective, and applicable quasi-optimal interconnection networks can be produced to further increase the performance of supercomputers, enabling critical future research in a variety of diverse fields.

Awards (3)

• Second Award of $2,000 $2,000
• European Organization for Nuclear Research-CERN: Third Award $500 $500
• Oracle Academy: Award of $5,000 for outstanding project in the systems software category. $5,000

Competition history

• ISEF 2015 Category not listed · Entry SOFT039T

Resources

• ISEF abstract page ↗

Related projects

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