performance - Divergencia de ramales, CUDA y Kinetic Monte Carlo

montecarlo

Question

Entonces, tengo un código que usa Kinetic Monte Carlo en un enrejado para simular algo. Estoy usando CUDA para ejecutar este código en mi GPU (aunque creo que la misma pregunta se aplica a OpenCl también).

Esto significa que divido mi celosía en pequeñas subredes y cada hebra opera en una de ellas. Como estoy haciendo KMC, cada hilo tiene este código:

 While(condition == true){
*Grab a sample u from U[0,1]*
for(i = 0; i < 100;i++){
*Do some stuff here to generate A*
if(A > u){
*Do more stuff here, which could include updates to global memory*
break();
}
}
}

A es diferente para diferentes hilos y tú y 100 es solo un número aleatorio. En el código, esto podría ser 1000 o incluso 10000.

Entonces, ¿no tendremos divergencia de rama cuando llegue el momento de que pase un hilo que si? ¿Qué tan gravemente puede afectar esto el rendimiento? Sé que la respuesta depende del código dentro de la cláusula if, pero ¿cómo se ampliará esta escala a medida que agregue más y más hilos?

También sería bienvenido cualquier referencia sobre cómo puedo estimar las pérdidas / ganancias en el rendimiento.

¡Gracias!

Answer 1

La GPU ejecuta subprocesos en grupos de 32 subprocesos, llamados warps. La divergencia solo puede ocurrir dentro de una disformidad. Entonces, si puede organizar sus hilos de tal manera que la condición if se evalúe de la misma manera en todo el warp, no hay divergencia.

Cuando hay divergencia en un if , conceptualmente, la GPU simplemente ignora los resultados y las solicitudes de memoria de los hilos en los que la condición if era falsa.

Por lo tanto, supongamos que if evalúa como true para 10 de los hilos en un warp en particular. Mientras que dentro de eso, el potencial rendimiento de cálculo del warp se reduce de 100% a 10/32 * 100 = 31%, ya que los 22 hilos que se inhabilitaron por el if podrían haber estado trabajando pero ahora solo están ocupando espacio en la disformidad

Una vez que sale del if , los subprocesos deshabilitados se habilitan nuevamente, y el warp procede con un rendimiento de cómputo potencial del 100%.

Un if-else comporta de la misma manera. Cuando el warp llega al else , los hilos habilitados en if se desactivan y los que estaban deshabilitados se habilitan.

En un bucle for que se repite una cantidad diferente de veces para cada subproceso en el warp, los subprocesos se desactivan cuando sus recuentos de iteración alcanzan sus números establecidos, pero el warp como un todo debe seguir repitiéndose hasta que se realice el recuento de iteración más alto.

Al observar el rendimiento potencial de la memoria, las cosas son un poco más complicadas. Si un algoritmo está enlazado a la memoria, es posible que no se pierda mucho o ningún rendimiento debido a la divergencia de la urdimbre, ya que se puede reducir el número de transacciones de memoria. Si cada hilo en la urdimbre estaba leyendo desde una ubicación completamente diferente en la memoria global (una mala situación para una GPU), se ahorraría tiempo para cada uno de los subprocesos desactivados ya que sus transacciones de memoria no tendrían que realizarse. Por otro lado, si los hilos estaban leyendo de una matriz que se había optimizado para el acceso de la GPU, varios hilos compartirían los resultados de una sola transacción. En ese caso, los valores que estaban destinados a los hilos desactivados se leyeron de la memoria y luego se descartaron junto con los cálculos que el hilo desactivado podría haber hecho.

Por lo tanto, ahora es probable que tenga suficiente visión general para poder hacer buenas llamadas de juicio sobre cuánta divergencia de la distorsión va a afectar su rendimiento. El peor caso es cuando solo está activo un hilo en una urdimbre. Luego obtienes 1/32 = 3.125% del potencial para el rendimiento vinculado al cálculo. El mejor caso es 31/32 = 96.875%. Para un if eso es completamente aleatorio, obtienes 50%. Y como se mencionó, el rendimiento de la memoria depende del cambio en el número de transacciones de memoria requeridas.