2020-07-09

Yesterday I spent some more time trying to think about how best to do the linear scan. I ended up wanting to rewrite Cosmins last-use analysis and use that instead of my own last-use analysis, because having last-use information attached to each expression/block seems more useful than just having a list of line-numbers. The plan is to continute that implementation today.

However, Cosmin has also written an email stating that driver-knn.fut is not being tuned correctly with my new autotuner. I'll have to look in to that first.

Let's try to run the benchmark using a few different version of the compiler.

$ futhark-0.15.8 bench --backend=opencl driver-knn.fut
Compiling driver-knn.fut...
Reporting average runtime of 10 runs for each dataset.

Results for driver-knn.fut:
256i32 [2097152][7]f32 [10000000][7]f32:    2817820μs (RSD: 0.003; min:  -0%; max:  +1%)

[jxk588@a00333 knn-by-kdtree]$ futhark-0.16.1 bench --backend=opencl driver-knn.fut
Compiling driver-knn.fut...
Reporting average runtime of 10 runs for each dataset.

Results for driver-knn.fut:
256i32 [2097152][7]f32 [10000000][7]f32:    4680997μs (RSD: 0.026; min:  -3%; max:  +5%)

Results for driver-knn.fut:
256i32 [2097152][7]f32 [10000000][7]f32:    4680997μs (RSD: 0.026; min:  -3%; max:  +5%)
[jxk588@a00333 knn-by-kdtree]$ futhark-0.16.1 autotune --backend=opencl driver-knn.fut
Compiling driver-knn.fut...
Tuning main.suff_outer_par_0 on entry point main and dataset 256i32 [2097152][7]f32 [10000000][7]f32
Tuning main.suff_outer_par_1 on entry point main and dataset 256i32 [2097152][7]f32 [10000000][7]f32
Tuning main.suff_outer_par_2 on entry point main and dataset 256i32 [2097152][7]f32 [10000000][7]f32
Tuning main.suff_intra_par_7 on entry point main and dataset 256i32 [2097152][7]f32 [10000000][7]f32
Tuning main.suff_intra_par_4 on entry point main and dataset 256i32 [2097152][7]f32 [10000000][7]f32
Tuning main.suff_outer_par_3 on entry point main and dataset 256i32 [2097152][7]f32 [10000000][7]f32
Tuning main.suff_outer_redomap_15 on entry point main and dataset 256i32 [2097152][7]f32 [10000000][7]f32
Wrote driver-knn.fut.tuning
Result of autotuning:
main.suff_intra_par_4=2097152
main.suff_intra_par_7=2000000000
main.suff_outer_par_0=2000000000
main.suff_outer_par_1=7
main.suff_outer_par_2=2000000000
main.suff_outer_par_3=2000000000
main.suff_outer_redomap_15=10248

[jxk588@a00333 knn-by-kdtree]$ futhark-0.16.1 bench --backend=opencl driver-knn.fut
Compiling driver-knn.fut...
Reporting average runtime of 10 runs for each dataset.

Results for driver-knn.fut (using driver-knn.fut.tuning):
256i32 [2097152][7]f32 [10000000][7]f32:    4688262μs (RSD: 0.027; min:  -4%; max:  +6%)

That took a looooong time… But the tuning results seem to at least match the performance of the untuned program. However, it's significantly slower than the 0.15.8 version.

Troels suggests I not worry about the regression from 0.15.8, so I've sent Cosmin an e-mail asking for his tuning parameters. He got

main.suff_intra_par_4=2000000000
main.suff_intra_par_7=2097152
main.suff_outer_par_0=2000000000
main.suff_outer_par_1=2000000000
main.suff_outer_par_2=2000000000
main.suff_outer_par_3=2000000000
main.suff_outer_redomap_15=5615445

I need to test his numbers on gpu04, but someone else is using the machine right now. It would be nice to figure out which of the two parameters are causing the problem.

Do I really need to use the LastUses lore? Why do I think I need it? I think I need it because it would make it easier to handle blocks. Here's the example from the other day:

 1: let mem1 = alloc(42)
 2: -- last-use: []
 3: let arr1@mem1 = ...
 4: 
 5: let x = reduce (+) 0 arr1
 6: 
 7: let (mem2, arr2@mem2) =
 8:   if ... then
 9:     let mem_then = alloc(42)
10:     let res_then@mem_then = map (* 2) (iota 42)
11:     in (mem_then, res_then)
12:   else
13:     let mem_else = alloc(x)
14:     let res_else = map (* 2) (iota x)
15:     in (mem_then, res_else)

And this is what it is transformed to:

 1: let mem1 = alloc(42)
 2: -- freelist: []
 3: let arr1@mem1 = ...
 4: -- freelist: []
 5: 
 6: let x = reduce (+) 0 arr1
 7: -- last-use is [arr1, mem1], freelist: [(mem1, 42)]
 8: 
 9: let (mem2, arr2@mem2) =
10:   if ... then
11:     -- mem1 is free and of size 42, so we use that instead of allocing
12:     let mem_then = mem1
13:     -- freelist is now []
14:     let res_then@mem_then = map (* 2) (iota 42)
15:     in (mem_then, res_then)
16:     -- also return freelist = []
17:   else
18:     let mem_else = alloc(x)
19:     let res_else = map (* 2) (iota x)
20:     in (mem_then, res_else)
21:     -- also return freelist = [(mem1, 42)]
22: -- freelist after if = []
23: ...
24: 
25: let y = reduce (+) 0 arr2
26: -- last-use is [arr2, mem2], freelist = [(mem2, ext)], cannot be reused

We could do something similar using the line counts, I guess? But this is so simple and straightforward, I think it's worth writing a more complicated LastUse lore for it.

There's one problem however: the last-use of mem1 isn't actually on line 6, but on line 3.

Wait, we can do the same thing rather simply by using the line count, right? Just have the last-uses sorted by line, pop things off the front, populate the freelist as required? Then, inside each block, we call last-uses before proceeding with the linear scan?

Also, we should rewrite last-uses to work on Body instead, so we can remove last-use entries for things that are returned by the body.