Page 1 of 2 12 LastLast
Results 1 to 10 of 14

Thread: Real-time raytracing -- Is MIMD req'd?

  1. #1
    Junior Member
    Join Date
    Feb 2012
    Posts
    10

    Real-time raytracing -- Is MIMD req'd?

    Hello all,

    Excuse me if this question is really basic, but this is my first time delving into GPGPU tech.

    I have an HD4850 card (R700 chipset) which I would like to develop on. I'll be casting a multitude of individual rays which requires a lot of branching/conditionals per ray marched.

    What I read about the R700 is that its cores are SIMD. This concerns me, because I'm not sure that OpenCL is going to help me much given that each ray pretty much follows a different execution path.

    Can anyone suggest whether or not I would need a newer card for this? If so, just how mainstream are the MIMD cards?

    Thanks,

    Nick

  2. #2
    Senior Member
    Join Date
    Aug 2011
    Posts
    271

    Re: Real-time raytracing -- Is MIMD req'd?

    Quote Originally Posted by Nick Wiggill
    Hello all,

    Excuse me if this question is really basic, but this is my first time delving into GPGPU tech.

    I have an HD4850 card (R700 chipset) which I would like to develop on. I'll be casting a multitude of individual rays which requires a lot of branching/conditionals per ray marched.

    What I read about the R700 is that its cores are SIMD. This concerns me, because I'm not sure that OpenCL is going to help me much given that each ray pretty much follows a different execution path.

    Can anyone suggest whether or not I would need a newer card for this? If so, just how mainstream are the MIMD cards?

    Thanks,

    Nick
    Whilst a newer card might be faster, all gpu's basically work like this, and in particular none of them will execute divergent branches well (what they all do is execute ALL branch paths, and use a hardware bit to ignore the results on un-taken paths). There are no MIMD cards, and AMD's (now out-dated) VLIW stuff is only at the thread level. And given the way they gain their flops/watt, I can't imagine there ever will be.

    One approach might be a state machine based on lookup-tables, so the code paths are the same but the data changes. Although I don't know if that could be applied to such a problem.

    (I just did a search on "state machine ray tracer" and it came up with a lot of hits about accelerated ray-tracing, so it obviously an obvious approach)

  3. #3
    Junior Member
    Join Date
    Feb 2012
    Posts
    10

    Re: Real-time raytracing -- Is MIMD req'd?

    I was with you through the first part of your answer.

    Re "state machine based on lookup tables", can you roughly outline how that would work? I googled the same terms with little coherent result; there was no clear topic that came to the fore.

    I think my question was unclear, so apologies -- I should have stated that I'm specifically talking about voxel raymarching, which means there is really very little that can be precalculated. I am not talking about the sort of ray tracing that relies on eg. distance fields or other non-discrete mathematical formulae to describe its volumes -- those work in a fundamentally different fashion and experience different complexity limitations as a result. Raymarching is highly conditional and its complexity relies directly on the grid resolution -- and each ray must be marched individually (which contains a lot of conditional logic) rather than in parallel for cache coherence reasons. So outside of MIMD, I really don't think it's possible to accelerate much...

  4. #4
    Junior Member
    Join Date
    Nov 2009
    Posts
    2

    Re: Real-time raytracing -- Is MIMD req'd?

    Quote Originally Posted by Nick Wiggill
    So outside of MIMD, I really don't think it's possible to accelerate much...
    Voxel rendering, path tracing, etc. are very common applications for GPUs (i.e. SIMD). There a many examples available on the net. For instance, this is something I wrote a couple of years ago and it does the rendering of a Julia set by ray marching:

    http://www.youtube.com/watch?v=WpSeQktTq24

    This is an example of path tracing (for off-line rendering) done with GPUs:

    http://www.youtube.com/watch?v=iZ56eHKz6Ts

    And this is another example of path tracing (for real-time rendering):

    http://www.youtube.com/watch?v=Dh9uWYaiP3s

    Divergence is a issue for ray tracing and GPUs but you can pack so much brute force on a consumer PC with multiple GPUs to still outperform expansive multi-CPUs solutions.

  5. #5
    Junior Member
    Join Date
    Feb 2012
    Posts
    10

    Re: Real-time raytracing -- Is MIMD req'd?

    OK, but that still doesn't tell me how 3D DDA raymarching (if that's what is being used) is parallelised on the GPU! Or is 3D DDA avoided in favour of voxel-plane intersection techniques?

    Please, can anyone give me any detail on methods to accelerate this if I am stuck with SIMD? The point is that if every ray takes a different execution path then... How do you parallelise this given SIMD!?

  6. #6
    Senior Member
    Join Date
    Aug 2011
    Posts
    271

    Re: Real-time raytracing -- Is MIMD req'd?

    Quote Originally Posted by Nick Wiggill
    OK, but that still doesn't tell me how 3D DDA raymarching (if that's what is being used) is parallelised on the GPU! Or is 3D DDA avoided in favour of voxel-plane intersection techniques?

    Please, can anyone give me any detail on methods to accelerate this if I am stuck with SIMD? The point is that if every ray takes a different execution path then... How do you parallelise this given SIMD!?
    Coding in opencl wasn't meant to be easy.

    Not being familiar with the algorithm you're talking about, it's hard to suggest anything; do you have some example code of the inner loop and all these different execution paths?

  7. #7
    Junior Member
    Join Date
    Feb 2012
    Posts
    10

    Re: Real-time raytracing -- Is MIMD req'd?

    No one suggested learning OpenCl would be easy. Here's the algorithm:

    http://euklid.mi.uni-koeln.de/c/mirror/ ... t12p1.html

    I strongly suspect that ray-plane/triangle intersections are where most real time raycasters get their speed gain on the GPU. DDA uses a largely arithmetic approach mixed in with heavily conditional grid-stepping.

  8. #8
    Junior Member
    Join Date
    Feb 2012
    Posts
    10

    Re: Real-time raytracing -- Is MIMD req'd?

    Sorry to double post (I can't seem to edit my last post).

    From “Understanding the Efficiency of Ray Traversal on GPUs”, this seems to confirm my suspicions(?):

    "All of the tests in this paper use bounding volume hierarchy (BVH)
    and Woop’s unit triangle intersection test [Woop 2004]. The ray-
    box and ray-triangle tests were optimized in CUDA 2.1"

    I was hoping there was some way to acclerate the core logic of 3D DDA on the GPU, but looking at the above, maybe there is not?

  9. #9
    Senior Member
    Join Date
    Aug 2011
    Posts
    271

    Re: Real-time raytracing -- Is MIMD req'd?

    Quote Originally Posted by Nick Wiggill
    No one suggested learning OpenCl would be easy. Here's the algorithm:

    http://euklid.mi.uni-koeln.de/c/mirror/ ... t12p1.html

    I strongly suspect that ray-plane/triangle intersections are where most real time raycasters get their speed gain on the GPU. DDA uses a largely arithmetic approach mixed in with heavily conditional grid-stepping.
    To me those loops although they contain branches are not what one would call 'branchy', e.g. "algorithm 3DDDA" only has 3 small cases inside the loop, and i suspect those could be collapses into 1 case with some fiddly branchless logic. Even if all lines in the branches are executed it isn't much redundant work: it's not like each branch option contains loops or in worse, data-dependent loops.

    Certainly the first nest if/else of "algorithm 3DDA" could be implemented fairly easily without branches using standard branchless logic techniques (i.e. using select, or ?). Although the compiler may very well do this for you anyway.

    (note that if you managed to use branchless logic here, you could then use vector types and thus explicit SIMD algorithms, however opencl/gpu doesn't need this to be done for good performance).

    But you really just have to code it to see if it will work well or not, even algorithms that don't 'fit' the gpu topology can run faster because it has so much parallelism and memory bandwidth.

  10. #10
    Junior Member
    Join Date
    Feb 2012
    Posts
    10

    Re: Real-time raytracing -- Is MIMD req'd?

    I see... Many thanks for your advice, I shall go ahead and experiment as suggested, then.

    On that topic, any good books for learning OpenCL?, since I get the impression GPGPU tech is definitely something that one needs solid material to learn from. (Particularly given it's relative newness and niche application.) Something like a Beginner-To-Pro sort of book that would suit a professional programmer.

Page 1 of 2 12 LastLast

Similar Threads

  1. OpenCL for Real-Time environments
    By albeld in forum OpenCL
    Replies: 3
    Last Post: 10-06-2011, 05:20 AM
  2. DigVid via IEEE 1394 in Real Time?
    By Robin in forum OpenML Coding & Technical Issues
    Replies: 1
    Last Post: 11-08-2005, 06:39 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •