Loop-level parallelism: Difference between revisions

Revision as of 01:28, 16 September 2016

Revision as of 05:51, 16 September 2016

Line 1:

'''Loop-level parallelism''' is a form of [[parallelism (computing)|parallelism]] in [[software programming]] that is concerned with extracting parallel tasks from [[Control_flowControl flow#Loops|loops]]. The opportunity for loop-level parallelism often arises in computing programs where data is stored in [[random access]] [[data structures]]. Where a sequential program will iterate over the data structure and operate on indices one at a time, a program exploiting loop-level parallelism will use multiple [[thread (computing)|threads ]] or [[process (computing)|processes]] which operate on some or all of the indices at the same time. Such parallelism provides a [[speedup]] to overall execution time of the program, typically in line with [[Amdahl's law]].

== Description ==

Line 53:

|}

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 True Dependence ===

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 book|last1=Unnikrishnan|first1=Priya|title=A Practical Approach to DOACROSS Parallelization|pages=219–231|url=http://download.springer.com/static/pdf/647/chp%253A10.1007%252F978-3-642-32820-6_23.pdf?originUrl=http%3A%2F%2Flink.springer.com%2Fchapter%2F10.1007%2F978-3-642-32820-6_23&token2=exp=1473797903~acl=%2Fstatic%2Fpdf%2F647%2Fchp%25253A10.1007%25252F978-3-642-32820-6_23.pdf%3ForiginUrl%3Dhttp%253A%252F%252Flink.springer.com%252Fchapter%252F10.1007%252F978-3-642-32820-6_23*~hmac=254f4a4ae181734da221ce06bcdb03ef232f25531eaf1195c6e1988a33b9d259|accessdate=13 September 2016}}</ref>.

Synchronization exists to enforce loop-carried dependence.