High Performance Data Traversal

Abstract

"What Mathematics is to Physics, Data traversal is to High-performance computing." The world of Computational science has witnessed an exponential expansion of sophisticated numerical algorithms in the last few decades mainly to understand minute details and solve complex physical problems. It has established itself as the third pillar of science after theory and experimentation and has managed to gain immense popularity as a mainstream research work among academicians and scientists working in entirely different fields. The Computational Sciences has brought together Mathematicians and Computer Scientists to work in close collaboration on the variety of interdisciplinary research problems. The principal challenge to achieve high performance for computational researchers in near about every front is data traversal, data placement, and memory access pattern which mostly influences floating point performance and energy efficiency. The Data traversal is the soul of high-performance computing. Indeed it is the backbone; the way data travels to the CPU from main memory mainly influences the performance of particular computational kernel on specific machine architecture. The majority of modern computing devices are designed to deliver high performance if data traversal can utilize maximum bandwidth to main memory (DRAM) and make efficient use of hierarchical memory structure. Thus, a hardware optimal data access pattern should be designed to take advantage of the underlying hardware to scale and achieve performance, and that forms the central theme of this work. The more important point here is, expensive hardware or massive computational infrastructure does not naturally invoke high-performance computing but implementation of hardware auxiliary mathematical ideas, cache efficient data traversal strategies, sensible use of parallel programming paradigms and energy aware management of computational resources on machines ranging from very grass-root level primary NUMA system to entire million core server stack does. In this master's thesis, we will first focus on investigating the impact of data traversal patterns on the performance of several micro-benchmarks on Non-Uniform Memory Access machine, and in the second part, we will implement Morton-order Space Filling Curve to improve cache utilization for two numerical methods and analyze performance impact.