The class of optimizations characterized by manipulating a loop’s interaction space for improved cache locality and reuse (i.e, cache tiling/blocking/strip mine and interchange) are static optimizations requiring a priori information about the microarchitectural and runtime environment of an application binary. However, particularly in datacenter environments, deployed applications face numerous dynamic environments over their lifetimes. As a result, this class of optimizations can result in sub-optimal performance due to the inability to flexibly adapt iteration spaces as cache conditions change at runtime. This paper introduces continuous shape shifiting, a compilation approach that removes the risks of cache tiling optimizations by dynamically rewriting (and reshaping) deployed, running application code. To realize continuous shape shifting, we present ShapeShifter, a framework for continuous monitoring of co-running applications and their runtime environments to reshape loop iteration spaces and pinpoint near-optimal loop tile configurations. Upon identifying a need for reshaping, a new tiling approach is quickly constructed for the application, new code is dynamically generated and is then seamlessly stitched into the running application with near-zero overhead. Our evaluation on a wide spectrum of runtime scenarios demonstrates that ShapeShifter achieves an average of 10–40% performance improvement (up to 2.4 χ) on real systems depending on the runtime environment compared to an oracle static loop tiling baseline.

By Animesh Jain, Michael A. Laurenzano, Lingjia Tang, and Jason Mars. International Symposium on Microarchitecture (MICRO), 2016.