Dependencies
By using a parallel for, you are telling the compiler that there are no inter-iteration loop dependencies; that is, the loop iterations are completely independent of one another. If this is not true, multiple problems (and incorrect results) can occur.
The loop cannot contain statements that terminate the loop prematurely. No break, return, exit, or goto (C/C++, Python) or exit, return, stop, or go to (Fortran).
Iterations can be skipped; continue (C/C++, Python) or cycle (Fortran) is permitted.
Types of Data Dependency
Computer scientists categorize data dependencies into three types.
True Dependence
A loop contains a true dependency if a variable’s value is written to memory before it is read. A simple example is
a[0]=0;
for (i=1; i<N; i++) {
a[i]=a[i-1]+10.;
}
The value at index i depends on the value set at the previous iteration. In a serial code, this does not cause a problem because a[i-1] has been computed and written. In a threaded code, a[i] and a[i-1] are not necessary accessed by the same thread, so the updated a[i-1] may not have been written when another thread wants to read it. This is also called a read after write dependence.
C
Contents of omp_truedep.c
#include <stdio.h>
#include <omp.h>
int main() {
const int N=48;
int a[N];
a[0]=100;
#pragma omp parallel for
for (int i=1; i<N; i++) {
a[i] = a[i-1] + 10;
}
for (int i=0; i<N; i++) {
printf("%d %d\n",i,a[i]);
}
}
Fortran
Contents of omp_truedep.f90
program truedep
integer, parameter :: N=48
integer, dimension(N) :: a
integer :: x=5
integer :: i
a(1)=100
!$omp parallel do
do i=1, N-1
a(i+1)=a(i)+10
enddo
!$omp end parallel do
do i=1, N
write(*,*) i,a(i)
enddo
end program
Python
Contents of omp_truedep.py
import numpy as np
from omp4py import *
@omp
def output_dependency(N):
a=np.zeros(N,dtype='int')
a[0]=100;
with omp("parallel for"):
for i in range(1,N):
a[i]=a[i-1]+10
return a
N=48;
a=output_dependency(N)
for i in range(N):
print(i,a[i])
Anti-Dependence
This is a write after_read dependence.
for (i=0; i<N-1; i++) {
a[i]=a[i+1]+10.;
}
In a serial code, the intention in such a loop would normally be to use the old value of a[i+1] to update the current a[i], but this cannot be guaranteed in a threading environment.
C
Contents of omp_antidep.c
#include <stdio.h>
#include <omp.h>
int main() {
const int N=48;
int a[N];
for (int i=0; i<N; i++)
a[i]=100-i;
#pragma omp parallel for
for (int i=0; i<N-1; i++) {
a[i] = a[i+1] + 10;
}
for (int i=0; i<N; i++) {
printf("%d %d\n",i,a[i]);
}
}
Fortran
Contents of omp_antidep.f90
program antidep
integer, parameter :: N=48
integer, dimension(N) :: a
integer :: i
do i=1,N
a(i)=100-i
enddo
!$omp parallel do
do i=1, N-1
a(i)=a(i+1)+10
enddo
!$omp end parallel do
do i=1, N
write(*,*) i,a(i)
enddo
end program
Python
Contents of omp_antidep.py
import numpy as np
from omp4py import *
@omp
def output_dependency(a,N):
with omp("parallel for"):
for i in range(N-1):
a[i]=a[i+1]+10
return a
N=48;
a=np.zeros(N,dtype='int')
for i in range(N):
a[i]=100-i;
a=output_dependency(a,N)
for i in range(N):
print(i,a[i])
Output Dependence
This is a write_after_write dependence. A location in memory must be written before it is written again.
for (i=0; i<N-1; i++) {
a[i] = i;
a[i+1] = x+i;
}
This pattern might be fairly unusual even in serial code, but it can happen. At iteration i the value of a[i+1] was located in memory at a[i]. If it is accessed before a[i], an incorrect result can be computed.
When run in serial, a loop such as this will overwrite all but the last value of a. Run threaded in C or Fortran, it usually gets the expected result but some values are incorrect.
C
Contents of omp_outdep.c
#include <stdio.h>
#include <omp.h>
int main() {
const int N=48;
int a[N];
int x=5;
a[N-1]=100;
#pragma omp parallel for
for (int i=0; i<N-1; i++) {
a[i]=i;
a[i+1]=x+i;
}
for (int i=0; i<N; i++) {
printf("%d %d\n",i,a[i]);
}
}
Fortran
Contents of omp_outdep.f90
program outdep
integer, parameter :: N=48
integer, dimension(N) :: a
integer :: x=5
integer :: i
a(N)=100;
!$omp parallel do
do i=1, N-1
a(i)=i
a(i+1)=x+i
enddo
!$omp end parallel do
do i=1, N
write(*,'(i4,x,i4)') i, a(i)
enddo
end program
Python
Contents of omp_outdep.py
import numpy as np
from omp4py import *
@omp
def output_dependency(N):
a=np.zeros(N,dtype='int')
x=5;
a[N-1]=100;
with omp("parallel for"):
for i in range(N-1):
a[i]=i
a[i+1]=x+i
return a
N=48;
a=output_dependency(N)
for i in range(N):
print(i,a[i])
Exercise
Run the codes for your language of choice. For C and Fortran, also compile without OpenMP to run as a serial code and compare the results.