Introduction to Parallel Programming – Part 12
INTEL CONFIDENTIAL
Review & Objectives
Previously:
Use loop fusion, loop fission, and loop inversion to create or
improve opportunities for parallel execution
Explain why it can be difficult both to optimize load balancing
and maximize locality
At the end of this part you should be able to:
Explain the pros and cons of static versus
dynamic loop scheduling
Explain the different OpenMP schedule clauses and
the situations each one is best suited for
Intel and the Intel logo are trademarks or registered trademarks of Intel Corporation or its subsidiaries in the United States
or other countries. * Other brands and names are the property of their respective owners.
2
Loop scheduling
Replicating work
Intel and the Intel logo are trademarks or registered trademarks of Intel Corporation or its subsidiaries in the United States
or other countries. * Other brands and names are the property of their respective owners.
3
Loop Scheduling Example
for (i = 0; i < 12; i++)
for (j = 0; j <= i; j++)
a[i][j] = ...;
Intel and the Intel logo are trademarks or registered trademarks of Intel Corporation or its subsidiaries in the United States
or other countries. * Other brands and names are the property of their respective owners.
4
Loop Scheduling Example
#pragma omp parallel for
for (i = 0; i < 12; i++)
for (j = 0; j <= i; j++)
a[i][j] = ...;
How are the
iterations divided
Intel and the Intel logo are trademarks or registered trademarks of Intel Corporation or its subsidiaries in the United States
or other countries. * Other brands and names are the property of their respective owners.
5
Loop Scheduling Example
#pragma omp parallel for
for (i = 0; i < 12; i++)
for (j = 0; j <= i; j++)
a[i][j] = ...;
Typically, the
iterations are
divided by the
and assigned as
chunks to a thread
Intel and the Intel logo are trademarks or registered trademarks of Intel Corporation or its subsidiaries in the United States
or other countries. * Other brands and names are the property of their respective owners.
6
Loop Scheduling
Loop schedule: how loop iterations are assigned to
Static schedule: iterations assigned to threads before
execution of loop
Dynamic schedule: iterations assigned to threads
during execution of loop
The OpenMP schedule clause affects how loop
iterations are mapped onto threads
Intel and the Intel logo are trademarks or registered trademarks of Intel Corporation or its subsidiaries in the United States
or other countries. * Other brands and names are the property of their respective owners.
7
The schedule clause
schedule(static [,chunk])
• Blocks of iterations of size “chunk” to threads
• Round robin distribution
• Low overhead, may cause load imbalance
Best used for predictable and similar work per
iteration
Intel and the Intel logo are trademarks or registered trademarks of Intel Corporation or its subsidiaries in the United States
or other countries. * Other brands and names are the property of their respective owners.
8
Loop Scheduling Example
#pragma omp parallel for schedule(static, 2)
for (i = 0; i < 12; i++)
for (j = 0; j <= i; j++)
a[i][j] = ...;
Intel and the Intel logo are trademarks or registered trademarks of Intel Corporation or its subsidiaries in the United States
or other countries. * Other brands and names are the property of their respective owners.
9
The schedule clause
schedule(dynamic[,chunk])
• Threads grab “chunk” iterations
• When done with iterations, thread requests next set
Best used for unpredictable or highly variable work
per iteration
Intel and the Intel logo are trademarks or registered trademarks of Intel Corporation or its subsidiaries in the United States
or other countries. * Other brands and names are the property of their respective owners.
10
Loop Scheduling Example
#pragma omp parallel for schedule(dynamic, 2)
for (i = 0; i < 12; i++)
for (j = 0; j <= i; j++)
a[i][j] = ...;
Intel and the Intel logo are trademarks or registered trademarks of Intel Corporation or its subsidiaries in the United States
or other countries. * Other brands and names are the property of their respective owners.
11
The schedule clause
schedule(guided[,chunk])
• Dynamic schedule starting with large block
• Size of the blocks shrink; no smaller than “chunk”
Best used as a special case of dynamic to reduce
scheduling overhead when the computation gets
progressively more time consuming
Intel and the Intel logo are trademarks or registered trademarks of Intel Corporation or its subsidiaries in the United States
or other countries. * Other brands and names are the property of their respective owners.
12
Loop Scheduling Example
#pragma omp parallel for schedule(guided)
for (i = 0; i < 12; i++)
for (j = 0; j <= i; j++)
a[i][j] = ...;
Intel and the Intel logo are trademarks or registered trademarks of Intel Corporation or its subsidiaries in the United States
or other countries. * Other brands and names are the property of their respective owners.
13
Replicate Work
Every thread interaction has a cost
Example: Barrier synchronization
Sometimes it’s faster for threads to replicate work
than to go through a barrier synchronization
Intel and the Intel logo are trademarks or registered trademarks of Intel Corporation or its subsidiaries in the United States
or other countries. * Other brands and names are the property of their respective owners.
14
Before Work Replication
for (i = 0; i < N; i++) a[i] = foo(i);
x = a[0] / a[N-1];
for (i = 0; i < N; i++) b[i] = x * a[i];
Both for loops are amenable to parallelization
Intel and the Intel logo are trademarks or registered trademarks of Intel Corporation or its subsidiaries in the United States
or other countries. * Other brands and names are the property of their respective owners.
15
First OpenMP Attempt
#pragma omp parallel
{
#pragma omp for
for (i = 0; i < N; i++) a[i] = foo(i);
#pragma omp single
x = a[0] / a[N-1];
Implicit Barrier
#pragma omp for
for (i = 0; i < N; i++) b[i] = x * a[i];
}
Synchronization among threads required if x is
shared and one thread performs assignment
Intel and the Intel logo are trademarks or registered trademarks of Intel Corporation or its subsidiaries in the United States
or other countries. * Other brands and names are the property of their respective owners.
16
After Work Replication
#pragma omp parallel private (x)
{
x = foo(0) / foo(N-1);
#pragma omp for
for (i = 0; i < N; i++) {
a[i] = foo(i);
b[i] = x * a[i];
}
}
Intel and the Intel logo are trademarks or registered trademarks of Intel Corporation or its subsidiaries in the United States
or other countries. * Other brands and names are the property of their respective owners.
17
References
Rohit Chandra, Leonardo Dagum, Dave Kohr, Dror
Maydan, Jeff McDonald, and Ramesh Menon,
Parallel Programming in OpenMP, Morgan
Kaufmann (2001).
Peter Denning, “The Locality Principle,” Naval