msp
July 19, 2017, 9:05am
1
In Lesson 6 of part 1, @jeremy mentioned that scan
could be implemented in parallel (also mentioning that it is a surprising and extraordinary result). I agree that it is surprising and extraordinary, and would love to have a reference to the paper.
Thanks!
msp
July 22, 2017, 9:42pm
2
There is some information here for the prefix sum example:
In computer science, the prefix sum, cumulative sum, inclusive scan, or simply scan of a sequence of numbers x0, x1, x2, ... is a second sequence of numbers y0, y1, y2, ..., the sums of prefixes (running totals) of the input sequence:
For instance, the prefix sums of the natural numbers are the triangular numbers:
Prefix sums are trivial to compute in sequential models of computation, by using the formula yi = yi − 1 + xi to compute each output value in sequence order. However, despite their ea...
In general if the operation is associative there is an efficient implementation:
jeremy
(Jeremy Howard)
July 24, 2017, 5:11pm
3