Today’s Agenda
I 08:30 Welcome and broader context (Saman Amarasinghe)
I 08:40 Introduction to OpenTuner (Jason Ansel)
I 09:10 Search techniques (Kalyan Veeramachaneni)
I 09:35 In depth example (Jeffrey Bosboom)
I 10:00 BreakI 10:15 Applications

Halide (Jonathan Ragan-Kelley)
SEJITS (Chick Markley)
I JVM optimization (Tharindu Rusira)I
I

I 11:00 Hands on session (Shoaib Kamil)
I 11:45 Discussion

1 / 41

Introduction to OpenTuner
Jason Ansel
MIT - CSAIL

Febuary 8, 2015

2 / 41Raytracer Example
An example ray tracer program: raytracer.cpp

3 / 41Raytracer Example
An example ray tracer program: raytracer.cpp$ g++ −O3 −o r a y t r a c e r a r a y t r a c e r . cpp$ time ./ r a y t r a c e r a./ raytracer a
0 . 1 7 s u s e r 0 . 0 0 s s y s t e m 99% cpu 0 . 1 7 5 t o t a l

3 / 41Raytracer Example
An example ray tracer program: raytracer.cpp$ g++ −O3 −o r a y t r a c e r a r a y t r a c e r . cpp$ time ./ r a y t r a c e r a./ raytracer a
0 . 1 7 s u s e r 0 . 0 0 s s y s t e m 99% cpu 0 . 1 7 5 t o t a l

1.47x speedup with:$ g++ −O3 −o r a y t r a c e r b a p p s / r a y t r a c e r . cpp −f u n s a f e −math−o p t i m i z a t i o n s −f w r a p v,→ −f n o−e x p e n s i v e −o p t i m i z a t i o n s −−param=max−p e e l −b r a n c h e s =115 −fweb −f n o−,→ cx−f o r t r a n −r u l e s −−param=max−i n l i n e −r e c u r s i v e −d e p t h =25 −f n o−b t r−bb−,→ e x c l u s i v e −f n o−t r e e −ch −−param=i v −max−c o n s i d e r e d −u s e s =69 −f g c s e −l a s −,→ f t r e e −l o o p−d i s t r i b u t i o n −−param=max−goto−d u p l i c a t i o n −i n s n s =11 −−param=,→ max−h o i s t −d e p t h =44 −f s c h e d −s t a l l e d −i n s n s −dep −−param=max−once−p e e l e d −,→ i n s n s =165 −−param=max−p i p e l i n e −r e g i o n −i n s n s =316 −−param=i v −c o n s i d e r −a l l,→ −c a n d i d a t e s −bound=75$ time ./ r a y t r a c e r b./ raytracer b
0 . 1 2 s u s e r 0 . 0 0 s s y s t e m 99% cpu 0 . 1 1 9 t o t a l

3 / 41

iv-consider-all-candidates-bound what???
This command is brittle and confusing:$ g++ −O3 −o r a y t r a c e r b a p p s / r a y t r a c e r . cpp −f u n s a f e −math−o p t i m i z a t i o n s −f w r a p v,→ −f n o−e x p e n s i v e −o p t i m i z a t i o n s −−param=max−p e e l −b r a n c h e s =115 −fweb −f n o−,→ cx−f o r t r a n −r u l e s −−param=max−i n l i n e −r e c u r s i v e −d e p t h =25 −f n o−b t r−bb−,→ e x c l u s i v e −f n o−t r e e −ch −−param=i v −max−c o n s i d e r e d −u s e s =69 −f g c s e −l a s −,→ f t r e e −l o o p−d i s t r i b u t i o n −−param=max−goto−d u p l i c a t i o n −i n s n s =11 −−param=,→ max−h o i s t −d e p t h =44 −f s c h e d −s t a l l e d −i n s n s −dep −−param=max−once−p e e l e d −,→ i n s n s =165 −−param=max−p i p e l i n e −r e g i o n −i n s n s =316 −−param=i v −c o n s i d e r −a l l,→ −c a n d i d a t e s −bound=75

4 / 41

iv-consider-all-candidates-bound what???
This command is brittle and confusing:$ g++ −O3 −o r a y t r a c e r b a p p s / r a y t r a c e r . cpp −f u n s a f e −math−o p t i m i z a t i o n s −f w r a p v,→ −f n o−e x p e n s i v e −o p t i m i z a t i o n s −−param=max−p e e l −b r a n c h e s =115 −fweb −f n o−,→ cx−f o r t r a n −r u l e s −−param=max−i n l i n e −r e c u r s i v e −d e p t h =25 −f n o−b t r−bb−,→ e x c l u s i v e −f n o−t r e e −ch −−param=i v −max−c o n s i d e r e d −u s e s =69 −f g c s e −l a s −,→ f t r e e −l o o p−d i s t r i b u t i o n −−param=max−goto−d u p l i c a t i o n −i n s n s =11 −−param=,→ max−h o i s t −d e p t h =44 −f s c h e d −s t a l l e d −i n s n s −dep −−param=max−once−p e e l e d −,→ i n s n s =165 −−param=max−p i p e l i n e −r e g i o n −i n s n s =316 −−param=i v −c o n s i d e r −a l l,→ −c a n d i d a t e s −bound=75

I Specific to:I

raytracer.cpp
I

I
I

Same flags are 1.42x slower than -O1 for fft.c

