Autotuning Halideschedules withOpenTuner
Jonathan Ragan-Kelley(Stanford)We are surrounded by computational cameras
Enormous opportunity,
demands extreme optimization
parallelism & locality limit
performance and energyWe are surrounded by computational cameras
Enormous opportunity,
demands extreme optimization
parallelism & locality limit
performance and energy
Camera: 8 Mpixels(96MB/frame as float)

CPUs: 15 GFLOP/sec
GPU: 115 GFLOP/sec

We are surrounded by computational cameras
Enormous opportunity,
demands extreme optimization
parallelism & locality limit
performance and energy
Camera: 8 Mpixels(96MB/frame as float)

CPUs: 15 GFLOP/sec
GPU: 115 GFLOP/sec
Requiredarithmetic > 40:1
intensity

A realistic pipeline: Local Laplacian Filters[Paris et al. 2010, Aubry et al. 2011]

COPY

input

COPY

LUT
SUB

level size
w×h

DOWN

DOWN

ADD
DOWN

UP
SUB

w×h
2 2

DDA

DDA

ADD
DOWN

UP

UP

...

..

..

..

...

DDA
COPY

LUT: look-up table
UP: upsample
O(x,y,k) ← lut(I(x,y) − kσ) T1(2x,2y) ← I(x,y)
T2 ← T1 ⊗x [1 3 3 1]
O ← T2 ⊗y [1 3 3 1]
ADD: addition
O(x,y) ← I1(x,y) + I2(x,y)
DOWN: downsample
T1 ← I ⊗x [1 3 3 1]
SUB: subtraction
T2 ← T1 ⊗y [1 3 3 1]O(x,y) ← I1(x,y) − I2(x,y)
O(x,y) ← T2(2x,2y)

UPThe algorithm uses 8 pyramid levels

w × h128 128

output

DDA: data-dependent accessk ← floor(I1(x,y) / σ)α ← (I1(x,y) / σ) − kO(x,y) ← (1−α) I2(x,y,k) + α I2(x,y,k+1)

COPY

wide, deep, heterogeneous
stencils + stream processing

Local Laplacian Filtersin Adobe Photoshop Camera Raw / Lightroom

1500 lines of expertoptimized C++
multi-threaded, SSE
3 months of work
10x faster than reference CLocal Laplacian Filtersin Adobe Photoshop Camera Raw / Lightroom

1500 lines of expertoptimized C++
multi-threaded, SSE
3 months of work
10x faster than reference CLocal Laplacian Filtersin Adobe Photoshop Camera Raw / Lightroom

1500 lines of expertoptimized C++
multi-threaded, SSE
3 months of work
10x faster than reference CLocal Laplacian Filtersin Adobe Photoshop Camera Raw / Lightroom

1500 lines of expertoptimized C++
multi-threaded, SSE
3 months of work
10x faster than reference C
2x slower than anotherorganization (which theycouldn’t find)Halidea new language & compiler for image processing

Halidea new language & compiler for image processing
1. Decouple algorithm from schedule
Algorithm: what is computed
Schedule: where and when it’s computed

Halidea new language & compiler for image processing
1. Decouple algorithm from schedule
Algorithm: what is computed
Schedule: where and when it’s computed

we want to autotune thisThe algorithm defines pipelines as pure functions
Pipeline stages are functions from coordinates to values
Execution order and storage are unspecified

The algorithm defines pipelines as pure functions
Pipeline stages are functions from coordinates to values
Execution order and storage are unspecified

3x3 blur as a Halide algorithm:
blurx(x,	  y)	  =	  (in(x-­‐1,	  y)	  +	  in(x,	  y)	  +	  in(x+1,	  y))/3;
blury(x,	  y)	  =	  (blurx(x,	  y-­‐1)	  +	  blurx(x,	  y)	  +	  blurx(x,	  y+1))/3;

Halidea new language & compiler for image processing
1. Decouple algorithm from schedule
Algorithm: what is computed
Schedule: where and when it’s computed

Halidea new language & compiler for image processing
1. Decouple algorithm from schedule
Algorithm: what is computed
Schedule: where and when it’s computed

2. Single, unified model for all schedules

Halidea new language & compiler for image processing
1. Decouple algorithm from schedule
Algorithm: what is computed
Schedule: where and when it’s computed

2. Single, unified model for all schedules
Simple enough to search, expose to user
Powerful enough to beat expert-tuned codeThe schedule defines intra-stage order, inter-stage interleaving
input

