on race condition

General OpenMP discussion

on race condition

Postby gonski » Fri Feb 01, 2008 6:25 pm

Hi, Everybody

I am puzzled by some situations relevant to race condition in OpenMP.

Can these following cases lead to race condition? Would you please give me some hints and suggestions?

Case 1

c$OMP PARALLEL DO DEFAULT(SHARED),
c$OMP* PRIVATE(I),
c$OMP* SCHEDULE(guided)

do i=1, n

f(i)=f(i)+a(i) ! here a,b f are common variables
f(i)=f(i)+b(i)

enddo



Case 2

c$OMP PARALLEL DO DEFAULT(SHARED),
c$OMP* PRIVATE(I),
c$OMP* SCHEDULE(guided)

do i=1, n

a(i)=i ! here a, f are common variables
f(i)=f(i)+a(i)

enddo


Case 2-1

c$OMP PARALLEL DO DEFAULT(SHARED),
c$OMP* PRIVATE(I,tmp),
c$OMP* SCHEDULE(guided)

do i=1, n

call ff(tmp)
a(i)=tmp ! here a are common variables

enddo

subroutine ff(atmp)
atmp=0
do i=1,100
atmp=atmp+1
enddo
return
end


Case 3

c$OMP PARALLEL DO DEFAULT(SHARED),
c$OMP* PRIVATE(I),
c$OMP* SCHEDULE(guided)

do i=1, n

call ff(i)

enddo

subroutine ff(i)

do j=1,nj
a(i)=j ! a) is a common variable
enddo

Case 4

c$OMP PARALLEL DO DEFAULT(SHARED),
c$OMP* PRIVATE(I),
c$OMP* SCHEDULE(guided)

do i=1, n ! only want to parallelize n loop

do j=1,m
a(i)=j ! here a is a common variable.
enddo

enddo


Case 5

c$OMP PARALLEL DO DEFAULT(SHARED),
c$OMP* PRIVATE(I),
c$OMP* SCHEDULE(guided)

do i=1, n

a0(i)=f(i) ! here a,a0, f are common variables
f(i)=f(i)+a(i)

enddo



Regards,
Gonski
gonski
 
Posts: 26
Joined: Fri Jan 18, 2008 10:58 pm

Re: on race condition

Postby ejd » Sat Feb 02, 2008 6:09 am

gonski wrote:Hi, Everybody

I am puzzled by some situations relevant to race condition in OpenMP.

Can these following cases lead to race condition? Would you please give me some hints and suggestions?

Races have nothing to do with whether the schedule is guided or whether the data is in a common block or not. It deals with whether two accesses (not both being reads - which is a race but not a problem) to the same variable can occur at the same time. For example, if one thread is writing variable "a" and another thread is trying to read it.

gonski wrote:Case 1

c$OMP PARALLEL DO DEFAULT(SHARED),
c$OMP* PRIVATE(I),
c$OMP* SCHEDULE(guided)

do i=1, n

f(i)=f(i)+a(i) ! here a,b f are common variables
f(i)=f(i)+b(i)

enddo

Each thread gets some set of iterations of the do loop to perform. Each thread's loop index is unique. All arrays are being accessed by "i" (and not for example i+1). There are no races in the code shown for Case 1.

gonski wrote:Case 2

c$OMP PARALLEL DO DEFAULT(SHARED),
c$OMP* PRIVATE(I),
c$OMP* SCHEDULE(guided)

do i=1, n

a(i)=i ! here a, f are common variables
f(i)=f(i)+a(i)

enddo

There are no races in the code shown for Case 2.

gonski wrote:Case 2-1

c$OMP PARALLEL DO DEFAULT(SHARED),
c$OMP* PRIVATE(I,tmp),
c$OMP* SCHEDULE(guided)

do i=1, n

call ff(tmp)
a(i)=tmp ! here a are common variables

enddo

subroutine ff(atmp)
atmp=0
do i=1,100
atmp=atmp+1
enddo
return
end

I am not quite as sure on this one. You have used "i" as the loop index in both loops and have not declared "i" in the subroutine. If subroutine ff is contained in the main, then there would be a race on variable "i", because the use association would be to a shared version of "i". If these are compiled as two separate programs, then I would say there is no race.

gonski wrote:Case 3

c$OMP PARALLEL DO DEFAULT(SHARED),
c$OMP* PRIVATE(I),
c$OMP* SCHEDULE(guided)

do i=1, n

call ff(i)

enddo

subroutine ff(i)

do j=1,nj
a(i)=j ! a) is a common variable
enddo

There are no races in the code shown for Case 3.

gonski wrote:Case 4

c$OMP PARALLEL DO DEFAULT(SHARED),
c$OMP* PRIVATE(I),
c$OMP* SCHEDULE(guided)

do i=1, n ! only want to parallelize n loop

do j=1,m
a(i)=j ! here a is a common variable.
enddo

enddo

There are no races in the code shown for Case 4.

gonski wrote:Case 5

