Evaluating the role of optimization-specific search heuristics in effective autotuning

Abstract. The increasing complexities of modern architectures require compilers to extensively apply a large collection of architecture-sensitive optimizations, e.g., parallelization and memory locality optimizations, which interact with each other in unpredictable ways. The configura-tion space of these optimizations are exceedingly large, and heuristics for exploring the search space routinely end up settling for subopti-mal solutions. We present a transformation-aware (TA) search algorithm which effectively combines optimization-specific heuristics (i.e., heuristics a compiler could use) to explore the configuration space of six optimiza-tions, parallelization via OpenMP, cache blocking, array copying, unroll-and-jam, scalar replacement, and loop unrolling, to improve the multi-threading, memory system and microprocessor performance of three lin-ear algebra routines. We compare the effectiveness of the TA-search al-gorithm with generic search algorithms (e.g., hill climbing, simulated annealing) commonly adopted in autotuning research and empirically study the performance tradeoffs of various optimization-specific heuris-tics when used to speed up the search process.