Booth Id:
SOFT024
Category:
Systems Software
Year:
2017
Finalist Names:
Blum, Talia
Abstract:
One of the most pressing issues in modern computing is computational speed. In supercomputers, hundreds of thousands of processors, or nodes, are connected in configurations called topologies or graphs to ensure proper inter-node communication. This research focused on creating optimized topologies for networks with relatively low node counts for application in supercomputer node networks to achieve faster and more efficient computational speed. The ultimate goal is to apply these topologies to design and build a supercomputer at a major research institution. When generating these topologies, a novel algorithm is introduced, based on probabilistic searching techniques including simulated annealing. First, a near-optimal starting state graph is generated, and then it is optimized with an edge-switching probabilistic algorithm, with a time complexity of O(N^4). Efficiency of a graph is evaluated by calculating the distance between nodes to determine network diameter and average distance between nodes. The algorithms introduced in this study created absolute optimal graphs for networks of low node count and number of edges, verified by prior research in the subject by Deng et al.; the absolute optimal state was easily reached for 16-node graphs with 24 edges. For higher node counts, the most optimal graphs produced by the algorithms showed significant increases in efficiency; 64-node graphs saw an improvement of over 50.0% in network diameter and 23.3% in average distance, as compared to the hypercube, a commercial standard. Overall, the findings of this study minimized computational time of relatively small networks, and show potential for future application to larger networks. All of the described procedures and results were developed and implemented by the student.
Awards Won:
Fourth Award of $500