blurx

blury

The schedule defines intra-stage order, inter-stage interleaving
For each stage:
1) In what order should wecompute its values?

input

blurx

blury

The schedule defines intra-stage order, inter-stage interleaving
For each stage:
1) In what order should wecompute its values?

input

split, tile, reorder, vectorize,
unroll loops

blurx

blury

The schedule defines intra-stage order, inter-stage interleaving
For each stage:
1) In what order should wecompute its values?

input

split, tile, reorder, vectorize,
unroll loops

2) When should wecompute its inputs?

blurxblury

The schedule defines intra-stage order, inter-stage interleaving
For each stage:
1) In what order should wecompute its values?

input

split, tile, reorder, vectorize,
unroll loops

2) When should wecompute its inputs?
level in loop nest ofconsumers at which tocompute each producer

blurx

blury

Schedule primitives compose to create many organizations	  	  blur_x.compute_at_root()

redundant
work

locality	  	  blur_x.compute_at(blury,	  x)redundant
workparallelism	  	  blur_x.compute_at(blury,	  x)	  	  	  	  	  	  	  	  .vectorize(x,	  4)	  	  blur_y.tile(x,	  y,	  xi,	  yi,	  8,	  8)	  	  	  	  	  	  	  	  .parallel(y)	  	  	  	  	  	  	  	  .vectorize(xi,	  4)redundant
work

locality	  	  blur_x.compute_at(blury,	  x)	  	  	  	  	  	  	  	  .store_at_root()

redundant
work

locality

locality

parallelism

parallelism	  	  blur_x.compute_at(blury,	  y)	  	  	  	  	  	  	  	  .store_at_root()	  	  	  	  	  	  	  	  .split(x,	  x,	  xi,	  8)	  	  	  	  	  	  	  	  .vectorize(xi,	  4)	  	  	  	  	  	  	  	  .parallel(x)	  	  blur_x.compute_at(blury,	  y)	  	  	  	  	  	  	  	  .store_at(blury,	  yi)	  	  	  	  	  	  	  	  .vectorize(x,	  4)	  	  blur_y.split(x,	  x,	  xi,	  8)	  	  	  	  	  	  	  	  .vectorize(xi,	  4)	  	  	  	  	  	  	  	  .parallel(x)	  	  blur_y.split(y,	  y,	  yi,	  8)	  	  	  	  	  	  	  	  .parallel(y)	  	  	  	  	  	  	  	  .vectorize(x,	  4)redundant
work

redundant
work

locality

locality	  	  	  parallelism

parallelismparallelism

Schedule primitives compose to create many organizations
in

blurx

redundant
work

blury

in

blurx

redundant
work

locality

parallelism

in

blury

locality

parallelism

in

blurx

redundant
work

locality

parallelism

blurx

redundant
work

blury

in

blury

locality

parallelism

locality

parallelism

blurx

redundant
work

blury

in

blurx

redundant
work

blury

locality

parallelism

A trivial Halide program//	  The	  algorithm	  -­‐	  no	  storage,	  ordera(x,	  y)	  =	  in(x,	  y);b(x,	  y)	  =	  a(x,	  y);c(x,	  y)	  =	  b(x,	  y);A trivial Halide program//	  The	  algorithm	  -­‐	  no	  storage,	  ordera(x,	  y)	  =	  in(x,	  y);b(x,	  y)	  =	  a(x,	  y);c(x,	  y)	  =	  b(x,	  y);Schedules are complex
split
reorder / reorder_storage
vectorize / parallel
compute_at / store_at//	  generated	  schedulea.split(x,	  x,	  x0,	  4)	  .split(y,	  y,	  y1,	  16)	  .reorder(y1,	  x0,	  y,	  x)	  .vectorize(y1,	  4)	  .compute_at(b,	  y);b.split(x,	  x,	  x2,	  64)	  .reorder(x2,	  x,	  y)	  .reorder_storage(y,	  x)	  .vectorize(x2,	  8)	  .compute_at(c,	  x4);
c.split(x,	  x,	  x4,	  8)	  .split(y,	  y,	  y5,	  2)	  .reorder(x4,	  y5,	  y,	  x)	  .parallel(x)	  .compute_root();

