Interlude: Data Dependencies
• In order for a loop to parallelize, the work done in one loop iteration cannot depend on the
work done in any other iteration.
• In other words, the order of execution of loop iterations must be irrelevant.
• Loops with this property are called data independent.
• Some data dependencies may be broken by changing the code.
Ümit Demirbaga (PhD)
Data Dependencies
• Only variables that are written in one Is there a dependency here?
iteration and read in another iteration
will create data dependencies.
• A variable cannot create a dependency do i = 2,N,2
unless it is shared. a(i) = c*a(i-1)
enddo
• Often data dependencies are difficult to
identify. Compiler tools can help by
identifying the dependencies
automatically. Thread
0 a(2) = c*a(1)
Recurrence:
1 a(3) = c*a(2)
do i = 2,5
a(i) = c*a(i-1) 2 a(4) = c*a(3)
enddo
3 a(5) = c*c(4)
Time
Ümit Demirbaga (PhD)
Data Dependencies
Temporary Variable Dependency
• Unless declared as private, a
temporary variable may be shared, and do i = 1,n
will cause a data dependency. x = cos(a(i))
b(i) = sqrt(x * c)
enddo
Function Calls
do i = 1,n
call myroutine(a,b,c,i) • In general, loops containing function
enddo calls can be parallelized.
• The programmer must make certain that
the function or subroutine contains no
subroutine myroutine(a,b,c,i) dependencies or other side effects.
… • In Fortran, make sure there are no
a(i) = 0.3 * (a(i-1)+b(i)+c) static variables in the called routine.
… • Intrinsic functions are safe.
return
Ümit Demirbaga (PhD)
Data Dependencies
Reductions
• Similar to the temporary variable do i = 1,n
dependency, a reduction dependency is xsum = xsum + a(i)
eliminated simply by using the xmu1 = xmu1 * a(i)
reduction clause to the parallel xmax = max(xmax,a(i))
do directive. xmin = min(xmin,a(i))
enddo
Indirect Indexing
do i = 1,n
a(i) = c * a(idx(i))
enddo • If idx(i) not equal to i on every
iteration, then there is a dependency.
do i = 1,n • If ndx(i) ever repeats itself, there is a
a(ndx(i)) = b(i)+c (i) dependency.
enddo
Ümit Demirbaga (PhD)
Data Dependencies
Conditional Loop Exit
• Loops with conditional exits should not
be parallelized. Requires ordered do i = 1,n
execution. a(i) = b(i) + c(i)
if (a(i).[Link]) then
a(i) = amax
goto 100
endif
Nested Loop Order
enddo
do k = 1, n
do j = 1, n 100 continue
do i = 1, n
a(i,j)=a(i,j)+b(i,k)*c(k,j)
enddo • If the k-loop is parallelized, then there
enddo is a dependency related to a(i,j)
enddo • This can be fixed by making the k-loop
the innermost loop
Ümit Demirbaga (PhD)
Minimizing the Cost of a Recurrence
• Move the dependency into a separate
loop.
• Parallelize the loop without the
dependency. c
• Make sure benefits outweigh the cost c Parallel Loop
of loop overhead. c
c$omp parallel do shared(junk)
c$omp& private(i)
do i = 1, NHUGE do i = 1, NHUGE
a(i) = ...lots of math... junk(i) = ...lots of math...
enddo
& + a(i-1)
enddo c
c Serial Loop
c
do i = 1, NHUGE
a(i) = junk(i) + a(i-1)
enddo
Ümit Demirbaga (PhD)
Loop Nest Parallelization Possibilities
All examples shown run on 8 threads with schedule(static)
• Parallelize the outer loop:
!$omp parallel do private(i,j) shared(a)
do i=1,16
do j=1,16
a(i,j) = i+j
enddo
enddo
• Each thread gets two values of i (T0 gets i=1,2; T1 gets i=3,4, etc.) and all
values of j
Ümit Demirbaga (PhD)
Loop Nest Parallelization Possibilities
• Parallelize the inner loop:
do i=1,16
!$omp parallel do private(j) shared(a,i)
do j=1,16
a(i,j) = i+j
enddo
enddo
• Each thread gets two values of j (T0 gets j=1,2; T1 gets j=3,4, etc.) and all
values of i
Ümit Demirbaga (PhD)
OpenMP Synchronization Constructs
• critical
• atomic
• barrier
• master
• ordered
• flush
Ümit Demirbaga (PhD)
OpenMP Synchronization - critical Section
• Ensures that a code block is executed by only one thread at a time in a parallel
region
• Syntax: #pragma omp critical [(name)]
structured block
!$omp critical [(name)]
structured block
!$omp end critical [(name)]
• When one thread is in the critical region, the others wait until the thread
inside exits the critical section.
• name identifies the critical region.
• Multiple critical sections are independent of one another unless they use the
same name.
• All unnamed critical regions are considered to have the same identity.
Ümit Demirbaga (PhD)
OpenMP Synchronization - critical Section Example
integer :: cnt1, cnt2
c$omp parallel private(i)
c$omp& shared(cnt1,cnt2)
c$omp do
do i = 1, n
…do work…
if(condition1)then
c$omp critical (name1)
cnt1 = cnt1+1
c$omp end critical (name1)
else
c$omp critical (name1)
cnt1 = cnt1-1
c$omp end critical (name1)
endif
if(condition2)then
c$omp critical (name2)
cnt2 =cnt2+1
c$omp end critical (name2)
endif
enddo
c$omp end parallel
Ümit Demirbaga (PhD)
OpenMP - critical Section Problem
Is this correct? What about this?
… …
c$omp parallel do c$omp parallel do
do i = 1,n do i = 1,n
if (a(i).[Link]) then c$omp critical
c$omp critical if (a(i).[Link]) then
xmax = a(i) xmax = a(i)
c$omp end critical endif
endif c$omp end critical
enddo enddo
… …
Ümit Demirbaga (PhD)
OpenMP Synchronization - atomic Update
• Prevents a thread that is in the process of (1) accessing, (2) changing, and (3)
restoring values in a shared memory location from being interrupted at any
stage by another thread.
• Syntax:
#pragma omp atomic
statement
!$omp atomic
statement
• Alternative to using the reduction clause (it applies to same kinds of
expressions).
• Directive in effect only for the code statement immediately following it.
Ümit Demirbaga (PhD)
OpenMP Synchronization - atomic Update
integer, dimension(8) :: a,index
data index/1,1,2,3,1,4,1,5/
c$omp parallel private(i),shared(a,index)
c$omp do
do i = 1, 8
c$omp atomic
a(index(I)) = a(index(I)) + index(I)
enddo
c$omp end parallel
Ümit Demirbaga (PhD)
OpenMP Synchronization - barrier
• Causes threads to stop until all threads have reached the barrier.
• Syntax:
!$omp barrier
#pragma omp barrier
• A red light until all threads arrive, then it turns green.
• Example:
c$omp parallel
c$omp do
do i = 1, N
<assignment>
c$omp barrier
<dependent work>
enddo
c$omp end parallel
Ümit Demirbaga (PhD)
OpenMP Synchronization - master Region
• Code in a master region is executed only by the master thread.
• Syntax:
#pragma omp master
structured block
!$omp master
structured block
!$omp end master
• Other threads skip over entire master region (no implicit barrier!).
Ümit Demirbaga (PhD)
OpenMP Synchronization - master Region
!$omp parallel shared(c,scale) &
!$omp private(j,myid)
myid=omp_get_thread_num()
!$omp master
print *,’T:’,myid,’ enter scale’
read *,scale
!$omp end master
!$omp barrier
!$omp do
do j = 1, N
c(j) = scale * c(j)
enddo
!$omp end do
!$omp end parallel
Ümit Demirbaga (PhD)
OpenMP Synchronization - ordered Region
• Within an ordered region, loop iterations are forced to be executed in
sequential order.
• Syntax:
c$omp ordered
structured block
c$omp end ordered
#pragma omp ordered
structured block
• An ordered region can only appear in a parallel loop.
• The parallel loop directive must contain the ordered clause (new).
• Threads enter the ordered region one at a time.
Ümit Demirbaga (PhD)
x
Ümit Demirbaga (PhD)
OpenMP Synchronization - ordered Region
integer, external :: omp_get_thread_num
call omp_set_num_threads(4)
c$omp parallel private(myid)
myid=omp_get_thread_num()
c$omp do private(i) ordered
do i = 1, 8
c$omp ordered
print *,’T:’,myid,’ i=‘,i
c$omp end ordered
enddo
c$omp end parallel
T:0 i=1
T:0 i=2
T:1 i=3
T:1 i=4
T:2 i=5
T:2 i=6
T:3 i=7
T:3 i=8
Ümit Demirbaga (PhD)
OpenMP Synchronization - flush Directive
• Causes the present value of the named shared variable to be immediately
written back (“flushed”) to memory.
• Syntax:
c$omp flush(var1[,var2]…)
#pragma omp flush(var1[,var2]…)
• Enables signaling between threads by using a shared variable as a semaphore.
• When other threads see that the shared variable has been changed, they know
that an event has occurred and proceed accordingly.
Ümit Demirbaga (PhD)
Sample Program: flush Directive
program flush
integer, parameter :: M=1600000
integer, dimension(M) :: c
integer :: stop,sum,tid
integer, dimension(0:1) :: done
integer, external :: omp_get_thread_num
call omp_set_num_threads(2)
c=1
c(345)=9
!$omp parallel default(private) shared(done,c,stop)
tid=omp_get_thread_num()
done(tid)=0
if(tid==0) then
neigh=1
else
neigh=0
end if
!$omp barrier
Ümit Demirbaga (PhD)
Sample Program: flush Directive (cont.)
if (tid==0) then
do j=1,M
if(c(j)==9) stop=j
end do
end if
done(tid)=1
!$omp flush(done)
do while(done(neigh).eq.0)
!$omp flush(done)
end do
if (tid==1) then
sum=0
do j=1,stop-1
sum=sum+c(j)
end do
end if
!$omp end parallel
end program flush
Ümit Demirbaga (PhD)