Super Mario Bros. problem

Input space

I 5 buttons per frame
I 24000 frames
I 524000 ≈ 1.9 × 1016775 possible input sequences

Exhaustive search won’t work here.

Tuning processNaive Representation1

http://youtu.be/nyYdq1jJQrw

Naive Representation

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

1

http://youtu.be/nyYdq1jJQrw

Better Representation

I Movements (list):IIDirection (left, right, run left, or run right)
Duration (frames)

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)

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

Super Mario Bros Results

Pixels Moved Right (Progress)

3500
30002500
2000
1500
1000

Win Level
OpenTuner
060120180
240Autotuning Time (seconds)

300

StreamJIT
input
5LowPassFilter
11 (2)

Synchronous dataflow programs
are graphs of (mostly) statelessworkers with statically-known
data rates.

FMDemodulator
1
6
DuplicateSplitter
1 x6
1
DuplicateSplitter

x6

1 x2

Using the data rates, thecompiler can compute a scheduleof worker executions, fuseworkers and introduce buffers toremove synchronization, thenchoose a combination of data,task and pipeline parallelism tofit the machine.

1 (4)

1 (4)

LowPassFilter1

LowPassFilter
1
1 x2
RoundrobinJoiner
22Subtractor
1
1Amplifier
1
1 x6
RoundrobinJoiner
66Summer
1
outputFusion, data-parallel fission and splitter/joiner removal

BandPass

BandPass

Compress

Compress

Process

Process

ExpandExpandBandStop

BandStop

Adder

BandPass
Compress
Process
ExpandBandPass
Compress
Process
ExpandBandStop

BandStop

Adder
Adder
Adder
Adder

Autotuning

StreamJIT delegates its optimization decisions to OpenTuner,which decides
I an overall schedule multiplier (to amortize synchronization)
I whether to fuse workers
I whether to remove splitters and joiners
I buffer implementations
I how to allocate fused groups to cores

Autotuning work allocation

Equal distribution across all cores is usually the best, but we needto load-balance around stateful workers.
I Bitset per worker, one bit per core: exponentially hard to get

equal distribution (all bits set).
I Array of floats summing to 1.0, one float per core: allows

load-balancing, but equal distribution is even harder.

Autotuning work allocation

Equal distribution across all cores is usually the best, but we needto load-balance around stateful workers.
I Bitset per worker, one bit per core: exponentially hard to get

equal distribution (all bits set).
I Array of floats summing to 1.0, one float per core: allows

load-balancing, but equal distribution is even harder.
I Permutation of cores, total count, bias count and bias

fraction: equal division across cores, biased for load balancing.

Bias fraction work allocation
Use the first count cores of the permutation, moving fraction of
the work from the first bias count cores.

Doesn’t cover all possibilities, but covers the good ones.

Custom techniques
StreamJIT uses custom techniques that force the obvious defaults.
Other techniques make some good and some bad changes:↑-↓--↑-↓↑↑-↓Custom techniques will then force some of the bad changes back:↑----↑-↓↑↑-Bandit will learn to stop using the custom techniques when theystop working or for unusual graphs where the obvious defaults arebad.