Profile-guided memory layout: theory and practice

Thesis (Ph. D.)--University of Rochester. Department of Computer Science, 2018.Modern software is growing in size and complexity, far faster than is hardware in performance. In particular, it executes and accesses an increasingly large amount of code and data, leading to performance bottlenecks in different levels of the memory hierarchy. Memory layout optimization can alleviate this effect by rearranging code and data in memory, in order to reduce cache misses. In this dissertation, we study the problem of profile-guided memory layout optimization both from a theoretical and from a practical perspective. Our thesis is that while in general, finding even an approximately optimal memory layout is impractical (assuming P 6≠NP), for code layout, we can achieve significant improvements by reordering code inter-procedurally and in basic block granularity, while paying close attention to the spatial distance between related code segments in the final layout. Our inter-procedural basic block layout optimizer yields an average improvement of 10% on five real-world applications. We also propose a function reordering strategy based on a new model of reference affinity. Our evaluation shows that affinity-based function reordering results in twice as high the improvement from traditional function reordering based on call graph edges