Loop-level parallelism: Difference between revisions

Revision as of 11:10, 16 September 2016

Revision as of 18:28, 3 October 2016

Line 55:

In order to preserve the sequential behaviour of a loop when run in parallel, True Dependence must be preserved. Anti-Dependence and Output Dependence can be dealt with by giving each process its own copy of variables (known as privatization).<ref name="Solihin" />

=== Example of Truetrue Dependencedependence ===

<source>

S1: int a, b;

Line 63:

<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 Antianti-dependence ===

<source>

S1: int a, b = 40;

Line 71:

<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 Outputoutput-dependence ===

<source>

S1: int a, b = 40;

Line 79:

<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 Inputinput-dependence ===

<source>

S1: int a, b, c = 2;

Line 120:

A Loop-carried dependence graph graphically shows the loop-carried dependencies between iterations. Each iteration is listed as a node on the graph, and directed edges show the true, anti, and output dependencies between each iteration.

== Types of Loop-level parallelism ==

There are a variety of methodologies for parallelizing loops.