Modeling the memory and performance impacts of loop fusion

On modern processors, data transfer exceeds floating-point operations as the predominant cost in many linear algebra computations. One tuning technique that focuses on reducing memory accesses is loop fusion. Determining the optimum amount of loop fusion to apply to a routine is difficult as fusion can both positively and negatively impact memory traffic. We present a model that accurately and efficiently evaluates how loop fusion choices affect data movement through the memory hierarchy. We show how to convert the model’s memory traffic predictions to runtime estimates that can be used to compare loop fusion variants.