StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<blockquote> <p>1-A sequence of kernel invocations is bulk- synchronous: each kernel is initially presented with a consistent view of the results from the previous.</p> </blockquote> <p>It's about parallel computation model: each processor has its own memory which is fast (like cache in CPU) and is performing computation using values stored there without any synchronization. Then non-blocking synchronization takes place - processor puts data it has computed so far and gets data from its neighbours. Then there's another synchronization - barrier, which makes all of them wait for each other.</p> <blockquote> <p>2-Prefix-sum is a bulk-synchronous algorithmic primitive</p> </blockquote> <p>I believe that's about the second step of BSP model - synchronization. That's the way processors store and get data for the next step.</p> <p>Name of the model implies that it is highly concurrent (many many processes that work synchronously relatively to each other). And this is how we get to the second point.</p> <p>As far as we want to live up to the name (be highly concurrent) we want get rid of sequential parts where it is possible. We can achieve that with prefix-sum.</p> <p>Consider prefix-sum associative operator <code>+</code>. Then scan on set <code>[5 2 0 3 1]</code> returns the set <code>[0 5 7 7 10 11]</code>. So, now we can replace such sequential pseudocode:</p> <pre><code>foreach i = 1...n foo[i] = foo[i-1] + bar(i); </code></pre> <p>with this pseudocode, which now can be parallel(!):</p> <pre><code>foreach(i) baz[i] = bar(i); scan(foo, baz); </code></pre> <p>That is very much naive version, but it's okay for explanation.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload