Tweeted twitter.com/#!/StackCompSci/status/574860614532726784
2 That the code example was written in a real programming language seems to be bothering some people, so changing to pseudocode
source | link

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 c++AMPthe programming language I am using is missing a minmax intrinsic, I made one myself, looks like this:

inline voidprocedure MinMax(const int &aa, const int &bb, constc):
 int &c, intlocal &minmin, int &max) restrict(amp) {max
  
   if (a > b) {:
      max = a;a
      min = b;b
    } else {:
      max = b;b
      min = a;
    }a
    if (c > max) {:
      max = c;c
    } else {:
        if( c < min) {:
            min = c;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?

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 c++AMP is missing a minmax intrinsic, I made one myself, looks like this:

inline void MinMax(const int &a, const int &b, const int &c, int &min, int &max) restrict(amp) {
    if (a > b) {
      max = a;
      min = b;
    } else {
      max = b;
      min = a;
    }
    if (c > max) {
      max = c;
    } else {
        if(c < min) {
            min = c;
        }
    }
}

So on the average it should be 2.5 * 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?

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
   else:
      max = b
      min = a
   if c > max:
      max = c
   else:
      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?

1
source | link

Why are comparisons so expensive on a GPU?

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 c++AMP is missing a minmax intrinsic, I made one myself, looks like this:

inline void MinMax(const int &a, const int &b, const int &c, int &min, int &max) restrict(amp) {
    if (a > b) {
      max = a;
      min = b;
    } else {
      max = b;
      min = a;
    }
    if (c > max) {
      max = c;
    } else {
        if(c < min) {
            min = c;
        }
    }
}

So on the average it should be 2.5 * 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?