Autotuning systems employ empirical techniques to evaluate the suitability of a search space of possible implementations of a computation. Autotuning has emerged as a critical strategy for achieving high performance as architectural complexity grows. Present-day autotuning technology augments the capabilities of expert users or is hidden inside compilers, but to date has not been adopted as a mainstream technology. Based on our prior experience and the experience of others in developing autotuning technology and applying it to libraries and applications, this paper examines some of the barriers to adoption of the technology and future research areas to break down these barriers.
AgakovFBonillaECavazosJ. (2004) Using machine learning to focus iterative optimization. In: Proceedings of the international symposium on code generation and optimization.
2.
AlexandrescuA (2001) Modern C++ design: generic programming and design patterns applied. Boston, MA: Addison-Wesley Longman Publishing Co., Inc.
3.
AnselJChanCWongYL. (2009) Petabricks: a language and compiler for algorithmic choice. In: Proceedings of the 2009 ACM SIGPLAN conference on programming language design and implementation (PLDI ‘09). New York: ACM Press, pp. 38–49. DOI: 10.1145/1542476.1542481.
BalaySBrownJBuschelmanK. (2010) PETSc Users Manual. Technical Report ANL-95/11 - Revision 3.1, Argonne National Laboratory. Available at: http://www.mcs.anl.gov/petsc.
6.
BarreteauMBodinFChamskiZ. (1999) Oceans - optimising compilers for embedded applications. In: Proceedings of Euro-Par, pp. 1171–1175.
7.
BarthouDDonadioSDuchateauACarribaultPJalbyW (2007) Loop optimization using adaptive compilation and kernel decomposition. In: ACM/IEEE international symposium on code optimization and generation. San Jose, CA: IEEE Computer Society, pp. 170–184.
8.
BaskaranMMBondhugulaUKrishnamoorthySRamanujamJRountevASadayappanP (2008a) Automatic data movement and computation mapping for multi-level parallel architectures with explicitly managed memories. In: ACM SIGPLAN symposium on principles and practice of parallel programming.
9.
BaskaranMMBondhugulaUKrishnamoorthySRamanujamJRountevASadayappanP (2008b) A compiler framework for optimization of affine loop nests for GPGPUs. In: Proceedings of the 22nd annual international conference on supercomputing (ICS ‘08).
10.
BaskaranMMHartonoATavarageriSHenrettyTRamanujamJSadayappanP (2010a) Parameterized tiling revisited. In: Proceedings of the 8th annual IEEE/ACM international symposium on code generation and optimization (CGO ‘10).
11.
BaskaranMMRamanujamJSadayappanP (2010b) Automatic C-to-CUDA code generation for affine programs. In: Proceedings of the international conference on compiler construction.
12.
BilmesJAsanovicKChinCWDemmelJ (1997) Optimizing matrix multiply using PHiPAC: A portable, high-performance, ANSI C coding methodology. In: Proceedings of the international conference on supercomputing.
13.
BondhugulaUHartonoARamanujamJSadayappanP (2008) A practical automatic polyhedral parallelizer and locality optimizer. In: Proceedings of ACM SIGPLAN conference on programming language design and implementation.
14.
BussAHarshvardhanPapadopoulos I. (2010) STAPL: standard template adaptive parallel library. In: Proceedings of the 3rd annual Haifa experimental systems conference (SYSTOR ‘10). New York: ACM Press, pp. 14:1–14:10. DOI: 10.1145/1815695.1815713.
15.
CampbellDPBensonTMCookDA. (2012) Challenge applications and scalable metrics (CHASM). Final Technical Report Contract HR0011-10-C-0145, Georgia Tech Research Institute, Georgia Institute of Technology.
16.
ChenC (2007) Model-Guided Empirical Optimization for Memory Hierarchy. Ph.D. thesis, University of Southern California.
17.
ChenCChameJHallMW (2005) Combining models and guided empirical search to optimize for multiple levels of the memory hierarchy. In: Proceedings of the international symposium on code generation and optimization. Available at: http://www.cs.utah.edu/~chunchen/papers/cgo05_chen.pdf.
18.
ChristenMSchenkOBurkhartH (2011) PATUS: A code generation and autotuning framework for parallel iterative stencil computations on modern microarchitectures. In: Proceedings of the IEEE international parallel and distributed processing symposium, pp. 676–687.
19.
CooperKDSchielkePJSubramanianD (1999) Optimizing for reduced code space using genetic algorithms. In: Proceedings of ACM SIGPLAN workshop on languages, compilers, and tools for embedded systems (LCTES’99).
20.
CuiHWangLXueJYangYFengX (2011) Automatic library generation for BLAS3 on GPUs. In: Proceedings of IEEE international parallel and distributed processing symposium.
21.
DattaKMurphyMVolkovV. (2008) Stencil computation optimization and auto-tuning on state-of-the-art multicore architectures. In: Proceedings of supercomputing ‘08.
22.
DingCKennedyK (1999) Improving cache performance in dynamic applications through data and computation reorganization at run time. In: Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation (PLDI ‘99).
23.
DonadioSBrodmanJRoederT. (2005) A language for the compact representation of multiple program versions. In: Proceedings of the 18th international workshop on languages and compilers for parallel computing.
24.
FatahalianKHornDRKnightTJ. (2006) Sequoia: programming the memory hierarchy. In: Proceedings of the 2006 ACM/IEEE conference on supercomputing (SC ‘06). New York: ACM Press. DOI: 10.1145/1188455.1188543.
25.
FinkEPolyaG (1998) How to solve it automatically: Selection among problem-solving methods. In: Proceedings of the fourth international conference on artificial intelligence planning systems. AAAI Press, pp. 128–136.
26.
FrigoM (1999) A fast Fourier transform compiler. In: Proceedings of ACM SIGPLAN conference on programming language design and implementation.
27.
GanapathiADattaKFoxAPattersonD (2009) A case for machine learning to optimize multicore performance. In: Proceedings of the first USENIX conference on hot topics in parallelism (HotPar’09). Berkeley, CA: USENIX Association.
28.
GirbalSVasilacheNBastoulC. (2006) Semi-automatic composition of loop transformations for deep parallelism and memory hierarchies. International Journal of Parallel Programming34(3): 261–317.
GuerriAMilanoM (2004) Learning techniques for automatic algorithm portfolio selection. In: Proceedings of the 16th European conference on artificial intelligence (ECAI 2004). IOS Press, pp. 475–479.
31.
GuoH (2003) A Bayesian approach for automatic algorithm selection. In: Proceedings of the IJCAI workshop on AI and autonomic computing: Developing a research agenda for self-managing computer systems.
32.
HallMWChameJChenCShinJRudyG (2009) Transformation recipes for code generation and auto-tuning. In: Proceedings of the international workshop on languages and compilers for parallel computing.
33.
HartonoANorrisBSadayappanP (2009) Annotation-based empirical performance tuning using Orio. In: IEEE international parallel and distributed processing symposium (IPDPS), Rome, Italy.
34.
HolewinskiJPouchetLNSadayappanP (2012) High-performance code generation for stencil computations on GPU architectures. In: Proceedings of the 26th ACM international conference on supercomputing (ICS ‘12).
35.
KamilSChanCOlikerLShalfJWilliamsS (2010) An auto-tuning framework for parallel multicore stencil computations. In: Proceedings of the international parallel and distributed processing symposium.
36.
KhanMBasuPRudyGHallMChenCChameJ (2013) A script-based autotuning compiler system to generate high-performance CUDA code. ACM Transactions on Architecture and Code Optimization9(4): 31:1–31:25. DOI: 10.1145/2400682.2400690.
37.
KotthoffLGentIPMiguelI (2011) A preliminary evaluation of machine learning in algorithm selection for search problems. In: Proceedings of the fourth annual symposium on combinatorial search.
38.
LagoudakisMGLittmanML (2000) Algorithm selection using reinforcement learning. In: Proceedings of the seventeenth international conference on machine learning (ICML ‘00). San Francisco, CA: Morgan Kaufmann Publishers Inc., pp. 511–518.
39.
LeeSEigenmannR (2010) OpenMPC: Extended OpenMP programming and tuning for GPUs. In: Proceedings of the 2010 ACM/IEEE international conference for high performance computing, networking, storage and analysis (SC ‘10). Washington, DC: IEEE Computer Society, pp. 1–11. DOI: 10.1109/SC.2010.36.
40.
LeungAVasilacheNMeisterB. (2010) A mapping path for multi-GPGPU accelerated computers from a portable high level programming abstraction. In: Proceedings of the 3rd workshop on general-purpose computation on graphics processing units.
41.
Leyton-BrownKNudelmanEAndrewGMcfaddenJShohamY (2003) A portfolio approach to algorithm selection. In: Proceedings of the international joint conference on artificial intelligence, pp. 1542–1543.
42.
LiXGarzaránMJPaduaD (2004) A dynamically tuned sorting library. In: Proceedings of the international symposium on code generation and optimization: feedback-directed and runtime optimization (CGO ‘04).
43.
LiXGarzaranMJPaduaD (2005) Optimizing sorting with genetic algorithms. In: Proceedings of the international symposium on code generation and optimization (CGO ‘05).
44.
LobjoisLLemaitreM (1998) Branch and bound algorithm selection by performance prediction. In: Proceedings of the association for the advancement of artificial intelligence. AAAI Press, pp. 353–358.
45.
MametjanovALowellDMaCCNorrisB (2012) Autotuning stencil-based computations on GPUs. In: Proceedings of CLUSTER, pp. 266–274.
46.
MerrillDGarlandMGrimshawA (2012a) Policy-based tuning for performance portability and library co-optimization. In: Proceedings of innovative parallel computing: Foundations and applications of GPU, manycore, and heterogeneous systems (InPar ‘12).
47.
MerrillDGarlandMGrimshawA (2012b) Scalable GPU graph traversal. In: Proceedings of the 17th ACM symposium on principles and practice of parallel programming (PPoPP ‘12).
48.
NarayananSHKNorrisBHovlandPD (2010) Generating performance bounds from source code. In: Proceedings of the 2010 39th international conference on parallel processing workshops (ICPPW ‘10), pp. 197–206. DOI: 10.1109/ICPPW.2010.37.
49.
NisbetAP (1998) GAPS: Iterative feedback directed parallelisation using genetic algorithms. In: Proceedings of the workshop on profile and feedback-directed compilation.
50.
ParkEPoucheLNCavazosJCohenASadayappanP (2011) Predictive modeling in a polyhedral optimization space. In: Proceedings of the international symposium on code generation and optimization.
51.
PearlJ (1989) Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference (Morgan Kaufmann Series in Representation and Reasoning). San Mateo, CA: Morgan Kaufmann.
52.
PouchetLNBastoulCCohenAVasilacheN (2007) Iterative optimization in the polyhedral model: Part I, one-dimensional time. In: Proceedings of the fifth international symposium on code generation and optimization (CGO’07), San Jose, CA.
53.
PouchetLNBastoulCCohenAVasilacheN (2008) Iterative optimization in the polyhedral model: Part II, multidimensional time. In: Proceedings of the ACM SIGPLAN conference on programming language design and implementation (PLDI’08), Tucson, AZ.
54.
PüschelMMouraJMFJohnsonJ. (2005) SPIRAL: Code generation for DSP transforms. Proceedings of the IEEE93(2): 232–275.
55.
PutermanML (2009) Markov decision processes: discrete stochastic dynamic programming ( Wiley Series in Probability and Statistics, vol. 414). New York: Wiley-Interscience.
56.
QasemAKennedyK (2006) Profitable loop fusion and tiling using model-driven empirical search. In: Proceedings of 2006 ACM international conference on supercomputing.
57.
QasemAKennedyK (2008) Model-guided empirical tuning of loop fusion. International Journal of High Performance Systems Architecture1(3): 183–198.
58.
RamalingamSHallMWChenC (2012) Improving high-performance sparse libraries using compiler-assisted specialization: A PETSc case study. In: Proceedings of the international parallel and distributed processing symposium workshops, pp. 487–496.
59.
RenMParkJYHoustonMAikenADallyWJ (2008) A Tuning Framework for Software-Managed Memory Hierarchies. In: International Conference on Parallel Architectures and Compilation Techniques, pp. 280–291.
60.
RiceJR (1976) The algorithm selection problem. Advances in Computers15: 65–118.
61.
RudyGChenCHallMWKhanMMChameJ (2010) A programming language interface to describe transformations and code generation. In: Proceedings of the 23nd international workshop on languages and compilers for parallel computing.
62.
SaltzJHAgrawalGChangC. (1997) Programming irregular applications: Runtime support, compilation and tools. Advances in Computers45: 105–153.
63.
SeymourKYouHDongarraJ (2008) A comparison of search heuristics for empirical code optimization. In: Proceedings of the 2008 IEEE international conference on cluster computing, pp. 421–429. DOI: 10.1109/CLUSTR.2008.4663803.
64.
ShendeSMalonyAD (2006) The tau parallel performance system. International Journal of High Performance Computing Applications20(2): 287–331.
65.
ShimijoFKaliaRKNakanoAVashishtaP (2008) Divide-and-conquer density functional theory on hierarchical real-space grids: Parallel implementation and applications. Physical Review B77: 085103.
66.
ShinJHallMWChameJChenCFischerPFHovlandPD (2010) Speeding up Nek5000 with autotuning and specialization. In: Proceedings of the 24th ACM international conference on supercomputing (ICS ‘10), pp. 253–262. DOI: 10.1145/1810085.1810120.
67.
StephensonMAmarasingheSMartinMO’ReillyUM (2003) Meta optimization: Improving compiler heuristics with machine learning. In: Proceedings of ACM SIGPLAN conference on programming language design and implementation.
68.
StroutMMCarterLFerranteJ (2001) Rescheduling for locality in sparse matrix computations. In: AlexandrovVNDongarraJTanCJK (eds.), Proceedings of the 2001 International Conference on Computational Science (Lecture Notes in Computer Science, vol. 2074). San Francisco, CA: Springer-Verlag.
69.
StroutMMCarterLFerranteJ (2003) Compile-time composition of run-time data and iteration reorderings. In: Proceedings of the 2003 ACM SIGPLAN conference on programming language design and implementation (PLDI).
70.
StroutMMGeorgeGOlschanowskyC (2012) Set and relation manipulation for the sparse polyhedral framework. In: Proceedings of the 25th international workshop on languages and compilers for parallel computing (LCPC).
71.
TangYChowdhuryRAKuszmaulBCLukCKLeisersonCE (2011) The Pochoir stencil compiler. In: Proceedings of the ACM symposium on parallelism in algorithms and architectures, pp. 117–128.
72.
TapusCChungIHHollingsworthJ (2002) Active harmony: Towards automated performance tuning. ACM/IEEE 2002 Conference on Supercomputing, p. 44. DOI: 10.1109/SC.2002.10062.
73.
ThomasNTanaseGTkachyshynOPerdueJAmatoNMRauchwergerL (2005) A framework for adaptive algorithm selection in STAPL. In: Proceedings of the tenth ACM SIGPLAN symposium on principles and practice of parallel programming (PPoPP ‘05). New York: ACM Press, pp. 277–288. DOI: 10.1145/1065944.1065981.
74.
TiwariAChenCChameJHallMHollingsworthJK (2009) A scalable auto-tuning framework for compiler optimization. In: Proceedings of international parallel and distributed processing symposium.
75.
TiwariAHollingsworthJK (2011) Online adaptive code generation and tuning. In: Proceedings of the international conference and parallel and distributed processing systems.
76.
TiwariAHollingsworthJKChenC. (2011) Auto-tuning full applications: A case study. International Journal of High Performance Computing Applications25: 286–294.
77.
VoronenkoYde MesmayFPüschelM (2009) Computer generation of general size linear transform libraries. In: Proceedings of the international symposium on code generation and optimization (CGO), Seattle, WA.
78.
VossMJEigenmannR (2001) High-level adaptive program optimization with ADAPT. In: ACM SIGPLAN symposium on principles and practice of parallel programming.
79.
VuducRDemmelJWBilmesJA (2004) Statistical models for empirical search-based performance tuning. International Journal of High Performance Computing Applications18(1): 65–94. DOI: 10.1177/1094342004041293.
80.
VuducRDemmelJWYelickKA (2005) OSKI: A library of automatically tuned sparse matrix kernels. Journal of Physics: Conference Series16(1): 521–530.
81.
WhaleyRCWhalleyDB (2005) Tuning high performance kernels through empirical compilation. In: Proceedings of the international conference on parallel processing.
82.
WilliamsSKalamkarDDSinghA. (2012) Optimization of geometric multigrid for emerging multi- and manycore processors. In: Proceedings of supercomputing ‘12, p. 96.
83.
WilliamsSWatermanAPattersonD (2009) Roofline: An insightful visual performance model for floating-point programs and multicore architectures. Communications of the ACM52(4): 65–76.
84.
WolfeM (1986) Loops skewing: The wavefront method revisited. International Journal of Parallel Programming15(4): 279–293.
85.
YiQ (2011) POET: A scripting language for applying parameterized source-to-source program transformations. Software: Practice and Experience42: 649–777. DOI: 10.1002/spe.1089.
86.
YiQSeymourKYouHVuducRQuinlanD (2007) POET: Parameterized optimizations for empirical tuning. In: Proceedings of the workshop on performance optimization of high-level languages and libraries (POHLL).
87.
ZhangYMuellerF (2012) Auto-generation and auto-tuning of 3d stencil codes on GPU clusters. In: Proceedings of the tenth international symposium on code generation and optimization (CGO ‘12).