GCC 4.8.2-19ubuntu1
Intel Core i7-4770S

4 / 41

iv-consider-all-candidates-bound what???
This command is brittle and confusing:$ g++ −O3 −o r a y t r a c e r b a p p s / r a y t r a c e r . cpp −f u n s a f e −math−o p t i m i z a t i o n s −f w r a p v,→ −f n o−e x p e n s i v e −o p t i m i z a t i o n s −−param=max−p e e l −b r a n c h e s =115 −fweb −f n o−,→ cx−f o r t r a n −r u l e s −−param=max−i n l i n e −r e c u r s i v e −d e p t h =25 −f n o−b t r−bb−,→ e x c l u s i v e −f n o−t r e e −ch −−param=i v −max−c o n s i d e r e d −u s e s =69 −f g c s e −l a s −,→ f t r e e −l o o p−d i s t r i b u t i o n −−param=max−goto−d u p l i c a t i o n −i n s n s =11 −−param=,→ max−h o i s t −d e p t h =44 −f s c h e d −s t a l l e d −i n s n s −dep −−param=max−once−p e e l e d −,→ i n s n s =165 −−param=max−p i p e l i n e −r e g i o n −i n s n s =316 −−param=i v −c o n s i d e r −a l l,→ −c a n d i d a t e s −bound=75

I Specific to:I

raytracer.cpp
I

I
I

Same flags are 1.42x slower than -O1 for fft.c

GCC 4.8.2-19ubuntu1
Intel Core i7-4770S

I Autotuners can help!

4 / 41

How to Autotune a Program

Program

5 / 41

How to Autotune a Program

Program
Search Space
Definition

Executes

Run Method

5 / 41

How to Autotune a Program

ProgramAutotuner

Program
Search Space
Definition
Configuration
Executes

Run Method

Measurement

MachineLearning
SearchTechnique(s)5 / 41

How to Autotune a Program

ProgramAutotuner

Program
Search Space
Definition
Configuration
Executes

Run Method

Measurement

MachineLearning
SearchTechnique(s)Optimized
Configuration

5 / 41

OpenTunerI OpenTuner is an general framework for program autotuning
I
I

Extensible configuration representation
Uses ensembles of techniques to provide robustness to different
search spaces

6 / 41

OpenTunerI OpenTuner is an general framework for program autotuning
I
I

Extensible configuration representation
Uses ensembles of techniques to provide robustness to different
search spaces

I As an example, lets implement a GCC flags autotuner with

OpenTuner(1)

Search Space
Definition(2)
Run Method

6 / 41

Define the Search Space with OpenTuner
I Optimization level: O0,

O1, O2, O3

manipulator = ConfigurationManipulator ()m a n i p u l a t o r . add parameter ( IntegerParameter ( ’ o p t l e v e l ’ , 0 , 3) )7 / 41

Define the Search Space with OpenTuner
I Optimization level: O0,

O1, O2, O3

