1 # The build and the degree count on every thread. Each def here that hands 2 # one array to two tasks relies on Base's @unsafe Array.fork: the tasks that 3 # share an array read it, write cells no other task writes, or add to cells 4 # atomically. 5 import Base 6 import ./graph.bend as G 7 import ./penetrable.bend as P 8 import ./report.bend as Report 9 import ./vg.bend as VG 10 11 def fork3(a: Array & Array, b: Array & Array, c: Array & Array) -> G.Cols & G.Cols: 12 (a1, a2) = a 13 (b1, b2) = b 14 (c1, c2) = c 15 (G.Cols{a1, b1, c1}, G.Cols{a2, b2, c2}) 16 17 def fork_cols(c: G.Cols) -> G.Cols & G.Cols: 18 G.Cols{ys, lefts, rights} = c 19 fork3(Array.fork(F32, ys), Array.fork(U32, lefts), Array.fork(U32, rights)) 20 21 # The stack runs on blocks in parallel; a merge then walks the blocks in 22 # order. 23 type Blocks is Data: 24 BOne{b: G.Block} 25 BJoin{a: Blocks, b: Blocks} 26 27 def block_of(l: G.Local) -> Blocks: 28 G.Local{b, c} = l 29 BOne{b} 30 31 # It forks nothing, so the runtime runs it once the tree has grown, on any 32 # idle thread; work done before a fork runs while the tree grows, on a few 33 # threads. 34 def block_leaf(+s: U32, +e: U32, c: G.Cols) -> Blocks: 35 G.Cols{ys, lefts, rights} = c 36 block_of(G.block_pass(U32.to_nat((e - s : U32)), s, Array.get(F32, ys, s), lefts, rights)) 37 38 def block_tree(depth: Nat, +s: U32, +e: U32, cc: G.Cols & G.Cols) -> Blocks: 39 match depth: 40 case 1n++d: 41 (c1, c2) = cc 42 +mid = (s + U32.shr((e - s : U32)) : U32) 43 x y = block_tree(d, s, mid, fork_cols(c1)) block_tree(d, mid, e, fork_cols(c2)) 44 BJoin{x, y} 45 case 0n: 46 (c1, c2) = cc 47 +mid = (s + U32.shr((e - s : U32)) : U32) 48 x y = block_leaf(s, mid, c1) block_leaf(mid, e, c2) 49 BJoin{x, y} 50 51 def merge(bs: Blocks, m: G.Merged) -> G.Merged: 52 match bs: 53 case BOne{b}: 54 G.merge_block(b, m) 55 case BJoin{a, b}: 56 merge(b, merge(a, m)) 57 58 type Chunks is Data: 59 CNil{} 60 CCon{start: U32, count: U32, next: Chunks} 61 62 def close(full: Bool, +start: U32, +end: U32, cs: Chunks) -> Chunks: 63 match full: 64 case True{}: 65 CCon{start, (end - start : U32), cs} 66 case False{}: 67 cs 68 69 type Cut is Type: 70 Cut{lefts: Array, rights: Array, cs: Chunks, m: U32} 71 72 def cut(count: Nat, +i: U32, lr: Array & U32, rr: Array & U32, +start: U32, +acc: U32, +target: U32, cs: Chunks, +m: U32) -> Cut: 73 match count: 74 case 0n: 75 (lefts, l) = lr 76 (rights, r) = rr 77 +last = U32.is_lt(start, i) 78 Cut{lefts, rights, close(last, start, i, cs), G.pick_u32(last, (m + 1 : U32), m)} 79 case 1n+c: 80 (lefts, +l) = lr 81 (rights, +r) = rr 82 +w = (acc + l + r + 1 : U32) 83 +full = U32.is_ge(w, target) 84 +i2 = (i + 1 : U32) 85 cut(c, i2, Array.get(U32, lefts, i2), Array.get(U32, rights, i2), G.pick_u32(full, i2, start), G.pick_u32(full, 0, w), target, close(full, start, i2, cs), G.pick_u32(full, (m + 1 : U32), m)) 86 87 def fork_depth() -> Nat: 88 8n 89 90 # At most 512 blocks, and at least 32 points in each unless n is below 64. 91 def block_depth(+n: U32) -> Nat: 92 Nat.min(fork_depth(), U32.log2(U32.shrn(n, 6n))) 93 94 # About two chunks for each of the tree's leaves. 95 def target(+visits: F32) -> U32: 96 U32.max(1, F32.to_u32(F32.div(visits, U32.to_f32(U32.shln(4, fork_depth()))))) 97 98 type Halves is Data: 99 Halves{a: Chunks, na: U32, b: Chunks, nb: U32} 100 101 def halve(k: Nat, cs: Chunks, +na: U32, +total: U32, acc: Chunks) -> Halves: 102 match k cs: 103 case 1n+q CCon{+start, +count, next}: 104 halve(q, next, na, total, CCon{start, count, acc}) 105 case _ _: 106 Halves{acc, na, cs, (total - na : U32)} 107 108 def halves(cs: Chunks, +m: U32) -> Halves: 109 halve(U32.to_nat(U32.shr(m)), cs, U32.shr(m), m, CNil{}) 110 111 def chunks(cs: Chunks, o: G.Out, +index: Bool, +g: G.Graph, +dir: G.Direction, +k: G.Weight, +lo: F32, +hi: F32) -> G.Out: 112 match cs: 113 case CCon{+start, count, next}: 114 G.Out{cols, xs, es} = o 115 G.Cols{ys, lefts, rights} = cols 116 chunks(next, G.points(U32.to_nat(count), start, Array.get(U32, lefts, start), Array.get(U32, rights, start), G.Walked{Array.get(F32, ys, start), Array.get(F32, xs, start), es}, index, g, dir, k, lo, hi), index, g, dir, k, lo, hi) 117 case CNil{}: 118 o 119 120 def leaf(cs: Chunks, c: G.Cols, xs: Array, +index: Bool, +g: G.Graph, +dir: G.Direction, +k: G.Weight, +lo: F32, +hi: F32) -> G.Edges: 121 G.edges_of(chunks(cs, G.Out{c, xs, G.ENil{}}, index, g, dir, k, lo, hi)) 122 123 def tree(depth: Nat, h: Halves, cc: G.Cols & G.Cols, xx: Array & Array, +index: Bool, +g: G.Graph, +dir: G.Direction, +k: G.Weight, +lo: F32, +hi: F32) -> G.Edges: 124 match depth h: 125 case 1n++d Halves{a, +na, b, +nb}: 126 (c1, c2) = cc 127 (x1, x2) = xx 128 x y = tree(d, halves(a, na), fork_cols(c1), Array.fork(F32, x1), index, g, dir, k, lo, hi) tree(d, halves(b, nb), fork_cols(c2), Array.fork(F32, x2), index, g, dir, k, lo, hi) 129 G.EJoin{x, y} 130 case _ Halves{a, na, b, nb}: 131 (c1, c2) = cc 132 (x1, x2) = xx 133 x y = leaf(a, c1, x1, index, g, dir, k, lo, hi) leaf(b, c2, x2, index, g, dir, k, lo, hi) 134 G.EJoin{x, y} 135 136 def split(+index: Bool, +g: G.Graph, +dir: G.Direction, +k: G.Weight, +lo: F32, +hi: F32, ys: Array, xs: Array, c: Cut) -> G.Edges: 137 Cut{lefts, rights, cs, +m} = c 138 tree(fork_depth(), halves(cs, m), fork_cols(G.Cols{ys, lefts, rights}), Array.fork(F32, xs), index, g, dir, k, lo, hi) 139 140 def cut_all(+index: Bool, +g: G.Graph, +dir: G.Direction, +k: G.Weight, +lo: F32, +hi: F32, +n: U32, ys: Array, xs: Array, lefts: Array, r: Array & F32) -> G.Edges: 141 (rights, +visits) = r 142 split(index, g, dir, k, lo, hi, ys, xs, cut(U32.to_nat(n), 0, Array.get(U32, lefts, 0), Array.get(U32, rights, 0), 0, 0, target(visits), CNil{}, 0)) 143 144 def merged(+index: Bool, +g: G.Graph, +dir: G.Direction, +k: G.Weight, +lo: F32, +hi: F32, +n: U32, ys: Array, xs: Array, m: G.Merged) -> G.Edges: 145 G.Merged{st, lefts, rights, +visits} = m 146 cut_all(index, g, dir, k, lo, hi, n, ys, xs, lefts, G.flush(st, n, rights, visits)) 147 148 def passed(+index: Bool, +g: G.Graph, +dir: G.Direction, +k: G.Weight, +lo: F32, +hi: F32, +n: U32, xs: Array, cc: G.Cols & G.Cols) -> G.Edges: 149 (c1, c2) = cc 150 G.Cols{ys, lefts, rights} = c2 151 merged(index, g, dir, k, lo, hi, n, ys, xs, merge(block_tree(block_depth(n), 0, n, fork_cols(c1)), G.Merged{G.KNil{}, lefts, rights, 0.0})) 152 153 def built(+index: Bool, +g: G.Graph, +dir: G.Direction, +k: G.Weight, +lo: F32, +hi: F32, ys: Array, xs: Array, +n: U32) -> G.Edges: 154 passed(index, g, dir, k, lo, hi, n, xs, fork_cols(G.Cols{ys, G.counts(n), G.counts(n)})) 155 156 # G.build on every thread: the stack runs on blocks, then the sweeps on 157 # chunks of equal work. 158 def visibility(+g: G.Graph, +dir: G.Direction, +k: G.Weight, +lo: F32, +hi: F32, ys: Array, xs: G.Xs, +n: U32) -> G.Edges: 159 match xs: 160 case G.Index{}: 161 built(True{}, g, dir, k, lo, hi, ys, G.no_xs(), n) 162 case G.At{a}: 163 built(False{}, g, dir, k, lo, hi, ys, a, n) 164 165 def chosen(is_visibility: Bool, +g: G.Graph, +dir: G.Direction, +k: G.Weight, +lo: F32, +hi: F32, +limit: U32, ys: Array, xs: G.Xs, +n: U32) -> G.Edges: 166 match is_visibility: 167 case True{}: 168 visibility(g, dir, k, lo, hi, ys, xs, n) 169 case False{}: 170 P.build(g, dir, k, lo, hi, limit, ys, xs, n) 171 172 # VG.build on every thread. 173 def build(o: VG.Options, s: VG.Series) -> G.Edges: 174 VG.Options{g, dir, k, lo, hi, +limit} = o 175 VG.Series{+n, ys, xs} = s 176 chosen(U32.is_zero(limit), g, dir, k, lo, hi, limit, ys, xs, n) 177 178 # Forks down the build's tree of EJoin into Report.degrees, which 179 # forks nothing, so the runtime spreads the tallies over every thread. 180 def degrees_tree(depth: Nat, es: G.Edges, dd: Array & Array) -> Array: 181 match depth es: 182 case 1n++p G.EJoin{a, b}: 183 (d1, d2) = dd 184 x y = degrees_tree(p, a, Array.fork(U32, d1)) degrees_tree(p, b, Array.fork(U32, d2)) 185 Array.join(U32, x, y) 186 case 0n G.EJoin{a, b}: 187 (d1, d2) = dd 188 x y = Report.degrees(a, d1) Report.degrees(b, d2) 189 Array.join(U32, x, y) 190 case _ _: 191 (d1, d2) = dd 192 Report.degrees(es, Array.join(U32, d1, d2)) 193 194 # VG.degrees on every thread. 195 def degrees(es: G.Edges, +n: U32) -> Array: 196 degrees_tree(fork_depth(), es, Array.fork(U32, Report.slots(n)))