Loop-level parallelism: Difference between revisions

Revision as of 03:35, 27 November 2016

Revision as of 14:25, 16 January 2019

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 journal|last1=Goff|first1=Gina|title=Practical dependence testing|journal=SIGPLANSigplan|url=http://delivery.acm.org/10.1145/120000/113448/p15-goff.pdf?ip=152.7.224.7&id=113448&acc=ACTIVE%20SERVICE&key=6ABC8B4C00F6EE47%2E4D4702B0C3E38B35%2E4D4702B0C3E38B35%2E4D4702B0C3E38B35&CFID=667494229&CFTOKEN=16697834&__acm__=1473798493_e58dcb18e741b6e6ac1c1c728fc5508d|accessdate=13 September 2016|doi=10.1145/120000/113448/p15-goff|doi-broken-date=2019-01-16}}</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|accessdate=13 September 2016|ref=https://www.researchgate.net/publication/220662641_Parallelization_of_DOALL_and_DOACROSS_Loops-a_Survey}}</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 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>{{cite bookcitation|last1=Unnikrishnan|first1=Priya|title=AEuro-Par Practical2012 ApproachParallel to DOACROSS ParallelizationProcessing|volume=7484|pages=219–231|urldoi=http://download10.springer.com1007/static/pdf/647/chp%253A10.1007%252F978978-3-642-32820-6_23.pdf?originUrl|series=http%3A%2F%2Flink.springer.com%2Fchapter%2F10.1007%2F978-3-642-32820-6_23&token2Lecture Notes in Computer Science|year=exp2012|isbn=1473797903~acl=%2Fstatic%2Fpdf%2F647%2Fchp%25253A10.1007%25252F978978-3-642-3282032819-6_23.pdf%3ForiginUrl%3Dhttp%253A%252F%252Flink.springer.com%252Fchapter%252F10.1007%252F978-3-642-32820-6_23*~hmac=254f4a4ae181734da221ce06bcdb03ef232f25531eaf1195c6e1988a33b9d2590|accessdatechapter=13A SeptemberPractical 2016Approach to DOACROSS Parallelization}}</ref>

Synchronization exists to enforce loop-carried dependence.