Parallel Computing for Data Science

238 CHAPTER 11. PREFIX SCAN

and wish to compute a sum scan, i.e., cumulative sums. Suppose we have

three threads. We break the data into three sections,

2 25 26 8 50 3 1 11 7 9 29 10

and then apply a scan to each section:

2 27 53 61 50 53 54 65 7 16 45 55

But we still don’t have the scan of the array overall. That 50, for instance,

should be 61+50 = 111 and the 53 should be 61+53 = 114. In other words,

61 must be added to that second section, (50,53,54,65), and 61+65 = 126

must be added to the third section, (7,16,45,55). This then is the last step,

yielding

2 27 53 61 111 114 115 126 133 142 171 181

11.4 Implementations of Parallel Prefix Scan

The abov