src/parallel.bend
bend-visgraph@1.0.1.0 · 196 lines · 0 definitions
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.
5import Base
6import bend-visgraph@1.0.1.0/src/graph.bend as G
7import bend-visgraph@1.0.1.0/src/penetrable.bend as P
8import bend-visgraph@1.0.1.0/src/report.bend as Report
9import bend-visgraph@1.0.1.0/src/vg.bend as VG
10
11def fork3(a: Array<F32> & Array<F32>, b: Array<U32> & Array<U32>, c: Array<U32> & Array<U32>) -> 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
17def 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.
23type Blocks is Data:
24 BOne{b: G.Block}
25 BJoin{a: Blocks, b: Blocks}
26
27def 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.
34def 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
38def 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
51def 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
58type Chunks is Data:
59 CNil{}
60 CCon{start: U32, count: U32, next: Chunks}
61
62def 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
69type Cut is Type:
70 Cut{lefts: Array<U32>, rights: Array<U32>, cs: Chunks, m: U32}
71
72def cut(count: Nat, +i: U32, lr: Array<U32> & U32, rr: Array<U32> & 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
87def fork_depth() -> Nat:
88 8n
89
90# At most 512 blocks, and at least 32 points in each unless n is below 64.
91def 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.
95def target(+visits: F32) -> U32:
96 U32.max(1, F32.to_u32(F32.div(visits, U32.to_f32(U32.shln(4, fork_depth())))))
97
98type Halves is Data:
99 Halves{a: Chunks, na: U32, b: Chunks, nb: U32}
100
101def 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
108def halves(cs: Chunks, +m: U32) -> Halves:
109 halve(U32.to_nat(U32.shr(m)), cs, U32.shr(m), m, CNil{})
110
111def 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
120def leaf(cs: Chunks, c: G.Cols, xs: Array<F32>, +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
123def tree(depth: Nat, h: Halves, cc: G.Cols & G.Cols, xx: Array<F32> & Array<F32>, +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
136def split(+index: Bool, +g: G.Graph, +dir: G.Direction, +k: G.Weight, +lo: F32, +hi: F32, ys: Array<F32>, xs: Array<F32>, 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
140def cut_all(+index: Bool, +g: G.Graph, +dir: G.Direction, +k: G.Weight, +lo: F32, +hi: F32, +n: U32, ys: Array<F32>, xs: Array<F32>, lefts: Array<U32>, r: Array<U32> & 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
144def merged(+index: Bool, +g: G.Graph, +dir: G.Direction, +k: G.Weight, +lo: F32, +hi: F32, +n: U32, ys: Array<F32>, xs: Array<F32>, 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
148def passed(+index: Bool, +g: G.Graph, +dir: G.Direction, +k: G.Weight, +lo: F32, +hi: F32, +n: U32, xs: Array<F32>, 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
153def built(+index: Bool, +g: G.Graph, +dir: G.Direction, +k: G.Weight, +lo: F32, +hi: F32, ys: Array<F32>, xs: Array<F32>, +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.
158def visibility(+g: G.Graph, +dir: G.Direction, +k: G.Weight, +lo: F32, +hi: F32, ys: Array<F32>, 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
165def chosen(is_visibility: Bool, +g: G.Graph, +dir: G.Direction, +k: G.Weight, +lo: F32, +hi: F32, +limit: U32, ys: Array<F32>, 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.
173def 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.
180def degrees_tree(depth: Nat, es: G.Edges, dd: Array<U32> & Array<U32>) -> Array<U32>:
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.
195def degrees(es: G.Edges, +n: U32) -> Array<U32>:
196 degrees_tree(fork_depth(), es, Array.fork(U32, Report.slots(n)))