on race condition

General OpenMP discussion

Re: on race condition

Postby ejd » Mon Feb 04, 2008 8:21 am

gonski wrote:HI, ejd
...
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.

I changed the loop variable to be "k" instead of "l" (because I have a hard time telling the difference between your i's and l's. Also, I am not sure where the initial values of "i" and "j" are coming from (did you mean to index particlei and particlej by "i" and "j" or by "k"?). My comments therefore, are somewhat dependent on exactly what the code looks like.

You can make "i" and "j" firstprivate (or private - depending on the code) and that gets rid of the first problem. I am assuming force is a constant calculated outside the loop and is shared. The second problem is the update of "f". If the values of "i" and "j" are unique, then you don't have a problem updating "f". However, you indicate there is a problem with "f", so I assume they aren't unique. In that case, you have to protect the updates of "f" (in different iterations of loop) from each other. You could use a critical region around both updates or a critical region around each update - but it would most likely be pretty slow (slower than sequential). Another way which may be faster, depends on how unique the numbers are and how the compiler (and runtime) implement atomic. If the numbers are fairly unique and the atomic isn't just a critical (but a compare and swap), then this could be faster than sequential.

Code: Select all
!$omp parallel do shared(particlei, particlej, f, force) private(k) firstprivate(i,j)
do k=1, list
   i=particlei(i)
   j=particlej(j)
   !$omp atomic
   f(i)=f(i)+force
   !$omp atomic
   f(j)=f(j)-force
enddo


gonski wrote: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?

Working on linked lists is hard to do with OpenMP through V2.5. Version 3.0 is adding tasking which makes it far easier to work with linked lists - though there are several things you have to watch out for. If you are using an Intel compiler, they have a version of tasking (taskq) in it that you could use now - though it is nonconforming to the new spec and isn't implemented by anyone else but Intel. This is the best I can suggest with the code you have shown. Maybe someone else has some ideas.
ejd
 
Posts: 1025
Joined: Wed Jan 16, 2008 7:21 am

Re: on race condition

Postby gonski » Mon Feb 04, 2008 3:32 pm

Sorry, I made a mistake in the previous post. This code in case 1 should be,

Code: Select all
do k=1, list
i=particlei(k)
j=particlej(k)

here, it needs many calculations

f(i)=f(i)+force
f(j)=f(j)-force
enddo


The code is changed to

Code: Select all
do k=1, list
i=particlei(k)
j=particlej(k)

here, it needs many calculations

f(i)=f(i)+force
tmp(k)=tmp(k)-force
enddo
do k=1,list
j=particlej(k)
f(j)=f(j)+tmp(j)
enddo


This way allows me to apply parallelism to both k loop and i loop.

I do use intel fortan.
but after checking the task clause, I am not sure it can be used to my case which aims at the generation of a so-called list.

Code: Select all
k=1

do i=1, n   ! to create a link list

first(i)=k

if(something)then

f(k)=.....
k=k+1
if(something)last(i)=k
endif
enddo


Would you please give me some hints?
gonski
 
Posts: 26
Joined: Fri Jan 18, 2008 10:58 pm

Re: on race condition

Postby ejd » Wed Feb 06, 2008 6:22 am

gonski wrote:The code is changed to
Code: Select all
do k=1, list
i=particlei(k)
j=particlej(k)

here, it needs many calculations

f(i)=f(i)+force
tmp(k)=tmp(k)-force
enddo
do k=1,list
j=particlej(k)
f(j)=f(j)+tmp(j)
enddo


This will only work if you know that the "i" values (and "k" values) are unique. Otherwise, you are still going to have a race on your update of "f" (and "tmp"). Remember that it is not just the dependence within one iteration that you have to look at, but also whether the same elements can be updated in different iterations.

gonski wrote:I do use intel fortan. but after checking the task clause, I am not sure it can be used to my case which aims at the generation of a so-called list.
Code: Select all
k=1

do i=1, n   ! to create a link list

first(i)=k

if(something)then

f(k)=.....
k=k+1
if(something)last(i)=k
endif
enddo

Would you please give me some hints?

If you are traversing a list and doing calculations on each element, then the task model would work well. I am not sure that there is a way to create the list in parallel that would gain you anything. I will have to think about this.
ejd
 
Posts: 1025
Joined: Wed Jan 16, 2008 7:21 am

Re: on race condition

Postby gonski » Wed Feb 06, 2008 1:15 pm

ejd wrote:
gonski wrote:The code is changed to
Code: Select all
do k=1, list
i=particlei(k)
j=particlej(k)

here, it needs many calculations

f(i)=f(i)+force
tmp(k)=tmp(k)-force
enddo
do k=1,list
j=particlej(k)
f(j)=f(j)+tmp(j)
enddo


This will only work if you know that the "i" values (and "k" values) are unique. Otherwise, you are still going to have a race on your update of "f" (and "tmp"). Remember that it is not just the dependence within one iteration that you have to look at, but also whether the same elements can be updated in different iterations.



gonski wrote:I do use intel fortan. but after checking the task clause, I am not sure it can be used to my case which aims at the generation of a so-called list.
Code: Select all
k=1

do i=1, n   ! to create a link list

first(i)=k

if(something)then

f(k)=.....
k=k+1
if(something)last(i)=k
endif
enddo

Would you please give me some hints?

If you are traversing a list and doing calculations on each element, then the task model would work well. I am not sure that there is a way to create the list in parallel that would gain you anything. I will have to think about this.



Yes, i and k are unique in my first case. I have confirmed this.

u are right. Now I just can not create list in parallel. In molecular dynamic and discrete element model which both become popular as computation fluid dynamic, the use of list is inevitable as it can greatly save computational efforts. How can report this to OpenMP team? Maybe they would help configure a solution in next release.
gonski
 
Posts: 26
Joined: Fri Jan 18, 2008 10:58 pm

Previous

Return to Using OpenMP

Who is online

Users browsing this forum: Yahoo [Bot] and 6 guests