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.

► We describe the impact of loop fusion on linear algebra routines.
► We present a model that estimates memory traffic for fused routines.
► Data movement estimates allow comparison of routine runtimes.
► Runtime estimates permit accurate prediction of routine performance.