Loop-level parallelism

Loop-level parallelism is a form of parallelism in software programming that is concerned with extracting parallel tasks from 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 threads or 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.

Loop-level parallelism is a form of parallelism in software programming that is concerned with extracting parallel tasks from 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 threads or 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. Consider the following code operating on a list l , where l.size() == n . for (int i = 0; i Each iteration of the loop takes the value from the current index of l , and increments it by 10. If statement s1 takes T time to execute, then the loop takes time n * T to execute sequentially, ignoring time taken by loop constructs. Now, consider a system with p processors where p > n . If n threads run in parallel, the time to execute all n steps is reduced to T . Less simple cases produce inconsistent, i.e. non-serializable outcomes. Consider the following loop operating on the same list l . for (int i = 0; i Each iteration sets the current index to be the value of the previous plus ten. When run sequentially, each iteration is guaranteed that the previous iteration will already have the correct value. With multiple threads, process scheduling and other considerations prevent the execution order from guaranteeing an iteration will execute only after its dependence is met. It very well may happen before, leading to unexpected results. Serializability can be restored by adding synchronization to preserve the dependence on previous iterations. The first line, int tmp = b[i] + 1; , has no loop-carried dependence. The loop can then be parallelized by computing the temp value in parallel, and then synchronizing the assignment to a[i] . Let's say the time of execution of s1 and s2 be T_{s_1} and T_{s_2} then the execution time for sequential form of above code is n \cdot (T_{s_1} + T_{s_2}) , Now because DOACROSS Parallelism exists, speed-up may be achieved by executing iterations in a pipelined fashion which gives us an execution time of T_{s_1} + n \cdot T_{s_2} .

Text derived from https://en.wikipedia.org/w/index.php?oldid=1318035675 under CC BY-SA 4.0; modifications have been made.