c$OMP PARALLEL DO DEFAULT(SHARED),
c$OMP* PRIVATE(I),
c$OMP* SCHEDULE(guided)

do i=1, n

a0(i)=f(i) ! here a,a0, f are common variables
f(i)=f(i)+a(i)

enddo

There are no races in the code shown for Case 5.
ejd
 
Posts: 1025
Joined: Wed Jan 16, 2008 7:21 am

Re: on race condition

Postby gonski » Sat Feb 02, 2008 12:02 pm

ejd wrote:
Case 2

c$OMP PARALLEL DO DEFAULT(SHARED),
c$OMP* PRIVATE(I),
c$OMP* SCHEDULE(guided)

do i=1, n

a(i)=i ! here a, f are common variables
f(i)=f(i)+a(i)

enddo
There are no races in the code shown for Case 2.

Case 2-1

c$OMP PARALLEL DO DEFAULT(SHARED),
c$OMP* PRIVATE(I,tmp),
c$OMP* SCHEDULE(guided)

do i=1, n

call ff(tmp)
a(i)=tmp ! here a are common variables

enddo

I am not quite as sure on this one. You have used "i" as the loop index in both loops and have not declared "i" in the subroutine. If subroutine ff is contained in the main, then there would be a race on variable "i", because the use association would be to a shared version of "i". If these are compiled as two separate programs, then I would say there is no race.




For case 2-1

It also means when a loop and subroutine are in the same file, e.g. "*.f", variables in the subroutine could be classified according to the declaration of the loop even I do not declare anything in subroutine, right?

For case 2

in "Parallel Programming in Fortran 95 using OpenMP" which can be download from http://www.openmp.org/presentations/mig ... Pv1_v2.pdf
Page 11-12 said :

Since each thread is executing part of the iterations of the do-loop and the updates of
the modifications made to the variables are not ensured until the end of the work-sharing
construct, the following example will not work correctly using the !$OMP DO/!$OMP END
DO directive-pair for its parallelization:
real(8) :: A(1000), B(1000)
do i = 1, 1000
B(i) = 10 * i
A(i) = A(i) + B(i)
enddo
because the correct value of the matrix B is not ensured until the end of the worksharing
construct !$OMP END DO.

But I test shows this way always works. so what is happening?
gonski
 
Posts: 26
Joined: Fri Jan 18, 2008 10:58 pm

Re: on race condition

Postby gonski » Sat Feb 02, 2008 1:43 pm

Here I give an example to further explain my above question.

case 1

the begin of 'test.f'

program test
c$omp parallel do default (shared),
c$omp *private(i,x)
do i=1, n
call ff
x=..
enddo

subroutine ff
do j=1,nn ??????? nn and j should be shared varaibles
enddo
return
end

end

the end of 'test.f'



Case 2

the begin of 'test.f'

program test
c$omp parallel do default (shared),
c$omp *private(i,x)
do i=1, n
call ff
x=..
enddo

end
the end of 'test.f'


the begin of 'other.f'

subroutine ff
do j=1,nn ??????? nn and j should be private variables
enddo
return
end


the end of 'other.f'


Case 3

the begin of 'other.f'

subroutine test
c$omp parallel do default (shared),
c$omp *private(i,x)
do i=1, n
call ff
x=..
enddo
return
end

subroutine ff
do j=1,nn ??????? nn and j should be private variables?
enddo
return
end

the end of 'other.f'
gonski
 
Posts: 26
Joined: Fri Jan 18, 2008 10:58 pm

Re: on race condition

Postby ejd » Sat Feb 02, 2008 3:53 pm

gonski wrote:For case 2-1

It also means when a loop and subroutine are in the same file, e.g. "*.f", variables in the subroutine could be classified according to the declaration of the loop even I do not declare anything in subroutine, right?

It depends on whether they are separate program units or one is contained within the other. I see you have posted another message so I will try and show what happens with your examples in that message.

gonski wrote:For case 2

in "Parallel Programming in Fortran 95 using OpenMP" which can be download from http://www.openmp.org/presentations/mig ... Pv1_v2.pdf
Page 11-12 said :

Since each thread is executing part of the iterations of the do-loop and the updates of
the modifications made to the variables are not ensured until the end of the work-sharing
construct, the following example will not work correctly using the !$OMP DO/!$OMP END
DO directive-pair for its parallelization:
real(8) :: A(1000), B(1000)
do i = 1, 1000
B(i) = 10 * i
A(i) = A(i) + B(i)
enddo
because the correct value of the matrix B is not ensured until the end of the worksharing
construct !$OMP END DO.

But I test shows this way always works. so what is happening?

I have not read this paper, but I don't agree with what he is saying about this example. Yes - each thread is indeed executing part of the iterations of the do-loop and the updates are not guaranteed until the implied flush at the barrier at the end of the loop. However, each iteration will be executed by a thread that first updates the ith element of B and then uses the ith element to update A. That thread knows the correct value of B(i), since it is the one that calculated it. So this example should always work correctly.
ejd
 
