Loop-level parallelism: Difference between revisions

Revision as of 21:32, 15 September 2016

Revision as of 21:39, 15 September 2016

Line 6:

== Example ==

For example, considerConsider the following code operating on a list <code>L</code> of length <code>n</code>.

<source>

Line 15:

Each iteration of the loop takes the value from the current index of <code>L</code>, and increments it by 10. If statement <code>S1</code> takes <code>T</code> time to execute, then the loop takes time <code>n * T</code> to execute sequentially, ignoring time taken by loop constructs. Now, consider a system with <code>p</code> processors where <code>p > n</code>. If <code>n</code> threads run in parallel, the time to execute all <code>n</code> steps is reduced to <code>T</code>.

Less simple cases produce inconsistent, i.e. [[serializability|non-serializable]] outcomes. Consider the following loop operating on the same list <code>L</code>.

<source>

for (int i = 0; i < n; i++) {

S1: L[i] = L[i - 1] + 10;

}

</source>

Each iteration sets the current index to be the value of the previous plus ten. When run sequentially, each iteration is guaranteed that the previous iteration will already have the correct value. With multiple threads, [[process scheduling]] and other considerations prevent the execution order from guaranteeing an iteration will execute only after its dependence is met. It very well may happen before, leading to unexpected results. Serializability can be restored by adding synchronization to preserve the dependence on previous iterations.

== Dependencies in code ==