Question about Bottom-up traversal used in LBVH and TRBVH

Practical and theoretical implementation discussion.
shocker_0x15
Posts: 75
Joined: Sun Aug 19, 2012 3:24 pm
Contact:

Re: Question about Bottom-up traversal used in LBVH and TRBV

Post by shocker_0x15 » Tue Nov 25, 2014 5:36 pm

Thanks sriravic, MohamedSakr.

Let me confirm to determine whether my understand about the atomic is right or not.

If 2 threads enter the while loop at the same time, that is, execute the atomic_inc(), is there a case that each returned value is 0? (The initial value of counters are 0.)
I think the counter value after 2 threads execute the atomic will be 2 because this is atomic operation.
However I'm not sure about the return value.
If it is true, the occurrence of the race condition seems natural.

Thanks.

MohamedSakr
Posts: 83
Joined: Thu Apr 24, 2014 2:27 am

Re: Question about Bottom-up traversal used in LBVH and TRBV

Post by MohamedSakr » Tue Nov 25, 2014 5:59 pm

shocker_0x15 wrote:Thanks sriravic, MohamedSakr.

Let me confirm to determine whether my understand about the atomic is right or not.

If 2 threads enter the while loop at the same time, that is, execute the atomic_inc(), is there a case that each returned value is 0? (The initial value of counters are 0.)
I think the counter value after 2 threads execute the atomic will be 2 because this is atomic operation.
However I'm not sure about the return value.
If it is true, the occurrence of the race condition seems natural.
first thread will run, atomic returns 0, which is while(false) , so first thread do nothing at all
second thread will run, atomic returns 1, which is while(true) , so second thread will do what you expect from the first thread
third thread will run, atomic returns 2, which is while(false) , so third thread will do nothing at all

sriravic
Posts: 20
Joined: Fri Jun 22, 2012 6:48 pm

Re: Question about Bottom-up traversal used in LBVH and TRBV

Post by sriravic » Tue Nov 25, 2014 6:32 pm

Hi

The hardware guarantees that increments will happen in atomic fashion as in serially and hence the return values would be unique (the function would not return till the increment happens). However I feel that the while loop condition is not a guarantee to prevent race condition as you will be having thousands of threads in flight with each thread in different code stages and hence would not have written their corresponding bounding boxes or parent bounding boxes(union). It would be totally a an undetermined operation. I guess that must be the reason why you are not able to get consistent results during rendering.

shocker_0x15
Posts: 75
Joined: Sun Aug 19, 2012 3:24 pm
Contact:

Re: Question about Bottom-up traversal used in LBVH and TRBV

Post by shocker_0x15 » Wed Nov 26, 2014 4:55 am

Thanks.
first thread will run, atomic returns 0, which is while(false) , so first thread do nothing at all
second thread will run, atomic returns 1, which is while(true) , so second thread will do what you expect from the first thread
third thread will run, atomic returns 2, which is while(false) , so third thread will do nothing at all
The hardware guarantees that increments will happen in atomic fashion as in serially and hence the return values would be unique (the function would not return till the increment happens).
My understanding seems not wrong.
The third thread will never come because this is a Binary Radix Tree and each thread starts from unique leaf.

I'm interested in how the author of the papar implements this.

shocker_0x15
Posts: 75
Joined: Sun Aug 19, 2012 3:24 pm
Contact:

Re: Question about Bottom-up traversal used in LBVH and TRBV

Post by shocker_0x15 » Sat Nov 29, 2014 2:31 pm

I have maybe succeeded to resolve this issue.
I guess that the atomic operation and using it in the while condition is not a problem.
The cause seems to be a "cache". Writing an AABB to global memory is cached, so in case another thread tries to read the written data, there is no consistency.
Therefore, I added "volatile" qualifier to the AABB memory object. it became not to be cached and now I get a consistent result.

Thanks.

Post Reply