Autotuning algorithmic choice for input sensitivity
Open Access
- 3 June 2015
- conference paper
- conference paper
- Published by Association for Computing Machinery (ACM) in Proceedings of the 36th ACM SIGPLAN Conference on Programming Language Design and Implementation
Abstract
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.Keywords
Funding Information
- U.S. Department of Energy (DE-SC0005288, DE-SC0008923, Early Career)
- National Science Foundation (1464216,1320796,CAREER)
This publication has 42 references indexed in Scilit:
- Performance Portability Across Heterogeneous SoCs Using a Generalized Library-Based ApproachACM Transactions on Architecture and Code Optimization, 2014
- Data representation synthesisACM SIGPLAN Notices, 2012
- Quick and Practical Run-Time Evaluation of Multiple Program OptimizationsLecture Notes in Computer Science, 2007
- OSKI: A library of automatically tuned sparse matrix kernelsJournal of Physics: Conference Series, 2005
- Sparsity: Optimization Framework for Sparse Matrix KernelsThe International Journal of High Performance Computing Applications, 2004
- Spiral: A Generator for Platform-Adapted Libraries of Signal Processing AlogorithmsThe International Journal of High Performance Computing Applications, 2004
- Optimizing Sparse Matrix Computations for Register Reuse in SPARSITYLecture Notes in Computer Science, 2001
- High-level adaptive program optimization with ADAPTACM SIGPLAN Notices, 2001
- Automated empirical optimizations of software and the ATLAS projectParallel Computing, 2001
- Induction of decision treesMachine Learning, 1986