Content deleted Content added
m →Types: subscript |
m {{sxhl|lang=c}} |
||
Line 8:
Consider the following code operating on a list <code>L</code> of length <code>n</code>.
{{sxhl|lang=c|1=
for (int i = 0; i < n;
S1: L[i] = L[i] + 10;
}
}}
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>.
Line 18:
Less simple cases produce inconsistent, i.e. [[serializability|non-serializable]] outcomes. Consider the following loop operating on the same list <code>L</code>.
{{sxhl|lang=c|1=
for (int i = 1; i < n;
S1: L[i] = L[i
}
}}
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.
Line 56:
=== Example of true dependence ===
{{sxhl|lang=c|1=
S1: int a, b;
S2: a = 2;
S3: b = a + 40;
}}
<code>S2 ->T S3</code>, meaning that S2 has a true dependence on S3 because S2 writes to the variable <code>a</code>, which S3 reads from.
=== Example of anti-dependence ===
{{sxhl|lang=c|1=
S1: int a, b = 40;
S2: a = b - 38;
S3: b = -1;
}}
<code>S2 ->A S3</code>, meaning that S2 has an anti-dependence on S3 because S2 reads from the variable <code>b</code> before S3 writes to it.
=== Example of output-dependence ===
{{sxhl|lang=c|1=
S1: int a, b = 40;
S2: a = b - 38;
S3: a = 2;
}}
<code>S2 ->O S3</code>, meaning that S2 has an output dependence on S3 because both write to the variable <code>a</code>.
=== Example of input-dependence ===
{{sxhl|lang=c|1=
S1: int a, b, c = 2;
S2: a = c - 1;
S3: b = c + 1;
}}
<code>S2 ->I S3</code>, meaning that S2 has an input dependence on S3 because S2 and S3 both read from variable <code>c</code>.
Line 99:
In the following example code used for swapping the values of two array of length n, there is a loop-independent dependence of <code>S1 ->T S3</code>.
{{sxhl|lang=c|1=
for (int i = 1; i < n;
S1: tmp = a[i];
S2: a[i] = b[i];
S3: b[i] = tmp;
}
}}
In loop-carried dependence, statements in an iteration of a loop depend on statements in another iteration of the loop. Loop-Carried Dependence uses a modified version of the dependence notation seen earlier.
Example of loop-carried dependence where <code>S1[i] ->T S1[i + 1]</code>, where <code>i</code> indicates the current iteration, and <code>i + 1</code> indicates the next iteration.
{{sxhl|lang=c|1=
for (int i = 1; i < n;
S1: a[i] = a[i
}
}}
=== Loop carried dependence graph ===
Line 154:
=== DISTRIBUTED loop ===
When a loop has a loop-carried dependence, one way to parallelize it is to distribute the loop into several different loops. Statements that are not dependent on each other are separated so that these distributed loops can be executed in parallel. For example, consider the following code.
{{sxhl|lang=c|1=
for (int i = 1; i < n;
S1: a[i] = a[i
S2: c[i] = c[i] + d[i];
}
}}
The loop has a loop carried dependence <code>S1[i] ->T S1[i
{{sxhl|lang=c|1=
loop1: for (int i = 1; i < n;
S1: a[i] = a[i
}
loop2: for (int i = 1; i < n;
S2: c[i] = c[i] + d[i];
}
}}
Note that now loop1 and loop2 can be executed in parallel. Instead of single instruction being performed in parallel on different data as in data level parallelism, here different loops perform different tasks on different data. Let's say the time of execution of S1 and S2 be <math>T_{S_1}</math> and <math>T_{S_2}
</math> then the execution time for sequential form of above code is <math>n*(T_{S_1}+T_{S_2})</math>, Now because we split the two statements and put them in two different loops, gives us an execution time of <math>n*T_{S_1} + T_{S_2}</math>. We call this type of parallelism either function or task parallelism.
Line 176:
DOALL parallelism exists when statements within a loop can be executed independently (situations where there is no loop-carried dependence).<ref name="Solihin" /> For example, the following code does not read from the array <code>a</code>, and does not update the arrays <code>b, c</code>. No iterations have a dependence on any other iteration.
{{sxhl|lang=c|1=
for (int i = 0; i < n;
S1: a[i] = b[i] + c[i];
}
}}
Let's say the time of one execution of S1 be <math>T_{S_1}</math> then the execution time for sequential form of above code is <math>n*T_{S_1}</math>, Now because DOALL Parallelism exists when all iterations are independent, speed-up may be achieved by executing all iterations in parallel which gives us an execution time of <math>T_{S_1}</math>, which is the time taken for one iteration in sequential execution.
The following example, using a simplified pseudo code, shows how a loop might be parallelized to execute each iteration independently.
{{sxhl|lang=c|1=
begin_parallelism();
for (int i = 0; i < n;
S1: a[i] = b[i] + c[i];
end_parallelism();
}
block();
}}
=== DOACROSS parallelism ===
Line 200:
Synchronization exists to enforce loop-carried dependence.
Consider the following, synchronous loop with dependence <code>S1[i] ->T S1[i
{{sxhl|lang=c|1=
for (int i = 1; i < n;
a[i] = a[i
}
}}
Each loop iteration performs two actions
* Calculate <code>a[i
* Assign the value to <code>a[i]</code>
Calculating the value <code>a[i
{{sxhl|lang=c|1=
S1: int tmp = b[i] + 1;
S2: a[i] = a[i - 1] + tmp;
}}
The first line, <code>int tmp = b[i] + 1;</code>, has no loop-carried dependence. The loop can then be parallelized by computing the temp value in parallel, and then synchronizing the assignment to <code>a[i]</code>.
{{sxhl|lang=c|1=
post(0);
for (int i = 1; i < n;
S1: int tmp = b[i] + 1;
wait(i
S2: a[i] = a[i
post(i);
}
}}
</math> then the execution time for sequential form of above code is <math>n*(T_{S_1}+T_{S_2})</math>, Now because DOACROSS Parallelism exists, speed-up may be achieved by executing iterations in a pipelined fashion which gives us an execution time of <math>T_{S_1} + n*T_{S_2}</math>.
Line 238 ⟶ 239:
DOPIPE Parallelism implements pipelined parallelism for loop-carried dependence where a loop iteration is distributed over multiple, synchronized loops.<ref name="Solihin" /> The goal of DOPIPE is to act like an assembly line, where one stage is started as soon as there is sufficient data available for it from the previous stage.<ref>{{cite web|title=DoPipe: An Effective Approach to Parallelize Simulation|url=https://software.intel.com/sites/default/files/m/a/a/7/d/6/12758-MC_Forum_Zangbinyu_dopipe.pdf|website=Intel|accessdate=13 September 2016}}</ref>
Consider the following, synchronous code with dependence <code>S1[i] ->T S1[i
{{sxhl|lang=c|1=
for (int i = 1; i < n;
S1: a[i] = a[i
S2: c[i] = c[i] + a[i];
}
}}
S1 must be executed sequentially, but S2 has no loop-carried dependence. S2 could be executed in parallel using DOALL Parallelism after performing all calculations needed by S1 in series. However, the speedup is limited if this is done. A better approach is to parallelize such that the S2 corresponding to each S1 executes when said S1 is finished.
Line 251 ⟶ 252:
Implementing pipelined parallelism results in the following set of loops, where the second loop may execute for an index as soon as the first loop has finished its corresponding index.
{{sxhl|lang=c|1=
for (int i = 1; i < n;
S1: a[i] = a[i
post(i);
}
Line 261 ⟶ 262:
S2: c[i] = c[i] + a[i];
}
}}
Let's say the time of execution of S1 and S2 be <math>T_{S_1}</math> and <math>T_{S_2}
</math> then the execution time for sequential form of above code is <math>n*(T_{S_1}+T_{S_2})</math>, Now because DOPIPE Parallelism exists, speed-up may be achieved by executing iterations in a pipelined fashion which gives us an execution time of <math>n*T_{S_1} + (n/p)*T_{S_2}</math>, where {{mvar|p}} is the number of processor in parallel.
| |||