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 (Admin))
July 24, 2017, 5:11pm
#3