Autotuning Algorithmic Choice for Input Sensitivity

作者：Ding Yufei^*; Ansel Jason; Veeramachaneni Kalyan; Shen Xipeng; O'Reilly Una May; Amarasinghe Saman

来源：ACM Sigplan Notices, 2015, 50(6): 379-390.

DOI：10.1145/2737924.2737969

• Algorithms
• Languages
• Performance
• Petabricks
• Autotuning
• Algorithmic Optimization
• Input Adaptive
• Input Sensitivity
• Two-level Input Learning

A daunting challenge faced by program performance autotuning is input sensitivity, where the best autotuned configuration may vary with different input sets. This paper presents a novel two-level input learning algorithm to tackle the challenge for an important class of autotuning problems, algorithmic autotuning. The new approach uses a two-level input clustering method to automatically refine input grouping, feature selection, and classifier construction. Its design solves a series of open issues that are particularly essential to algorithmic autotuning, including the enormous optimization space, complex influence by deep input features, high cost in feature extraction, and variable accuracy of algorithmic choices. Experimental results show that the new solution yields up to a 3x speedup over using a single configuration for all inputs, and a 34x speedup over a traditional one-level method for addressing input sensitivity in program optimizations.

• 出版日期2015-6