manipulator = ConfigurationManipulator ()m a n i p u l a t o r . add parameter ( IntegerParameter ( ’ o p t l e v e l ’ , 0 , 3) )I On/off flags, eg: ’-falign-functions’ vs’-fno-align-functions’
GCC FLAGS = [’ a l i g n −f u n c t i o n s ’ , ’ a l i g n −jumps ’ , ’ a l i g n −l a b e l s ’ ,’ b r a n c h−co un t−r e g ’ , ’ b r a n c h−p r o b a b i l i t i e s ’ ,# . . . (176 t o t a l )]f o r f l a g i n GCC FLAGS :m a n i p u l a t o r . a d d p a r a m e t e r ( EnumParameter ( f l a g , [ ’ on ’ , ’ o f f ’ , ’ d e f a u l t ’ ] ) )7 / 41

Define the Search Space with OpenTuner
I Optimization level: O0,

O1, O2, O3

manipulator = ConfigurationManipulator ()m a n i p u l a t o r . add parameter ( IntegerParameter ( ’ o p t l e v e l ’ , 0 , 3) )I On/off flags, eg: ’-falign-functions’ vs’-fno-align-functions’
GCC FLAGS = [’ a l i g n −f u n c t i o n s ’ , ’ a l i g n −jumps ’ , ’ a l i g n −l a b e l s ’ ,’ b r a n c h−co un t−r e g ’ , ’ b r a n c h−p r o b a b i l i t i e s ’ ,# . . . (176 t o t a l )]f o r f l a g i n GCC FLAGS :m a n i p u l a t o r . a d d p a r a m e t e r ( EnumParameter ( f l a g , [ ’ on ’ , ’ o f f ’ , ’ d e f a u l t ’ ] ) )I Parameters, eg: ’--param

early-inlining-insns=512’# ( name , min , max )GCC PARAMS = [( ’ e a r l y −i n l i n i n g −i n s n s ’ , 0 , 1 0 0 0 ) ,( ’ g c s e−c o s t−d i s t a n c e −r a t i o ’ , 0 , 1 0 0 ) ,# . . . (145 t o t a l )]f o r param , m i n v a l , m a x v a l i n GCC PARAMS :m a n i p u l a t o r . a d d p a r a m e t e r ( I n t e g e r P a r a m e t e r ( param , m i n v a l , m a x v a l ) )7 / 41

Defining the Run Function
I Optimization level: O0,

O1, O2, O3

def run ( s e l f , d e s i r e d r e s u l t , program input , l i m i t ) :cfg = d e s i r e d r e s u l t . c o n f i g u r a t i o n . data
gcc cmd = ’ g++ r a y t r a c e r . cpp −o . / tmp . b i n ’
gcc cmd += ’ −O{0} ’ . f o r m a t ( c f g [ ’ o p t l e v e l ’ ] )8 / 41

Defining the Run Function
I Optimization level: O0,

O1, O2, O3

def run ( s e l f , d e s i r e d r e s u l t , program input , l i m i t ) :cfg = d e s i r e d r e s u l t . c o n f i g u r a t i o n . data
gcc cmd = ’ g++ r a y t r a c e r . cpp −o . / tmp . b i n ’
gcc cmd += ’ −O{0} ’ . f o r m a t ( c f g [ ’ o p t l e v e l ’ ] )I On/off flags:
f o r f l a g i n GCC FLAGS :i f c f g [ f l a g ] == ’ on ’ :gcc cmd += ’ −f {0} ’ . f o r m a t ( f l a g )e l i f c f g [ f l a g ] == ’ o f f ’ :gcc cmd += ’ −f n o −{0} ’ . f o r m a t ( f l a g )I Parameters:
f o r param , m i n v a l u e , m a x v a l u e i n GCC PARAMS :gcc cmd += ’ −−param {0}={1} ’ . f o r m a t ( param , c f g [ param ] )8 / 41

Defining the Run Function
I Optimization level: O0,

O1, O2, O3

def run ( s e l f , d e s i r e d r e s u l t , program input , l i m i t ) :cfg = d e s i r e d r e s u l t . c o n f i g u r a t i o n . data
gcc cmd = ’ g++ r a y t r a c e r . cpp −o . / tmp . b i n ’
gcc cmd += ’ −O{0} ’ . f o r m a t ( c f g [ ’ o p t l e v e l ’ ] )I On/off flags:
f o r f l a g i n GCC FLAGS :i f c f g [ f l a g ] == ’ on ’ :gcc cmd += ’ −f {0} ’ . f o r m a t ( f l a g )e l i f c f g [ f l a g ] == ’ o f f ’ :gcc cmd += ’ −f n o −{0} ’ . f o r m a t ( f l a g )I Parameters:
f o r param , m i n v a l u e , m a x v a l u e i n GCC PARAMS :gcc cmd += ’ −−param {0}={1} ’ . f o r m a t ( param , c f g [ param ] )I Measure how well it performs:
c o m p i l e r e s u l t = s e l f . c a l l p r o g r a m ( gcc cmd )r u n r e s u l t = s e l f . c a l l p r o g r a m ( ’ . / tmp . b i n ’ )r e t u r n R e s u l t ( t i m e=r u n r e s u l t [ ’ t i m e ’ ] )8 / 41

OpenTuner Results for GCC Flags

Execution Time (seconds)

0.75

g++ -O1
g++ -O2
g++ -O3OpenTuner

0.7
0.65
0.6
0.55
0.5
0.45
0.4
0

300

600
900
1200
1500
Autotuning Time (seconds)

1800

Autotune GCC flags for Ray Tracer. Median of 30 runs, error bars
are 20th and 80th percentiles.
9 / 41

OpenTuner Results for GCC Flags

Execution Time (seconds)

0.6

g++ -O1
g++ -O2
g++ -O3OpenTuner

0.55
0.5
0.45
0.4
0

300

600
900
1200
1500
Autotuning Time (seconds)

1800

Autotune GCC flags for TSP GA. Median of 30 runs, error bars are
20th and 80th percentiles.
10 / 41

OpenTuner Results for GCC Flags

Execution Time (seconds)

1

gcc -O1
gcc -O2
gcc -O3OpenTuner

0.95
0.9
0.85
0.8
0

300

600
900
1200
1500
Autotuning Time (seconds)

1800

Autotune GCC flags for FFT. Median of 30 runs, error bars are
20th and 80th percentiles.
11 / 41

OpenTuner Results for GCC Flags

Execution Time (seconds)

0.3

g++ -O1
g++ -O2
g++ -O3OpenTuner

0.25
0.2
0.15
0.1
0

300

600
900
1200
1500
Autotuning Time (seconds)

1800

Autotune GCC flags for Matrix Multiply. Median of 30 runs, error
bars are 20th and 80th percentiles.
12 / 41

Related Projects
A small selection of many related projects:
Package
ATLAS
Code Perforation
FFTW
OSKI
Periscope
Active Harmony
PATUS
Sepya
Dynamic Knobs
Milepost GCC / cTuning
SEEC / Heartbeats
InsiemePetaBricks
SPIRAL

DomainDense Linear Algebra
Compiler
Fast Fourier Transform
Sparse Linear Algebra
HPC
Runtime System
Stencil Computations
Stencil Computations
Runtime System
Compiler
Runtime System
Compiler
Programming Language
DSP Algorithms

Search Method
Exhaustive
Exhaustive + Simulated Annealing
Exhaustive / Dynamic Prog.
Exhaustive + Heuristic
Exhaustive + Nelder-Mead
Nelder-Mead
Nelder-Mead or Evolutionary
Random-Restart Gradient AscentControl Theory
IID Model + Central DB
Control Theory
Differential Evolution
Bottom-up Evolutionary
Pareto Active Learning

13 / 41

Related Projects
A small selection of many related projects:
Package
ATLAS
Code Perforation
FFTW
OSKI
Periscope
Active Harmony
PATUS
Sepya
Dynamic Knobs
Milepost GCC / cTuning
SEEC / Heartbeats
InsiemePetaBricks
SPIRAL

DomainDense Linear Algebra
Compiler
Fast Fourier Transform
Sparse Linear Algebra
HPC
Runtime System
Stencil Computations
Stencil Computations
Runtime System
Compiler
Runtime System
Compiler
Programming Language
DSP Algorithms

Search Method
Exhaustive
Exhaustive + Simulated Annealing
Exhaustive / Dynamic Prog.
Exhaustive + Heuristic
Exhaustive + Nelder-Mead
Nelder-Mead
Nelder-Mead or Evolutionary
Random-Restart Gradient AscentControl Theory
IID Model + Central DB
Control Theory
Differential Evolution
Bottom-up Evolutionary
Pareto Active Learning

I Simple techniques (exhaustive, hill climbers, etc) are popularI

No single technique is best for all problems

I Representations are often just integers/floats/booleans
13 / 41

Limits of Current Approaches

I We believe simple techniques limit the scope and efficiency ofautotuning
I A hill climber works great for a block size, but fails for more

complex applications
I Many users of autotuning work hard to prune their search

spaces to fit techniques such as exhaustive search

14 / 41

Limits of Current Approaches

I We believe simple techniques limit the scope and efficiency ofautotuning
I A hill climber works great for a block size, but fails for more

complex applications
I Many users of autotuning work hard to prune their search

spaces to fit techniques such as exhaustive search
I Real problems have large search spaces

14 / 41

Over 10806 Combinations of GCC Optimizations
g++ apps/raytracer.cpp -o ./raytracer c -O3 -fno-align-functions -fno-align-loops -fasynchronous-unwind-tables -fbranch-count-reg -fbranch-probabilities-fno-branch-target-load-optimize -fbtr-bb-exclusive -fno-combine-stack-adjustments -fno-common -fcompare-elim -fcrossjumping -fcse-follow-jumps-fcx-fortran-rules -fcx-limited-range -fdata-sections -fno-dce -fdelete-null-pointer-checks -fno-devirtualize -fno-dse -fearly-inlining -fexceptions-ffinite-math-only -fforward-propagate -fgcse -fgcse-after-reload -fno-gcse-las -fno-graphite-identity -fno-if-conversion2 -fno-inline-functions-fno-inline-small-functions -fno-ipa-cp -fno-ipa-matrix-reorg -fno-ipa-profile -fno-ipa-pta -fipa-pure-const -fipa-reference -fno-ipa-sra -fno-ivopts-fno-loop-block -fno-loop-flatten -floop-interchange -fno-loop-parallelize-all -floop-strip-mine -fmath-errno -fno-merge-all-constants -fno-modulo-sched-fno-non-call-exceptions -fno-optimize-sibling-calls -fno-optimize-strlen -fpeel-loops -fpeephole -fno-peephole2 -fno-predictive-commoning-fno-prefetch-loop-arrays -fno-reg-struct-return -fno-regmove -frename-registers -fno-reorder-blocks -freorder-blocks-and-partition -freorder-functions-fno-rerun-cse-after-loop -fno-rounding-math -fno-rtti -fno-sched-critical-path-heuristic -fno-sched-dep-count-heuristic -fno-sched-group-heuristic-fno-sched-interblock -fno-sched-pressure -fsched-rank-heuristic -fsched-spec-insn-heuristic -fsched-spec-load -fno-sched-stalled-insns -fsched-stalled-insns-dep-fno-sched2-use-superblocks -fno-schedule-insns -fschedule-insns2 -fno-sel-sched-pipelining -fno-sel-sched-pipelining-outer-loops -fsel-sched-reschedule-pipelined-fno-short-wchar -fno-shrink-wrap -fsignaling-nans -fsingle-precision-constant -fno-split-ivs-in-unroller -fstrict-enums -fno-thread-jumps-ftrapping-math -fno-trapv -fno-tree-builtin-call-dce -fno-tree-ccp -fno-tree-copy-prop -ftree-copyrename -fno-tree-cselim -fno-tree-dce -ftree-dse-fno-tree-forwprop -ftree-fre -ftree-loop-distribute-patterns -fno-tree-loop-distribution -ftree-loop-if-convert -fno-tree-loop-if-convert-stores-fno-tree-loop-ivcanon -ftree-pta -fno-tree-reassoc -fno-tree-scev-cprop -fno-tree-slp-vectorize -ftree-sra -ftree-switch-conversion -fno-tree-ter-fno-tree-vectorize -ftree-vrp -fno-unit-at-a-time -fno-unroll-all-loops -fno-unroll-loops -funsafe-loop-optimizations -funwind-tables -fno-var-tracking-fvar-tracking-assignments-toggle -fno-var-tracking-uninit -fno-vect-cost-model -fno-vpt -fweb -fwhole-program -fwrapv --param=align-loop-iterations=16--param=align-threshold=28 --param=allow-load-data-races=1 --param=allow-packed-load-data-races=1 --param=allow-packed-store-data-races=0--param=allow-store-data-races=1 --param=case-values-threshold=3 --param=comdat-sharing-probability=14 --param=cxx-max-namespaces-for-diagnostic-help=1008--param=early-inlining-insns=19 --param=gcse-after-reload-critical-fraction=15 --param=gcse-after-reload-partial-fraction=10 --param=gcse-cost-distance-ratio=14--param=gcse-unrestricted-cost=5 --param=ggc-min-expand=66 --param=ggc-min-heapsize=15449 --param=graphite-max-bbs-per-function=248 --param=graphite-max-nb-scop-params=10--param=hot-bb-count-ws-permille=271 --param=hot-bb-frequency-fraction=2357 --param=inline-min-speedup=36 --param=inline-unit-growth=26 --param=integer-share-limit=511--param=ipa-cp-eval-threshold=222 --param=ipa-cp-loop-hint-bonus=18 --param=ipa-cp-value-list-size=18 --param=ipa-max-agg-items=13 --param=ipa-sra-ptr-growth-factor=6--param=ipcp-unit-growth=3 --param=ira-loop-reserved-regs=8 --param=ira-max-conflict-table-size=261 --param=ira-max-loops-num=25 --param=iv-always-prune-cand-set-bound=17--param=iv-consider-all-candidates-bound=26 --param=iv-max-considered-uses=85 --param=l1-cache-line-size=128 --param=l1-cache-size=24 --param=l2-cache-size=356--param=large-function-growth=237 --param=large-function-insns=4444 --param=large-stack-frame=431 --param=large-stack-frame-growth=250 --param=large-unit-insns=2520--param=lim-expensive=10 --param=loop-block-tile-size=40 --param=loop-invariant-max-bbs-in-loop=2500 --param=loop-max-datarefs-for-datadeps=816--param=lto-min-partition=261 --param=lto-partitions=96 --param=max-average-unrolled-insns=22 --param=max-completely-peel-loop-nest-depth=18--param=max-completely-peel-times=31 --param=max-completely-peeled-insns=325 --param=max-crossjump-edges=30 --param=max-cse-insns=251 --param=max-cse-path-length=8--param=max-cselib-memory-locations=1202 --param=max-delay-slot-insn-search=137 --param=max-delay-slot-live-search=84 --param=max-dse-active-local-stores=1250--param=max-early-inliner-iterations=2 --param=max-fields-for-field-sensitive=0 --param=max-gcse-insertion-ratio=50 --param=max-gcse-memory=13107200--param=max-goto-duplication-insns=15 --param=max-grow-copy-bb-insns=23 --param=max-hoist-depth=101 --param=max-inline-insns-auto=43 --param=max-inline-insns-recursive=126--param=max-inline-insns-recursive-auto=135 --param=max-inline-insns-single=421 --param=max-inline-recursive-depth=24 --param=max-inline-recursive-depth-auto=28--param=max-iterations-computation-cost=24 --param=max-iterations-to-track=253 --param=max-jump-thread-duplication-stmts=21 --param=max-last-value-rtl=2794--param=max-modulo-backtrack-attempts=14 --param=max-once-peeled-insns=105 --param=max-partial-antic-length=25 --param=max-peel-branches=84--param=max-peel-times=23 --param=max-peeled-insns=25 --param=max-pending-list-length=10 --param=max-pipeline-region-blocks=44 --param=max-pipeline-region-insns=578--param=max-predicted-iterations=28 --param=max-reload-search-insns=356 --param=max-sched-extend-regions-iters=1 --param=max-sched-insn-conflict-delay=1--param=max-sched-ready-insns=101 --param=max-sched-region-blocks=15 --param=max-sched-region-insns=36 --param=max-slsr-cand-scan=12 --param=max-stores-to-sink=2--param=max-tail-merge-comparisons=24 --param=max-tail-merge-iterations=1 --param=max-tracked-strlens=351 --param=max-unroll-times=26 --param=max-unrolled-insns=570--param=max-unswitch-insns=17 --param=max-unswitch-level=11 --param=max-variable-expansions-in-unroller=0 --param=max-vartrack-expr-depth=14--param=max-vartrack-reverse-op-size=15 --param=max-vartrack-size=12500164 --param=min-crossjump-insns=18 --param=min-inline-recursive-probability=9--param=min-insn-to-prefetch-ratio=23 --param=min-spec-prob=15 --param=min-vect-loop-bound=2 --param=omega-eliminate-redundant-constraints=0--param=omega-hash-table-size=138 --param=omega-max-eqs=43 --param=omega-max-geqs=68 --param=omega-max-keys=378 --param=omega-max-vars=32--param=omega-max-wild-cards=55 --param=partial-inlining-entry-probability=68 --param=predictable-branch-outcome=0 --param=prefetch-latency=115--param=prefetch-min-insn-to-mem-ratio=2 --param=sccvn-max-alias-queries-per-access=2543 --param=sccvn-max-scc-size=2504 --param=scev-max-expr-complexity=32--param=scev-max-expr-size=45 --param=sched-mem-true-dep-cost=0 --param=sched-pressure-algorithm=1 --param=sched-spec-prob-cutoff=79 --param=sched-state-edge-prob-cutoff=2--param=selsched-insns-to-rename=6 --param=selsched-max-lookahead=14 --param=selsched-max-sched-times=1 --param=simultaneous-prefetches=9--param=sink-frequency-threshold=53 --param=slp-max-insns-in-bb=279 --param=sms-dfa-history=3 --param=sms-loop-average-count-threshold=2--param=sms-max-ii-factor=35 --param=sms-min-sc=3 --param=ssp-buffer-size=13 --param=switch-conversion-max-branch-ratio=2 --param=tm-max-aggregate-size=32--param=tracer-dynamic-coverage=66 --param=tracer-dynamic-coverage-feedback=46 --param=tracer-max-code-growth=200 --param=tracer-min-branch-probability=82--param=tracer-min-branch-probability-feedback=70 --param=tracer-min-branch-ratio=21 --param=tree-reassoc-width=2 --param=uninit-control-dep-attempts=415--param=use-canonical-types=0 --param=vect-max-version-for-alias-checks=11 --param=vect-max-version-for-alignment-checks=23

15 / 41

Large Search Spaces are a Challenge
Project

BenchmarkPossible Configurations

GCC/G++ Flags
HalideHalideHalideHPL
PetaBricks
PetaBricks
PetaBricks
PetaBricks
Stencil
Unitary
Mario

all
Blur
WaveletBilateraln/aPoisson
Sort
Strassen
TriSolve
all
n/a
n/a

10806
1025
1032
10176
109.9
1036571090
10188
101559106.5
1021
10632816 / 41

OpenTuner’s General Representation

I Large search spaces do not mean haphazard ones
I Choosing the right representation is critical
I OpenTuner allows programmers to easily express structured

search spaces
Supports complex parameter types such as permutations,schedules, mappings
I User defined parameter types
I

17 / 41

OpenTuner Model

Results

Meta
Technique

Configuration
Manipulator

TechniqueTechniqueTechniqueParameter
Parameter
Parameter

Configuration
Configuration
Configuration
Data
Data
Data

Measurement
Run Method

Objective

18 / 41

OpenTuner Configuration Manipulator Parameters
Parameter
Primitive
Integer

Float

LogInteger

Complex
ScaledNumeric Boolean Switch Enum Permutation

LogFloat

PowerOfTwo

Selector

Schedule

I Hierarchical structure of parameters, user defined parametertypes can be added at any point
I Primitive parameters behave like bounded integers or floats
I Complex parameters have a set of stochastic mutation

operators
I Technique-specific operators

19 / 41

Ensembles of Techniques

I OpenTuner contains many techniques such as:

Differential Evolution
Genetic Algorithms
I Greedy Mutation
I Multi-armed Bandit
I Nelder MeadI Partial Swarm Optimization
I Pattern Search
I Pseudo Annealing
I Torczon
I
I

I Uses ensembles of techniques to provide robustness todifferent search spaces

20 / 41

Ensembles of Techniques in OpenTuner

Differential
Evolution

Particle
Swarm
Optimization

Torczon
Hill
Climber

21 / 41

Ensembles of Techniques in OpenTuner
Information sharing through ResultsDB

Differential
Evolution

Particle
Swarm
Optimization

Torczon
Hill
Climber

21 / 41

Ensembles of Techniques in OpenTuner
Information sharing through ResultsDB

Differential
Evolution

Particle
Swarm
Optimization

Torczon
Hill
Climber

AUC Bandit

21 / 41

Ensembles of Techniques in OpenTuner
Information sharing through ResultsDB

Differential
Evolution

Particle
Swarm
Optimization

Torczon
Hill
Climber?
AUC Bandit

Which configuration should we try next?

21 / 41

Ensembles of Techniques in OpenTuner
Information sharing through ResultsDB

Differential
Evolution
33%

Particle
Swarm
Optimization
33%

Torczon
Hill
Climber
33%

Exploration
AUC Bandit

Which configuration should we try next?

21 / 41

Ensembles of Techniques in OpenTuner
Information sharing through ResultsDB

Differential
Evolution
100%

Particle
Swarm
Optimization
0%Torczon
Hill
Climber0%

Exploitation
AUC Bandit

Which configuration should we try next?

21 / 41

AUC Bandit1

I |H| is the length of the sliding history window
I Ht is the number of times the technique has been used in that

history window,
I C is a constant controlling the exploration/exploitation

trade-off
I AUC t is the credit assignment term

1

Based on strategy in Fialho PPSN’10
22 / 41

AUC Bandit1
Exploitation

Exploration

I |H| is the length of the sliding history window
I Ht is the number of times the technique has been used in that

history window,
I C is a constant controlling the exploration/exploitation

trade-off
I AUC t is the credit assignment term

1

Based on strategy in Fialho PPSN’10
22 / 41

OpenTuner System Overview
SearchSearchDriverMeasurement
Measurement
Driver

SearchTechniques

User Defined
Measurement
Function

Configuration
Manipulator
Reads: Results
Writes: Desired Results

Reads: Desired Results
Writes: Results

Results Database

23 / 41

Conclusions
I A lot of performance is left on thefloor due to poorly optimized
programs
I OpenTuner makes state of the art
machine learning accessible to all
Extensible configuration
representation
I Ensembles of techniques
I

I Conventional wisdom

http://opentuner.org/

underestimates the size tractablesearch spaces
I However, choosing the right

representation is critical tosuccessful autouners
24 / 41

Today’s Agenda
I 08:30 Welcome and broader context (Saman Amarasinghe)
I 08:40 Introduction to OpenTuner (Jason Ansel)
I 09:10 Search techniques (Kalyan Veeramachaneni)
I 09:35 In depth example (Jeffrey Bosboom)
I 10:00 BreakI 10:15 Applications

Halide (Jonathan Ragan-Kelley)
SEJITS (Chick Markley)
I JVM optimization (Tharindu Rusira)I
I

I 11:00 Hands on session (Shoaib Kamil)
I 11:45 Discussion

25 / 41

Backup Slides: Mario

26 / 41

OpenTuner Can Play Super Mario Bros!

(Video 2 )2

http://youtu.be/pTi_tHpj6Ow
27 / 41

OpenTuner Can Play Super Mario Bros!

I Only feedback is number of pixels moved to the rightIe.g. approximately 1500 pixels for first pit

I OpenTuner doesn’t see the screen
I Super Mario Bros is deterministic, single run suffices

28 / 41

Naive Representation3

http://youtu.be/nyYdq1jJQrw
29 / 41

Naive Representation

I Bad, because most configurations make no sense.
I Just mashing random buttons.
I Doesn’t work at all (Video 3 ).

3http://youtu.be/nyYdq1jJQrw
29 / 41

Better Representation

I Movements (list):
I
I

Direction (left, right, run left, or run right)
Duration (frames)

30 / 41

Better Representation

I Movements (list):
I
I

Direction (left, right, run left, or run right)
Duration (frames)

I Jumps (list):
I
I

Start frame
Duration (frames)

30 / 41

Better Representation

I Movements (list):
I
I

Direction (left, right, run left, or run right)
Duration (frames)

I Jumps (list):
I
I

Start frame
Duration (frames)

Choosing the right representation is critical
I Search space size 106328
I Winning run found in 13641 (≈ 104 ) attempts
I Under 5 minutes of training time

30 / 41

Super Mario Bros Results

Pixels Moved Right (Progress)

3500
3000
2500
2000
1500
1000

Win Level
OpenTuner
0

60

120
180
240
Autotuning Time (seconds)

300

31 / 41

A Final Video 4

I OpenTuner learning to play Super

Mario Bros
I Every run that achieves a highscore
I Runs that don’t make

improvements are skipped
I Run # in top left caption

http://opentuner.org/
pip install opentuner
Try OpenTuner today!

I Thanks!

4

http://youtu.be/O5IK9f2nBsE
32 / 41

Backup Slides: Halide

33 / 41

OpenTuner Generating Halide Schedules

I A domain specific language for image

processing and photography
I Used for camera pipeline in Google Glass,

HDR+ in Android, some filters in
Photoshop
I Separate algorithm language andscheduling language
I We use OpenTuner to generate thescheduling language

34 / 41

Simple Halide Example
Algorithm:
ImageParam i n p u t ( UInt ( 1 6 ) , 2 ) ;Func a ( ” a ” ) , a ( ”b” ) , a ( ” c ” ) ;Var x ( ” x ” ) , y ( ” y ” ) ;a(x , y) = input (x , y) ;b(x , y) = a(x , y) ;c(x , y) = b(x , y) ;35 / 41

Simple Halide Example
Algorithm:

OpenTuner Generated Schedule:

ImageParam i n p u t ( UInt ( 1 6 ) , 2 ) ;Func a ( ” a ” ) , a ( ”b” ) , a ( ” c ” ) ;Var x ( ” x ” ) , y ( ” y ” ) ;Var x0 , y1 , x2 , x4 , y5 ;a . s p l i t ( x , x , x0 , 4 ). s p l i t ( y , y , y1 , 1 6 ). r e o r d e r ( y1 , x0 , y , x ). v e c t o r i z e ( y1 , 4 ). compute at ( b , y ) ;b . s p l i t ( x , x , x2 , 6 4 ). r e o r d e r ( x2 , x , y ). reorder storage (y , x)
. v e c t o r i z e ( x2 , 8 ). compute at ( c , x4 ) ;c . s p l i t ( x , x , x4 , 8 ). s p l i t ( y , y , y5 , 2 ). r e o r d e r ( x4 , y5 , y , x ). parallel (x). compute root ( ) ;a(x , y) = input (x , y) ;b(x , y) = a(x , y) ;c(x , y) = b(x , y) ;35 / 41

Simple Halide Example
Algorithm:

OpenTuner Generated Schedule:

ImageParam i n p u t ( UInt ( 1 6 ) , 2 ) ;Func a ( ” a ” ) , a ( ”b” ) , a ( ” c ” ) ;Var x ( ” x ” ) , y ( ” y ” ) ;Var x0 , y1 , x2 , x4 , y5 ;a . s p l i t ( x , x , x0 , 4 ). s p l i t ( y , y , y1 , 1 6 ). r e o r d e r ( y1 , x0 , y , x ). v e c t o r i z e ( y1 , 4 ). compute at ( b , y ) ;b . s p l i t ( x , x , x2 , 6 4 ). r e o r d e r ( x2 , x , y ). reorder storage (y , x)
. v e c t o r i z e ( x2 , 8 ). compute at ( c , x4 ) ;c . s p l i t ( x , x , x4 , 8 ). s p l i t ( y , y , y5 , 2 ). r e o r d e r ( x4 , y5 , y , x ). parallel (x). compute root ( ) ;a(x , y) = input (x , y) ;b(x , y) = a(x , y) ;c(x , y) = b(x , y) ;Complex schedules:
I Split
I Reorder / reorder storage
I Vectorize / Parallel
I Compute at / compute root

35 / 41

Simple Halide Example
Algorithm:

OpenTuner Generated Schedule:

ImageParam i n p u t ( UInt ( 1 6 ) , 2 ) ;Func a ( ” a ” ) , a ( ”b” ) , a ( ” c ” ) ;Var x ( ” x ” ) , y ( ” y ” ) ;Var x0 , y1 , x2 , x4 , y5 ;a . s p l i t ( x , x , x0 , 4 ). s p l i t ( y , y , y1 , 1 6 ). r e o r d e r ( y1 , x0 , y , x ). v e c t o r i z e ( y1 , 4 ). compute at ( b , y ) ;b . s p l i t ( x , x , x2 , 6 4 ). r e o r d e r ( x2 , x , y ). reorder storage (y , x)
. v e c t o r i z e ( x2 , 8 ). compute at ( c , x4 ) ;c . s p l i t ( x , x , x4 , 8 ). s p l i t ( y , y , y5 , 2 ). r e o r d e r ( x4 , y5 , y , x ). parallel (x). compute root ( ) ;a(x , y) = input (x , y) ;b(x , y) = a(x , y) ;c(x , y) = b(x , y) ;Complex schedules:
I Split
I Reorder / reorder storage
I Vectorize / Parallel
I Compute at / compute root

35 / 41

Simplified Schedules (Placement Only)

Schedule:a.compute at(b, y)b.compute at(c, x)
c.compute root()

36 / 41

Simplified Schedules (Placement Only)
Logical Loop Structure:
Schedule:a.compute at(b, y)b.compute at(c, x)
c.compute root()

36 / 41

Simplified Schedules (Placement Only)
Logical Loop Structure:
Schedule:

for c x:a.compute at(b, y)b.compute at(c, x)
c.compute root()
for c y:compute c()

36 / 41

Simplified Schedules (Placement Only)
Logical Loop Structure:
Schedule:a.compute at(b, y)b.compute at(c, x)
c.compute root()

for c x:for b x:for b y:compute b()
for c y:compute c()

36 / 41

Simplified Schedules (Placement Only)
Logical Loop Structure:
Schedule:a.compute at(b, y)b.compute at(c, x)
c.compute root()

for c x:for b x:for b y:for a x:for a y:compute a()compute b()
for c y:compute c()

36 / 41

Simplified Schedules (Placement Only)
Logical Loop Structure:
Schedule:a.compute at(b, y)b.compute at(c, x)
c.compute root()

Resulting Code:for c x:for b x:for b y:for a x:for a y:compute a()compute b()
for c y:compute c()for x:for y:
tmp a = input[x, y]
tmp b[y] = tmp afor y:
output[x, y] = tmp b[y]36 / 41

Naive Halide Representation

Based on Halidescheduling language:a.compute at(b, y)b.compute at(c, x)
c.compute root()

37 / 41

Naive Halide Representation

I 8 possible placements:

compute at(a, x),
compute at(a, y),
I compute at(b, x),
I compute at(b, y),
I compute at(c, x),
I compute at(c, y),
I compute root(),
I inline

I

Based on Halidescheduling language:a.compute at(b, y)b.compute at(c, x)
c.compute root()I37 / 41

Naive Halide Representation

I 8 possible placements:

compute at(a, x),
compute at(a, y),
I compute at(b, x),
I compute at(b, y),
I compute at(c, x),
I compute at(c, y),
I compute root(),
I inline

I

Based on Halidescheduling language:a.compute at(b, y)b.compute at(c, x)
c.compute root()I

I 3 computations that must beplaced (a, b, c):
I 512 possible schedules

37 / 41

Naive Representation Does Not WorkI Naive representation works for

simple halide programs
I Fails completely for more complex

programs

38 / 41

Naive Representation Does Not WorkI Naive representation works for

simple halide programs
I Fails completely for more complex

programs
I 474 of 512 schedules are invalid
I
I

Callgraph orderings not respected
Exponentially worse with larger
programs

I Poor locality
I

Small changes move large
subtrees around38 / 41

Better Representation
for c x:for b x:for b y:for a x:for a y:compute a()compute b()
for c y:compute c()
I Representation based logical loop structure
I Loop structure can be reconstructed from token order
I Representation is a permutation of tokens that:39 / 41

Better Representation
for c x:for b x:for b y:for a x:for a y:compute a()compute b()
for c y:compute c()
I Representation based logical loop structure
I Loop structure can be reconstructed from token order
I Representation is a permutation of tokens that:
I

Respects callgraph orderings

39 / 41

Better Representation
for c x:for b x:for b y:for a x:for a y:compute a()compute b()
for c y:compute c()
I Representation based logical loop structure
I Loop structure can be reconstructed from token order
I Representation is a permutation of tokens that:
I
I

Respects callgraph orderings
Respects loop orderings

39 / 41

Better Representation
for c x:for b x:for b y:for a x:for a y:compute a()compute b()
for c y:compute c()
I Representation based logical loop structure
I Loop structure can be reconstructed from token order
I Representation is a permutation of tokens that:
I
I

Respects callgraph orderings
Respects loop orderings

I Handling of some subtle corner cases and reorder()discussed in the paper
39 / 41

Halide Blur

Execution Time (seconds)

0.03

Hand-optimized
OpenTuner

0.025
0.02
0.015
0.01
0.005
0

0

100
200
300
400
Autotuning Time (seconds)

500

40 / 41

Halide Bilateral Grid

Execution Time (seconds)

1.4

Hand-optimized
OpenTuner

1.2
1
0.8
0.6
0.4
0.2
0

0

5000
10000
15000
Autotuning Time (seconds)

41 / 41