HOME

2020-08-26

ReuseAllocations

We're getting closer and closer to a ReuseAllocations.

For reference, here is the graph and coloring for psum.fut:

graph = [(mem_764, mem_768), (mem_768, mem_772)]

coloring = [(mem_764, 0), (mem_768, 1), (mem_772, 0)]

There are two colors, but for some reason, my optimiseKernel produces three colors?

Eh, there's something strange going on when I call analyseSegOps directly. By hoisting the interference graph analysis, I seemed to fix the problem. Is this a long-term solution though? We need the interference graphs to be per-kernel. I guess they are so now.

I now have… something:

 1: #[incremental_flattening(only_intra)]
 2: let {i64 binop_x_774} = sext i32 impl₀_245 to i64
 3: #[incremental_flattening(only_intra)]
 4: let {i64 binop_y_775} = sext i32 impl₁_246 to i64
 5: #[incremental_flattening(only_intra)]
 6: let {i64 binop_x_776} = mul_nw64(binop_x_774, binop_y_775)
 7: #[incremental_flattening(only_intra)]
 8: let {i64 bytes_773} = mul_nw64(4i64, binop_x_776)
 9: #[incremental_flattening(only_intra)]
10: let {mem mem_777} =
11:   alloc(bytes_773)
12: let {i64 binop_x_763} = binop_y_775
13: let {i64 bytes_762} = mul_nw64(4i64, binop_y_775)
14: let {i64 binop_x_767} = binop_y_775
15: let {i64 bytes_766} = bytes_762
16: let {i64 binop_x_771} = binop_y_775
17: let {i64 bytes_770} = bytes_762
18: #[incremental_flattening(only_intra)]
19: -- res_408 : [impl₀_245][impl₁_246]i32@@mem_777->
20: -- {base: [impl₀_245, impl₁_246]; contiguous: True; LMADs: [{offset: 0i32;
21: --                                                           strides: [impl₁_246, 1i32];
22: --                                                           rotates: [0i32, 0i32];
23: --                                                           shape: [impl₀_245, impl₁_246];
24: --                                                           permutation: [0, 1];
25: --                                                           monotonicity: [Inc, Inc]}]}
26: let {[impl₀_245][impl₁_246]i32 res_408} =
27:   segmap_group
28:   (#groups=impl₀_245; groupsize=impl₁_246)
29:   (gtid_292 < impl₀_245) (~phys_tid_305) : {[impl₁_246]i32} {
30:     let {mem color_778} =
31:       alloc(bytes_762)
32:     let {mem color_779} =
33:       alloc(bytes_762)
34:     let {mem@local mem_764} = color_778
35:     -- resarr0_415 : [impl₁_246]i32@@mem_764->
36:     -- {base: [impl₁_246]; contiguous: True; LMADs: [{offset: 0i32; strides: [1i32];
37:     --                                                rotates: [0i32];
38:     --                                                shape: [impl₁_246];
39:     --                                                permutation: [0];
40:     --                                                monotonicity: [Inc]}]}
41:     let {[impl₁_246]i32 resarr0_415} =
42:       segscan_thread
43:       (#groups=impl₀_245; groupsize=impl₁_246)
44:       ({{0i32},
45:         [],
46:         fn {i32} (i32 x_416, i32 x_417) =>
47:           let {i32 res_418} = add32(x_416, x_417)
48:           in {res_418}})
49:       (gtid_295 < impl₁_246) (~phys_tid_296) : {i32} {
50:         let {i32 x_419} = xss_247[gtid_292, gtid_295]
51:         return {returns x_419}
52:       }
53:     let {mem@local mem_768} = color_779
54:     -- resarr0_425 : [impl₁_246]i32@@mem_768->
55:     -- {base: [impl₁_246]; contiguous: True; LMADs: [{offset: 0i32; strides: [1i32];
56:     --                                                rotates: [0i32];
57:     --                                                shape: [impl₁_246];
58:     --                                                permutation: [0];
59:     --                                                monotonicity: [Inc]}]}
60:     let {[impl₁_246]i32 resarr0_425} =
61:       segscan_thread
62:       (#groups=impl₀_245; groupsize=impl₁_246)
63:       ({{0i32},
64:         [],
65:         fn {i32} (i32 x_426, i32 x_427) =>
66:           let {i32 res_428} = add32(x_426, x_427)
67:           in {res_428}})
68:       (gtid_297 < impl₁_246) (~phys_tid_298) : {i32} {
69:         let {i32 x_429} = resarr0_415[gtid_297]
70:         return {returns x_429}
71:       }
72:     let {mem@local mem_772} = color_778
73:     -- resarr0_434 : [impl₁_246]i32@@mem_772->
74:     -- {base: [impl₁_246]; contiguous: True; LMADs: [{offset: 0i32; strides: [1i32];
75:     --                                                rotates: [0i32];
76:     --                                                shape: [impl₁_246];
77:     --                                                permutation: [0];
78:     --                                                monotonicity: [Inc]}]}
79:     let {[impl₁_246]i32 resarr0_434} =
80:       segscan_thread
81:       (#groups=impl₀_245; groupsize=impl₁_246)
82:       ({{0i32},
83:         [],
84:         fn {i32} (i32 x_435, i32 x_436) =>
85:           let {i32 res_437} = add32(x_435, x_436)
86:           in {res_437}})
87:       (gtid_299 < impl₁_246) (~phys_tid_300) : {i32} {
88:         let {i32 x_438} = resarr0_425[gtid_299]
89:         return {returns x_438}
90:       }
91:     return {returns resarr0_434}
92:   }

There's (at least) one problem though: I don't take the allocation space into account. For instance, on line 34, color_778, a memory block residing in default memory, is assigned to mem_764, which is supposed to reside in local memory. Somehow, we need to make either the interference graph, the coloring algorithm, or the allocation reuser (or some combination of the three) aware of memory space such that only memory blocks in the same memory space are merged, and such that the new colored blocks are allocated in the correct space.

By manually setting the space to Space "local", we can inspect what the code would look like:

  1: -- xss_247 : [impl₀_245][impl₁_246]i32@@xss_mem_759->
  2: -- {base: [impl₀_245, impl₁_246]; contiguous: True; LMADs: [{offset: 0i32;
  3: --                                                           strides: [impl₁_246, 1i32];
  4: --                                                           rotates: [0i32, 0i32];
  5: --                                                           shape: [impl₀_245, impl₁_246];
  6: --                                                           permutation: [0, 1];
  7: --                                                           monotonicity: [Inc, Inc]}]}
  8: entry {*[?0][?1]i32@?2->
  9:        {base: [?0, ?1]; contiguous: True; LMADs: [{offset: 0i32;
 10:                                                    strides: [?1, 1i32];
 11:                                                    rotates: [0i32, 0i32];
 12:                                                    shape: [?0, ?1];
 13:                                                    permutation: [0, 1];
 14:                                                    monotonicity: [Inc, Inc]}]}}
 15: main (mem xss_mem_759, i32 impl₀_245, i32 impl₁_246,
 16:       [impl₀_245][impl₁_246]i32 xss_247) = {
 17:   #[incremental_flattening(only_intra)]
 18:   let {i64 binop_x_774} = sext i32 impl₀_245 to i64
 19:   #[incremental_flattening(only_intra)]
 20:   let {i64 binop_y_775} = sext i32 impl₁_246 to i64
 21:   #[incremental_flattening(only_intra)]
 22:   let {i64 binop_x_776} = mul_nw64(binop_x_774, binop_y_775)
 23:   #[incremental_flattening(only_intra)]
 24:   let {i64 bytes_773} = mul_nw64(4i64, binop_x_776)
 25:   #[incremental_flattening(only_intra)]
 26:   let {mem mem_777} =
 27:     alloc(bytes_773)
 28:   let {i64 bytes_762} = mul_nw64(4i64, binop_y_775)
 29:   #[incremental_flattening(only_intra)]
 30:   -- res_408 : [impl₀_245][impl₁_246]i32@@mem_777->
 31:   -- {base: [impl₀_245, impl₁_246]; contiguous: True; LMADs: [{offset: 0i32;
 32:   --                                                           strides: [impl₁_246, 1i32];
 33:   --                                                           rotates: [0i32, 0i32];
 34:   --                                                           shape: [impl₀_245, impl₁_246];
 35:   --                                                           permutation: [0, 1];
 36:   --                                                           monotonicity: [Inc, Inc]}]}
 37:   let {[impl₀_245][impl₁_246]i32 res_408} =
 38:     segmap_group
 39:     (#groups=impl₀_245; groupsize=impl₁_246)
 40:     (gtid_292 < impl₀_245) (~phys_tid_305) : {[impl₁_246]i32} {
 41:       let {mem@local color_778} =
 42:         alloc(bytes_762, @local)
 43:       let {mem@local color_779} =
 44:         alloc(bytes_762, @local)
 45:       -- resarr0_415 : [impl₁_246]i32@@color_778->
 46:       -- {base: [impl₁_246]; contiguous: True; LMADs: [{offset: 0i32; strides: [1i32];
 47:       --                                                rotates: [0i32];
 48:       --                                                shape: [impl₁_246];
 49:       --                                                permutation: [0];
 50:       --                                                monotonicity: [Inc]}]}
 51:       let {[impl₁_246]i32 resarr0_415} =
 52:         segscan_thread
 53:         (#groups=impl₀_245; groupsize=impl₁_246)
 54:         ({{0i32},
 55:           [],
 56:           fn {i32} (i32 x_416, i32 x_417) =>
 57:             let {i32 res_418} = add32(x_416, x_417)
 58:             in {res_418}})
 59:         (gtid_295 < impl₁_246) (~phys_tid_296) : {i32} {
 60:           let {i32 x_419} = xss_247[gtid_292, gtid_295]
 61:           return {returns x_419}
 62:         }
 63:       -- resarr0_425 : [impl₁_246]i32@@color_779->
 64:       -- {base: [impl₁_246]; contiguous: True; LMADs: [{offset: 0i32; strides: [1i32];
 65:       --                                                rotates: [0i32];
 66:       --                                                shape: [impl₁_246];
 67:       --                                                permutation: [0];
 68:       --                                                monotonicity: [Inc]}]}
 69:       let {[impl₁_246]i32 resarr0_425} =
 70:         segscan_thread
 71:         (#groups=impl₀_245; groupsize=impl₁_246)
 72:         ({{0i32},
 73:           [],
 74:           fn {i32} (i32 x_426, i32 x_427) =>
 75:             let {i32 res_428} = add32(x_426, x_427)
 76:             in {res_428}})
 77:         (gtid_297 < impl₁_246) (~phys_tid_298) : {i32} {
 78:           let {i32 x_429} = resarr0_415[gtid_297]
 79:           return {returns x_429}
 80:         }
 81:       -- resarr0_434 : [impl₁_246]i32@@color_778->
 82:       -- {base: [impl₁_246]; contiguous: True; LMADs: [{offset: 0i32; strides: [1i32];
 83:       --                                                rotates: [0i32];
 84:       --                                                shape: [impl₁_246];
 85:       --                                                permutation: [0];
 86:       --                                                monotonicity: [Inc]}]}
 87:       let {[impl₁_246]i32 resarr0_434} =
 88:         segscan_thread
 89:         (#groups=impl₀_245; groupsize=impl₁_246)
 90:         ({{0i32},
 91:           [],
 92:           fn {i32} (i32 x_435, i32 x_436) =>
 93:             let {i32 res_437} = add32(x_435, x_436)
 94:             in {res_437}})
 95:         (gtid_299 < impl₁_246) (~phys_tid_300) : {i32} {
 96:           let {i32 x_438} = resarr0_425[gtid_299]
 97:           return {returns x_438}
 98:         }
 99:       return {returns resarr0_434}
100:     }
101:   in {impl₀_245, impl₁_246, mem_777, res_408}
102: }

Promising, I think!

However, calling my program on OptionPricing.fut results in an error:

$ cabal run futhark-linear-scan -- ../futhark-benchmarks/finpar/OptionPricing.fut
Up to date
optimise graph: [(dir_vs_mem_9186, inpacc_mem_9405), (dir_vs_mem_9186, acc0_mem_9410),
 (dir_vs_mem_9186, mem_9431), (mem_9241, inpacc_mem_9405), (mem_9241,
                                                            acc0_mem_9410),
 (mem_9241, mem_9431), (mem_9258, mem_9271), (mem_9258, mem_9286), (mem_9258,
                                                                    inpacc_mem_9405),
 (mem_9258, acc0_mem_9410), (mem_9258, mem_9431), (mem_9271, inpacc_mem_9405),
 (mem_9271, acc0_mem_9410), (mem_9271, mem_9431), (mem_9286, inpacc_mem_9405),
 (mem_9286, acc0_mem_9410), (mem_9286, mem_9431), (mem_9335, mem_9347),
 (mem_9335, mem_9360), (mem_9335, inpacc_mem_9405), (mem_9335, acc0_mem_9410),
 (mem_9347, mem_9360), (mem_9347, inpacc_mem_9405), (mem_9347, acc0_mem_9410),
 (mem_9360, inpacc_mem_9405), (mem_9360, acc0_mem_9410), (mem_9388,
                                                          inpacc_mem_9405),
 (mem_9388, acc0_mem_9410), (inpacc_mem_9405, acc0_mem_9410), (inpacc_mem_9405,
                                                               mem_9431),
 (acc0_mem_9410, mem_9431)]
res:


graph: [(dir_vs_mem_9186, inpacc_mem_9405), (dir_vs_mem_9186, acc0_mem_9410),
 (dir_vs_mem_9186, mem_9431), (mem_9241, inpacc_mem_9405), (mem_9241,
                                                            acc0_mem_9410),
 (mem_9241, mem_9431), (mem_9258, mem_9271), (mem_9258, mem_9286), (mem_9258,
                                                                    inpacc_mem_9405),
 (mem_9258, acc0_mem_9410), (mem_9258, mem_9431), (mem_9271, inpacc_mem_9405),
 (mem_9271, acc0_mem_9410), (mem_9271, mem_9431), (mem_9286, inpacc_mem_9405),
 (mem_9286, acc0_mem_9410), (mem_9286, mem_9431), (mem_9335, mem_9347),
 (mem_9335, mem_9360), (mem_9335, inpacc_mem_9405), (mem_9335, acc0_mem_9410),
 (mem_9347, mem_9360), (mem_9347, inpacc_mem_9405), (mem_9347, acc0_mem_9410),
 (mem_9360, inpacc_mem_9405), (mem_9360, acc0_mem_9410), (mem_9388,
                                                          inpacc_mem_9405),
 (mem_9388, acc0_mem_9410), (inpacc_mem_9405, acc0_mem_9410), (inpacc_mem_9405,
                                                               mem_9431),
 (acc0_mem_9410, mem_9431)]
coloring: [(dir_vs_mem_9186, 3), (mem_9241, 3), (mem_9258, 4), (mem_9271, 3), (mem_9286,
                                                                     3),
 (mem_9335, 4), (mem_9347, 3), (mem_9360, 0), (mem_9388, 0), (inpacc_mem_9405,
                                                              2),
 (acc0_mem_9410, 1), (mem_9431, 0)]
inverted coloring: [(0, [mem_9360, mem_9388, mem_9431]), (1, [acc0_mem_9410]), (2,
                                                             [inpacc_mem_9405]),
 (3, [dir_vs_mem_9186, mem_9241, mem_9271, mem_9286, mem_9347]), (4, [mem_9258,
                                                                      mem_9335])]
look up: mem_9360
allocs: [(mem_9204, bytes_9195), (mem_9241, bytes_9195), (mem_9258, bytes_9254),
 (mem_9271, bytes_9269), (mem_9286, bytes_9269), (mem_9335, bytes_9198),
 (mem_9347, bytes_9254), (mem_9360, bytes_9269), (mem_9388, bytes_9198),
 (mem_9431, size_9430)]
look up: mem_9388
look up: mem_9431
look up: acc0_mem_9410
futhark-linear-scan: Map.!: given key is not an element in the map
CallStack (from HasCallStack):
  error, called at libraries/containers/containers/src/Data/Map/Internal.hs:627:17 in containers-0.6.2.1:Data.Map.Internal

There's probably an issue with the way I color the graph. For each kernel, I now try to color the whole graph, but I really only need the ones that are present in the current kernel. That may be the issue I'm running in to with regards to OptionPricing. So I should filter the graph first. Then, how do I handle the space issue? I guess the easiest thing is to make GreedyColoring aware or memory spaces.

Ah, and I also need to handle names that are not in the graph for some reason (they don't overlap with anything).

I think I've handled both now in GreedyColoring. Tomorrow, let's add some tests and try to integrate those changes in ReuseAllocations