A trivial Halide program//	  The	  algorithm	  -­‐	  no	  storage,	  ordera(x,	  y)	  =	  in(x,	  y);b(x,	  y)	  =	  a(x,	  y);c(x,	  y)	  =	  b(x,	  y);Schedules are complex
split
reorder / reorder_storage
vectorize / parallel
compute_at / store_at//	  generated	  schedulea.split(x,	  x,	  x0,	  4)	  .split(y,	  y,	  y1,	  16)	  .reorder(y1,	  x0,	  y,	  x)	  .vectorize(y1,	  4)	  .compute_at(b,	  y);b.split(x,	  x,	  x2,	  64)	  .reorder(x2,	  x,	  y)	  .reorder_storage(y,	  x)	  .vectorize(x2,	  8)	  .compute_at(c,	  x4);
c.split(x,	  x,	  x4,	  8)	  .split(y,	  y,	  y5,	  2)	  .reorder(x4,	  y5,	  y,	  x)	  .parallel(x)	  .compute_root();

A simple schedule (interleaving only)
Synthesized loop nest:
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:	  	  	  	  	  	  	  	  	  	  a[a.x,	  a.y]	  =	  in[a.x,	  a.y]	  	  	  	  	  	  b[b.x,	  b.y]	  =	  a[b.x,	  b.y]	  	  for	  c.y:	  	  	  	  c[c.x,	  c.y]	  =	  b[c.x,	  c.y]

A naive representation

Direct schedule encoding:a.compute_at(b,	  y);b.compute_at(c,	  x);c.compute_root();

A naive representation
8 placement locationsDirect schedule encoding:a.compute_at(b,	  y);b.compute_at(c,	  x);c.compute_root();

compute_at(a, x)
compute_at(a, y)
compute_at(b, x)
compute_at(b, y)compute_at(c, x)
compute_at(c, y)compute_root()
inlineA naive representation
8 placement locations

Direct schedule encoding:a.compute_at(b,	  y);b.compute_at(c,	  x);c.compute_root();

compute_at(a, x)
compute_at(a, y)
compute_at(b, x)
compute_at(b, y)compute_at(c, x)
compute_at(c, y)compute_root()
inline3 functions to place(a, b, c)A naive representation
8 placement locations

Direct schedule encoding:a.compute_at(b,	  y);b.compute_at(c,	  x);c.compute_root();

compute_at(a, x)
compute_at(a, y)
compute_at(b, x)
compute_at(b, y)compute_at(c, x)
compute_at(c, y)compute_root()
inline3 functions to place(a, b, c)3
8 = 512 possible schedules

A naive representation
doesn’t work
Most of the space ismeaningless474 of 512 schedules are invalid
Exponentially worse for large
programs

Poor search space locality
small changes radically restructure
the generated loops

Fails completely for
nontrivial programs

A naive representation
doesn’t work
Most of the space ismeaningless474 of 512 schedules are invalid
Exponentially worse for large
programs

Poor search space locality
small changes radically restructure
the generated loops

Fails completely for
nontrivial programsfor	  c.x:	  	  for	  b.x:	  	  	  	  for	  b.y:	  	  	  	  	  	  for	  a.x:	  	  	  	  	  	  	  	  for	  a.y:	  	  	  	  	  	  	  	  	  	  compute	  a()	  	  	  	  	  	  compute	  b()	  	  for	  c.y:	  	  	  	  compute	  c()A naive representation
doesn’t work
Most of the space ismeaningless474 of 512 schedules are invalid
Exponentially worse for large
programs

Poor search space locality
small changes radically restructure
the generated loops

for	  c.x:	  	  for	  b.x:	  	  	  	  for	  b.y:	  	  	  	  	  	  for	  a.x:	  	  	  	  	  	  	  	  for	  a.y:	  	  	  	  	  	  	  	  	  	  compute	  a()	  	  	  	  	  	  compute	  b()	  	  for	  c.y:	  	  	  	  compute	  c()A naive representation
doesn’t work
Most of the space ismeaningless474 of 512 schedules are invalid
Exponentially worse for large
programs

Poor search space locality
small changes radically restructure
the generated loops

Fails completely for
nontrivial programsfor	  c.x:	  	  for	  b.x:	  	  	  	  for	  b.y:	  	  	  	  	  	  for	  a.x:	  	  	  	  	  	  	  	  for	  a.y:	  	  	  	  	  	  	  	  	  	  compute	  a()	  	  	  	  	  	  compute	  b()	  	  for	  c.y:	  	  	  	  compute	  c()A better representation

