Optimizing parallel programs using composable locality models

Thesis (Ph. D.)--University of Rochester. Department of Computer Science, 2017On modern processors, the on-chip cache memory is structured in a hierarchy, in order to accommodate the rapidly growing disparity between processor peak speed and off-chip memory speed. This design makes a program’s performance highly correlated with its memory access pattern and where the accessed data are positioned within the hierarchy. Locality analysis is to study such correlation and optimize programs accordingly. However, the existing research effort in locality analysis is rather limited when dealing with contemporary parallel workloads. The performance of these workloads can be significantly influenced by how their threads interactively access data. The state of the art in locality analysis is neither sufficient nor efficient in modeling such interaction. Therefore, in this dissertation, I will present a set of locality models to analyze modern parallel workloads. The new models give insights on how the threads share data on a quantitative basis. They have a common property, composability, which makes predicting cache miss ratio extremely efficient, especially for a large number of thread and data placements. I will also show how these models enable new optimizations that significantly improve the performance of GPU applications and parallel workloads on NUMA systems