Loop-level parallelism: Difference between revisions

Revision as of 00:37, 4 August 2021

Revision as of 10:23, 19 March 2022

Line 169:

}

</pre>

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>Ts1T_{S_1}</math> and <math>Ts2T_{S_2}

</math> then the execution time for sequential form of above code is <math>n*(Ts1T_{S_1}+Ts2T_{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*Ts1T_{S_1} + Ts2T_{S_2}</math>. We call this type of parallelism either function or task parallelism.

=== DOALL parallelism ===

Line 182:

</pre>

Let's say the time of one execution of S1 be <math>Ts1T_{S_1}</math> then the execution time for sequential form of above code is <math>n*Ts1T_{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>Ts1T_{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.

Line 231:

post(i);

}

</pre>Let's say the time of execution of S1 and S2 be <math>Ts1T_{S_1}</math> and <math>Ts2T_{S_2}

</math> then the execution time for sequential form of above code is <math>n*(Ts1T_{S_1}+Ts2T_{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>Ts1T_{S_1} + n*Ts2T_{S_2}</math>.

=== DOPIPE parallelism ===

Line 262:

}

</pre>

Let's say the time of execution of S1 and S2 be <math>Ts1T_{S_1}</math> and <math>Ts2T_{S_2}

</math> then the execution time for sequential form of above code is <math>n*(Ts1T_{S_1}+Ts2T_{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*Ts1T_{S_1} + (n/p)*Ts2T_{S_2}</math>, where {{mvar|p}} is the number of processor in parallel.

== See also ==