A better representation
loop orderconstraints

c.x
b.x
b.y
a.x
a.y
compute	  a()a.endcompute	  b()
b.end
c.y
compute	  c()c.endconstrained
permuted list

callgraphorder
constraints

A better representation
loop orderconstraints

c.x
b.x
b.y
a.x
a.y
compute	  a()a.endcompute	  b()
b.end
c.y
compute	  c()c.endconstrained
permuted list

callgraphorder
constraints

for	  c.x:	  	  for	  b.x:	  	  	  	  for	  b.y:	  	  	  	  	  	  for	  a.x:	  	  	  	  	  	  	  	  for	  a.y:	  	  	  	  	  	  	  	  	  	  compute	  a()	  	  	  	  	  	  compute	  b()	  	  for	  c.y:	  	  	  	  compute	  c()Halide Blur

Results: blur

Execution Time (seconds)

0.03

Hand-optimized
OpenTuner

0.025
0.020.015
0.010.005
00100
200
300
400
Autotuning Time (seconds)

500

Halide Wavelet

Execution Time (seconds)

0.02

Results: wavelet
Hand-optimized
OpenTuner

0.015

0.01

0.005

00500
1000
Autotuning Time (seconds)

Halide Bilateral Grid

Results: bilateral grid
Execution Time (seconds)

1.4

Hand-optimized
OpenTuner

1.2
10.8
0.6
0.4
0.2
005000
10000
15000
Autotuning Time (seconds)

x86
Blur
Bilateral GridSpeedup

Factorshorter

1.2 ⨉

18 ⨉

4.4 ⨉

4⨉

Camera pipeline

3.4 ⨉

2⨉

“Healing brush”

1.7 ⨉

7⨉

Local Laplacian

1.7 ⨉

5⨉

Speedup

Factorshorter

Bilateral Grid

2.3 ⨉

11 ⨉

“Healing brush”

5.9* ⨉

7* ⨉Local Laplacian

9* ⨉

7* ⨉

Speedup

Factorshorter

1.1 ⨉

3⨉

GPU

ARM
Camera pipeline

x86
Blur
Bilateral Grid

Speedup

Factorshorter

1.2 ⨉

18 ⨉

4.4 ⨉

4⨉

Camera pipeline

3.4 ⨉

2⨉

“Healing brush”

1.7 ⨉

7⨉

Local Laplacian

1.7 ⨉

5⨉

Speedup

Factorshorter

Bilateral Grid2.3 ⨉11 ⨉“Healing brush”

5.9* ⨉

7* ⨉Local Laplacian

9* ⨉

7* ⨉

Speedup

Factorshorter

1.1 ⨉3⨉

GPUARM
Camera pipeline

x86
Blur
Bilateral Grid

Speedup

Factorshorter

1.2 ⨉

18 ⨉

4.4 ⨉

4⨉

Camera pipeline

3.4 ⨉

2⨉

“Healing brush”

1.7 ⨉

7⨉

Local Laplacian

1.7 ⨉

5⨉

Speedup

Factorshorter

Bilateral Grid

2.3 ⨉

11 ⨉

“Healing brush”

5.9* ⨉

7* ⨉Local Laplacian

9* ⨉

7* ⨉

Speedup

Factorshorter

1.1 ⨉3⨉GPUARM
Camera pipeline

Autotuning time:(single node)
2 hrs to 2 days
85% within < 24 hrs

x86
Blur
Bilateral Grid

Speedup

Factorshorter

1.2 ⨉

18 ⨉

4.4 ⨉4⨉

Camera pipeline

3.4 ⨉

2⨉

“Healing brush”

1.7 ⨉

7⨉

Local Laplacian

1.7 ⨉

5⨉

Speedup

Factorshorter

Bilateral Grid

2.3 ⨉

11 ⨉

“Healing brush”

5.9* ⨉

7* ⨉Local Laplacian

9* ⨉

7* ⨉

Speedup

Factorshorter

1.1 ⨉

3⨉GPU

ARM
Camera pipeline

In progress
new representation
smarter heuristic seedschedules

Autotuning time:(single node)
2 hrs to 2 days
85% within < 24 hrs

Halide: current status
open source at http://halide-lang.org

Google~ 50 developers> 10 kLOC in production
G+ Photos auto-enhance
Data centerAndroid
Chrome (PNaCl)

HDR+GlassNexus devices

Computational photography course (6.815)
60 undergrads