Can't quite understand what's going on under the horizontal black bar. Can someone explain please?
machine6
The operations above the horizontal bar is known as the upsweep phase. At each row, it just keeps summing pairs that are 1 jump away, then in the next row it sums pairs that are 2 jumps away, then 4 jumps away, and so on.
The stuff below the bar is the downsweep phase, where you perform a bunch of downsweep operations. The downsweep function basically works on 2 indices i and j.
dwsweep(i,j,A) does two things:
Does A[j] = A[i] + A[j].
Sets A[i] = old_A[j].
(The dotted lines in the slide represent (2) and the solid lines (1)).
In this phase, you keep using the downsweep function on elements that are 8 hops away (in the above case as N = 16), then 4 hops away, then 2 hops, and so on.
For instance, in the very first row, there's downsweep(7, 15), see?
You keep doing that until you downsweep all elements that are 1 hop away, at which point you have all the prefix sums.
Can't quite understand what's going on under the horizontal black bar. Can someone explain please?
The operations above the horizontal bar is known as the upsweep phase. At each row, it just keeps summing pairs that are 1 jump away, then in the next row it sums pairs that are 2 jumps away, then 4 jumps away, and so on.
The stuff below the bar is the downsweep phase, where you perform a bunch of downsweep operations. The downsweep function basically works on 2 indices i and j.
dwsweep(i,j,A)does two things:Does
A[j] = A[i] + A[j].Sets
A[i] = old_A[j].(The dotted lines in the slide represent (2) and the solid lines (1)).
In this phase, you keep using the downsweep function on elements that are 8 hops away (in the above case as N = 16), then 4 hops away, then 2 hops, and so on. For instance, in the very first row, there's
downsweep(7, 15), see? You keep doing that until you downsweep all elements that are 1 hop away, at which point you have all the prefix sums.Does this make sense? Corrections are welcome.