Loop-level parallelism: Difference between revisions

Revision as of 07:22, 24 March 2022

Latest revision as of 00:27, 2 May 2024

(5 intermediate revisions by 4 users not shown)

Line 10:

{{sxhl|lang=c|1=

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

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

}

}}

Line 28:

== Dependencies in code ==

There are several types of dependences that can be found within code.<ref name="Solihin">{{cite book|last1=Solihin|first1=Yan|title=Fundamentals of Parallel Architecture|date=2016|publisher=CRC Press|___location=Boca Raton, FL|isbn=978-1-4822-1118-4}}</ref><ref>{{cite book|last1=Goff|first1=Gina|title=Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation - PLDI '91|pages=15–29|chapter=Practical dependence testing|doi=10.1145/113445.113448|year=1991|isbn=0897914287|s2cid=2357293 }}</ref>

{| class="wikitable"

Line 130:

* DOPIPE Parallelism

Each implementation varies slightly in how threads synchronize, if at all. In addition, parallel tasks must somehow be mapped to a process. These tasks can either be allocated statically or dynamically. Research has shown that load-balancing can be better achieved through some dynamic allocation algorithms than when done statically.<ref>{{cite journal|last1=Kavi|first1=Krishna|title=Parallelization of DOALL and DOACROSS Loops-a Survey|refurl=https://www.researchgate.net/publication/220662641_Parallelization_of_DOALL_and_DOACROSS_Loops-a_Survey220662641}}</ref>

The process of parallelizing a sequential program can be broken down into the following discrete steps.<ref name="Solihin" /> Each concrete loop-parallelization below implicitly performs them.

Line 157:

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

S1: a[i] = a[i-1] + b[i];

S2: c[i] = c[i] += d[i];

}

}}

Line 166:

}

loop2: for (int i = 1; i < n; ++i) {

S2: c[i] = c[i] += d[i];

}

}}

Line 196:

=== DOACROSS parallelism ===

DOACROSS Parallelism exists where iterations of a loop are parallelized by extracting calculations that can be performed independently and running them simultaneously.<ref>{{citation|last1=Unnikrishnan|first1=Priya|title=Euro-Par 2012 Parallel Processing|volume=7484|pages=219–231|doi=10.1007/978-3-642-32820-6_23|series=Lecture Notes in Computer Science|year=2012|isbn=978-3-642-32819-0|chapter=A Practical Approach to DOACROSS Parallelization|chapters2cid=18571258 |doi-urlaccess=https://semanticscholar.org/paper/0885cd07bc4affd8f433bd3b4ee56012101ae09afree}}</ref>

Synchronization exists to enforce loop-carried dependence.

Line 216:

{{sxhl|lang=c|1=

S1: int tmp = b[i] + 1;

S2: a[i] = a[i - 1] + tmp;

}}

Line 244:

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

S1: a[i] = a[i-1] + b[i];

S2: c[i] = c[i] += a[i];

}

}}

Line 260:

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

wait(i);

S2: c[i] = c[i] += a[i];

}

}}

Line 268:

== See also ==

* [[Data parallelism]]

* [[DOACROSS parallelism]]

* [[Task parallelism]]

* Parallelism using different types of memory models like [[Shared memory|shared]] and [[Distributed memory|distributed]] and [[Message Passing Interface|Message Passing]]