¿Por qué las comparaciones son tan caras en una GPU?

10

Mientras intentaba mejorar el rendimiento de mi clase de detección de colisión, descubrí que ~ 80% del tiempo que pasaba en la gpu, lo dedicaba a las condiciones de si / de lo contrario solo intentaba descubrir los límites de los cubos por los que debería pasar.

Más precisamente:

  1. cada hilo obtiene una ID, por esa ID obtiene su triángulo de la memoria (3 enteros cada uno) y por esos 3 obtiene sus vértices (3 flota cada uno).

  2. Luego transforma los vértices en puntos de cuadrícula entera (actualmente 8x8x8) y los transforma en los límites del triángulo en esa cuadrícula

  3. Para transformar los 3 puntos en límites, encuentra el mínimo / máximo de cada dimensión entre cada uno de los puntos

Como al lenguaje de programación que estoy usando le falta un mínimo intrínseco, lo hice yo mismo, se ve así:

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)

Entonces, en promedio, debería ser 2.5 * 3 * 3 = 22.5 comparaciones que terminan consumiendo mucho más tiempo que las pruebas reales de intersección triángulo-borde (alrededor de 100 * 11-50 instrucciones).

De hecho, descubrí que calcular previamente los cubos necesarios en la CPU (subproceso único, sin vectorización), apilarlos en una vista de gpu junto con la definición del cubo y hacer que el gpu haga ~ 4 lecturas adicionales por hilo fue 6 veces más rápido que intentarlo para descubrir los límites en el acto. (tenga en cuenta que se vuelven a calcular antes de cada ejecución ya que estoy tratando con mallas dinámicas)

Entonces, ¿por qué la comparación es tan terriblemente lenta en una gpu?

user29075
fuente
2
Su pregunta es sobre el rendimiento a nivel de instrucción de un código específico en un tipo específico de hardware. Para mí, eso parece mucho más una pregunta de programación que una pregunta de informática.
David Richerby
77
Mi conjetura es que no son las comparaciones que son caros, pero las ramas. Si el compilador no usa la predicción (o la GPU no proporciona tal), se usarían ramas que causan bifurcación de "subproceso" (porque las GPU están orientadas a SIMD). Convertir la condición en una máscara y usar la máscara para sintetizar movimientos / intercambios condicionales puede ser una alternativa razonable.
Paul A. Clayton
1
@DavidRicherby No estoy seguro de que sea tan específico. ¿No se aplicaría esta pregunta a cualquier arquitectura SIMD?
kasperd
1
@DavidRicherby: la razón por la que enseñamos el arco de compilación en los departamentos de CS es porque el arco de compilación tiene un impacto en los algoritmos que elija. Las arquitecturas SIMD pueden producir un alto rendimiento solo si puede descubrir cómo escribir el programa sin ramas anidadas.
Wandering Logic
2
Como dice la respuesta de Wandering Logic de una manera menos obvia, las GPU funcionan asumiendo que muchos "hilos" están en la misma instrucción simultáneamente. Entonces, las GPU, en términos generales, toman cada rama en lugar de solo las ramas verdaderas. Esta es la razón por la cual las GPU explotan el hecho de que los vecinos generalmente toman las mismas ramas; y el rendimiento es terrible cuando esto no es cierto.
Rob

Respuestas:

10

Las GPU son arquitecturas SIMD. En las arquitecturas SIMD, cada instrucción debe ejecutarse para cada elemento que procese. (Hay una excepción a esta regla, pero rara vez ayuda).

Por lo tanto, en su MinMaxrutina no solo cada llamada necesita obtener las tres instrucciones de bifurcación (incluso si en promedio solo se evalúan 2.5), sino que cada declaración de asignación también toma un ciclo (incluso si en realidad no se "ejecuta" )

Este problema a veces se llama divergencia de hilo . Si su máquina tiene algo así como 32 carriles de ejecución SIMD, todavía tendrá una sola unidad de recuperación. (Aquí el término "hilo" básicamente significa "carril de ejecución SIMD".) De modo que internamente cada carril de ejecución SIMD tiene un bit "Estoy habilitado / deshabilitado", y las ramas en realidad solo manipulan ese bit. (La excepción es que en el punto donde cada carril SIMD se deshabilita, la unidad de búsqueda generalmente saltará directamente a la cláusula "else").

Entonces, en su código, cada línea de ejecución SIMD está haciendo:

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)

Puede darse el caso de que en algunas GPU esta conversión de condicionales a predicción sea más lenta si la GPU lo hace por sí misma. Como señaló @ PaulA.Clayton, si su lenguaje y arquitectura de programación tienen una operación de movimiento condicional predicada (especialmente una de las formas if (c) x = y else x = z), podría hacerlo mejor. (Pero probablemente no mucho mejor).

Además, no es necesario colocar el c < mincondicional dentro elsede c > max. Ciertamente no le está ahorrando nada, y (dado que la GPU tiene que convertirlo automáticamente a una predicción) en realidad puede ser doloroso tenerlo anidado en dos condicionales diferentes.

Lógica Errante
fuente
2
(Lo siento si alguna parte de esto no está clara, estoy tratando de obtener una respuesta antes de que los teóricos cierren la pregunta como fuera de tema.)
Wandering Logic
Para obtener más información básica: http.developer.nvidia.com/GPUGems2/gpugems2_chapter34.html Y para soluciones más recientes: eecis.udel.edu/~cavazos/cisc879/papers/a3-han.pdf
Fizz
Es sobre el tema en el sentido de que algunos algoritmos no pueden acelerarse a través del paralelismo SIMD. (es decir: trabajo, alcance, etc. para un tratamiento más teórico de por qué)
Rob
1
Aquí hay otra conferencia sobre los conceptos básicos de divergencia people.maths.ox.ac.uk/gilesm/cuda/lecs/lec3-2x2.pdf Tenga en cuenta que el problema (en Nvidia de todos modos) es solo por deformación. El código que se ejecuta en diferentes urdimbres puede divergir felizmente. Y otro documento que propone un método para evitarlo: hal.inria.fr/file/index/docid/649650/filename/sbiswi.pdf
Fizz
En un rumbo ligeramente diferente, pero en línea con los comentarios que escribí bajo la pregunta eprint.iacr.org/2012/137.pdf vale la pena leer: una desaceleración de 10x en comparación con el rendimiento previsto puede ser "normal" para una GPU a menos que baje para su montaje (generalmente con herramientas oficialmente no compatibles). Es posible que los compiladores de GPU hayan mejorado, pero no aguantaba la respiración.
Fizz