Evaluating the Role of Optimization-Specific Search Heuristics in Effective Autotuning

Date

2010-07

Authors

Guo, Jichi
Yi, Qing
Qasem, Apan

Journal Title

Journal ISSN

Volume Title

Publisher

UTSA Department of Computer Science

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 configuration space of these optimizations are exceedingly large, and heuristics for exploring the search space routinely end up settling for suboptimal 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 optimizations, parallelization via OpenMP, cache blocking, array copying, unroll-and-jam, scalar replacement, and loop unrolling, to improve the multithreading, memory system and microprocessor performance of three linear algebra routines. We compare the effectiveness of the TA-search algorithm 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 heuristics when used to speed up the search process.

Description

Keywords

Citation

Department

Computer Science