Scalable parallelism

Software is said to exhibit scalable parallelism if it can make use of additional processors to solve larger problems,
i.e. this term refers to software for which <a href="/facts/Gustafson%2527s_law/7z2S6dXb">Gustafson's law</a> holds.
Consider a program whose execution time is dominated by one or more loops,
each of that updates every element of an array ---
for example, the following <a href="/facts/Finite_difference_method/EoG81Qn9">finite difference</a> <a href="/facts/Heat_equation/2JPPr5GG">heat equation</a> <a href="/facts/Stencil_(numerical_analysis)/rNIq2e37">stencil calculation</a>:

for t := 0 to T do
 for i := 1 to N-1 do
 new(i) := (A(i-1) + A(i) + A(i) + A(i+1)) * .25
 // explicit forward-difference with R = 0.25
 end
 for i := 1 to N-1 do
 A(i) := new(i)
 end
end

In the above code, we can execute all iterations of each "i" loop concurrently,
i.e., turn each into a <a href="/facts/Data_parallelism/SkYoL91S">parallel loop</a>.
In such cases,
it is often possible to make effective use of twice as many processors for a problem of array size 2N
as for a problem of array size N.
As in this example, scalable parallelism is typically a form of <a href="/facts/Data_parallelism/SkYoL91S">data parallelism</a>.
This form of parallelism is often the target of <a href="/facts/Automatic_parallelization/t40BDoWG">automatic parallelization</a> of <a href="/facts/Loop_optimization/2eFKIg32">loops</a>.
<a href="/facts/Distributed_computing/o5nyhqTF">Distributed computing systems</a> and <a href="/facts/Non-uniform_memory_access/MpmN5mN0">non-uniform memory access</a> architectures
are typically the most easily scaled to large numbers of processors,
and thus would seem a natural target for software that exhibits scalable parallelism.
However, applications with scalable parallelism may not have parallelism of
sufficiently <a href="/facts/Parallel_computing/nQzcpzQt">coarse grain</a>
to run effectively on such systems (unless the software is <a href="/facts/Embarrassingly_parallel/phT66Up4">embarrassingly parallel</a>).
In our example above, the second "i" loop is embarrassingly parallel,
but in the first loop each iteration requires results produced in several prior iterations.
Thus, for the first loop, parallelization may involve extensive communication or synchronization among processors,
and thus only result in a net speedup if such interactions have very low overhead,
or if the code can be transformed to resolve this issue (i.e., by combined <a href="/facts/Scalable_locality/FIN7tWDH">scalable locality</a>/scalable parallelism optimization).

Scalable parallelism open-in-new

Scalable parallelism