While trying to improve the performance of my collision detection class, I found that ~80% of the time spent at the gpu, it spent on if/else conditions just trying to figure out the bounds for the buckets it should loop through.

More precisely:

  1. each thread gets an ID, by that ID it fetches its triangle from the memory (3 integers each) and by those 3 it fetches its vertices(3 floats each).

  2. Then it transforms the vertices into integer grid points (currently 8x8x8) and transforms them into the triangle bounds on that grid

  3. To transform the 3 points into bounds, it finds the min/max of each dimension among each of the points

Since the programming language I am using is missing a minmax intrinsic, I made one myself, looks like this:

procedure MinMax(a, b, c):
   local min, max

   if a > b:
      max = a
      min = b
      max = b
      min = a
   if c > max:
      max = c
      if c < min:
         min = c

   return (min, max)

So on the average it should be 2.5 * 3 *3 = 22.5 comparisons which ends up eating up way more time than the actual triangle - edge intersection tests (around 100 * 11-50 instructions).

In fact, I found that pre-calculating the required buckets on the cpu (single threaded, no vectorization), stacking them in a gpu view along with bucket definition and making the gpu do ~4 extra reads per thread was 6 times faster than trying to figure out the bounds on the spot. (note that they get recalculated before every execution since I'm dealing with dynamic meshes)

So why is the comparison so horrendously slow on a gpu?

  • 2
    $\begingroup$ Your question is about the instruction-level performance of a specific piece of code on a specific type of hardware. That sounds a lot more like a programming question than a computer science question, to me. $\endgroup$ – David Richerby Feb 27 '15 at 9:49
  • 7
    $\begingroup$ My guess is that it is not the comparisons that are expensive but the branches. If the compiler does not use predication (or the GPU does not provide such), branches would be used which causes "thread" forking (because GPUs are SIMD-oriented). Converting the condition to a mask and using the mask to synthesize conditional moves/swaps may be a reasonable alternative. $\endgroup$ – Paul A. Clayton Feb 27 '15 at 11:33
  • 1
    $\begingroup$ @DavidRicherby I'm not sure it is that specific though. Wouldn't this question apply to any SIMD architecture? $\endgroup$ – kasperd Feb 27 '15 at 11:33
  • 1
    $\begingroup$ @DavidRicherby: the reason we teach comp arch in CS departments is because the comp arch has impact on the algorithms you choose. SIMD architectures can produce high throughput only if you can figure out how to write the program with no nested branches. $\endgroup$ – Wandering Logic Feb 27 '15 at 16:01
  • 2
    $\begingroup$ As the answer by Wandering Logic states in a less obvious manner, GPUs work by assuming that many "threads" are at the same instruction simultaneously. So GPUs, roughly speaking, take every branch rather than just the true branches. This is why GPUs exploit the fact that neighbors usually take the same branches; and performance is terrible when this is not true. $\endgroup$ – Rob Feb 27 '15 at 20:35

GPUs are SIMD architectures. In SIMD architectures every instruction needs to be executed for every element that you process. (There's an exception to this rule, but it rarely helps).

So in your MinMax routine not only does every call need to fetch all three branch instructions, (even if on average only 2.5 are evaluated), but every assignment statement takes up a cycle as well (even if it doesn't actually get "executed").

This problem is sometimes called thread divergence. If your machine has something like 32 SIMD execution lanes, it will still have only a single fetch unit. (Here the term "thread" basically means "SIMD execution lane".) So internally each SIMD execution lane has a "I'm enabled/disabled" bit, and the branches actually just manipulate that bit. (The exception is that at the point where every SIMD lane becomes disabled, the fetch unit will generally jump directly to the "else" clause.)

So in your code, every SIMD execution lane is doing:

compare (a > b)
assign (max = a if a>b)
assign (min = b if a>b)
assign (max = b if not(a>b))
assign (min = a if not(a>b))
compare (c > max)
assign (max = c if c>max)
compare (c < min if not(c>max))
assign (min = c if not(c>max) and c<min)

It may be the case that on some GPUs this conversion of conditionals to predication is slower if the GPU is doing it itself. As pointed out by @PaulA.Clayton, if your programming language and architecture has a predicated conditional move operation (especially one of the form if (c) x = y else x = z) you might be able to do better. (But probably not much better).

Also, placing the c < min conditional inside the else of c > max is unnecessary. It certainly isn't saving you anything, and (given that the GPU has to automatically convert it to predication) may actually be hurting to have it nested in two different conditionals.

  • 2
    $\begingroup$ (Sorry if any part of this is unclear, I'm trying to get an answer in before the theorists close the question as off topic.) $\endgroup$ – Wandering Logic Feb 27 '15 at 16:27
  • $\begingroup$ For more on the basics: http.developer.nvidia.com/GPUGems2/gpugems2_chapter34.html And for more recent workarounds: eecis.udel.edu/~cavazos/cisc879/papers/a3-han.pdf $\endgroup$ – Fizz Feb 27 '15 at 20:07
  • $\begingroup$ It is on-topic in the sense that some algorithms cannot be sped up through SIMD parallelism. (ie: Work, Span, etc for a more theoretical treatment of why) $\endgroup$ – Rob Feb 27 '15 at 20:46
  • 1
    $\begingroup$ Here's another lecture on teh basics of divergence people.maths.ox.ac.uk/gilesm/cuda/lecs/lec3-2x2.pdf Note from these that the problem (on Nvidia anyway) is only per-warp. Code running on different warps may happily diverge. And another paper proposing a method for avoiding it: hal.inria.fr/file/index/docid/649650/filename/sbiswi.pdf $\endgroup$ – Fizz Feb 27 '15 at 20:46
  • $\begingroup$ On a slightly different tack, but in line with the comments I wrote under the question eprint.iacr.org/2012/137.pdf is worth reading: 10x slowdown compared to predicted performance can be "normal" for a GPU unless you get down to its assembly (usually with officially unsupported tools). It's possible that GPU-targeting compilers got better, but I wouldn't hold my breath. $\endgroup$ – Fizz Feb 27 '15 at 21:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.