Posts: 1025
Joined: Wed Jan 16, 2008 7:21 am

Re: on race condition

Postby ejd » Sat Feb 02, 2008 4:28 pm

gonski wrote:Here I give an example to further explain my above question.

case 1

the begin of 'test.f'

program test
integer j, nn
c$omp parallel do default (shared),
c$omp *private(i,x)
do i=1, n
call ff
x=..
enddo

contains
subroutine ff
do j=1,nn ! nn and j are shared variables
enddo
return
end subroutine

end program

the end of 'test.f'

I have modified your program (items in bold) so that it would compile with my F90 compiler and have variables "nn" and "j" shared (I believe the correct Fortran terminology is use associated). Since "nn" is never modified, having it shared is not a problem. However, since "j" is a loop index that will be used by each thread, this will cause a problem (race condition). One way to fix this problem would be to change the loop index (j) to a variable declared within subroutine ff.

gonski wrote:Case 2

the begin of 'test.f'

program test
c$omp parallel do default (shared),
c$omp *private(i,x)
do i=1, n
call ff
x=..
enddo

end
the end of 'test.f'


the begin of 'other.f'

subroutine ff
do j=1,nn ! nn and j are private variables
enddo
return
end

the end of 'other.f'

In this case variables "nn" and "j" are both private to subroutine ff.

gonski wrote:Case 3

the begin of 'other.f'

subroutine test
c$omp parallel do default (shared),
c$omp *private(i,x)
do i=1, n
call ff
x=..
enddo
return
end

subroutine ff
do j=1,nn ! nn and j are private variables?
enddo
return
end

the end of 'other.f'

In this case variables "nn" and "j" are both private to subroutine ff.
ejd
 
Posts: 1025
Joined: Wed Jan 16, 2008 7:21 am

Re: on race condition

Postby gonski » Sun Feb 03, 2008 2:52 am

Thanks! all above answers really help
gonski
 
Posts: 26
Joined: Fri Jan 18, 2008 10:58 pm

Re: on race condition

Postby gonski » Sun Feb 03, 2008 2:57 am

This paper is quite interesting. How can use the so-called new directives in my code. If I can not do it by myself, is it possible for openmp tem to consider the directive in future release?


New OPENMP Directives for Irregular Data Access Loops


http://citeseer.ist.psu.edu/516597.html
gonski
 
Posts: 26
Joined: Fri Jan 18, 2008 10:58 pm

Re: on race condition

Postby ejd » Sun Feb 03, 2008 7:33 am

The paper you mention is based on work that was done at a couple of universities and has not been adopted by the OpenMP ARB. The ARB (Architecture Review Board) has a language group made up of members from industry (companies like HP, IBM, Intel, and SUN to mention a few) and from users (Aachen, EPCC, and CEPBA). The language group has regular phone meetings where proposals for extensions to the OpenMP specification are discussed. When a majority of the members feel that a proposal has merit it goes through a rather lengthly review and is incorporated into a new specification. At some point, this new spec is put out for public comment. Updates are made based on the comments received and the spec is formally adopted by the ARB.

So the only way to try using something like what is described in the paper, is to contact the authors and see if what they implemented is available for use. It may be supported or not by them. Remember though, that what they describe is most likely not part of the spec and thus may or may not be generally adopted by others and thus may not be available in other compilers.

Contacting the company that wrote the compiler you use and pushing on them is one way to get things done. If enough people do it and a company implements it, it goes a long way to helping get it adopted. That way, there is a prototype that people can see and play with to understand if the function is useful. Another way is to contact lfm (currently the CEO of the ARB) and see if there is a way to ask that something like this be considered for inclusion to OpenMP. I don't know if there is a process for this or not, but he will.
ejd
 
Posts: 1025
Joined: Wed Jan 16, 2008 7:21 am

Re: on race condition

Postby gonski » Sun Feb 03, 2008 5:15 pm

HI, edj
This is a big thing. I have to give up as having no time enough to do it.
Any way, with your help, my code works with 30% improvement (2 CPUs are used in the parallel running).

In my code there are two places I can not use parallelism.

Case 1

Code: Select all
do l=1, list
i=particlei(i)
j=particlej(j)
f(i)=f(i)+force
f(j)=f(j)-force
enddo


Here race condition exits. the aforementioned new directives can solve the problem. Another way is to create a temporary variable to store f(j), and combine them later. With this treatment, parallelism is acceptable for this part of code. Therefore the new directives mentioned seem not important to me now.

Case 2

Code: Select all
do i=1, n   ! to create a link list

if(something)then

k=k+2
f(k)=.....

enddo


In this case, as too many variables in the code are relevant to k and spreading everywhere, I have to use sequential running here.
Do you have any good idea on this point?

Cheers,
Gonski
gonski
 
Posts: 26
Joined: Fri Jan 18, 2008 10:58 pm

Next

Return to Using OpenMP

Who is online

Users browsing this forum: Google [Bot] and 5 guests