Pourquoi les comparaisons sont-elles si chères sur un GPU?

Tout en essayant d'améliorer les performances de ma classe de détection de collision, j'ai constaté que ~ 80% du temps passé sur le processeur graphique, il passait sur les conditions if / else à essayer de comprendre les limites des compartiments qu'il devait parcourir.

Plus précisément:

1. chaque thread obtient un ID, par cet ID, il récupère son triangle dans la mémoire (3 entiers chacun) et par ces 3, il récupère ses sommets (3 flottants chacun).

2. Ensuite, il transforme les sommets en points de grille entiers (actuellement 8x8x8) et les transforme en bornes triangulaires sur cette grille

3. Pour transformer les 3 points en bornes, il trouve le min / max de chaque dimension parmi chacun des points

Étant donné que le langage de programmation que j'utilise manque un intrinsèque minmax, j'en ai créé un moi-même, ressemble à ceci:

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)

Donc, en moyenne, il devrait y avoir 2,5 * 3 * 3 = 22,5 comparaisons qui finissent par prendre beaucoup plus de temps que les tests d'intersection triangle-bord réels (environ 100 * 11-50 instructions).

En fait, j'ai trouvé que le pré-calcul des compartiments requis sur le processeur (simple thread, pas de vectorisation), les empilant dans une vue gpu avec la définition du compartiment et faisant le gpu faire ~ 4 lectures supplémentaires par thread était 6 fois plus rapide que d'essayer pour comprendre les limites sur place. (notez qu'ils sont recalculés avant chaque exécution car j'ai affaire à des maillages dynamiques)

Alors pourquoi la comparaison est-elle si horriblement lente sur un GPU?

Les GPU sont des architectures SIMD. Dans les architectures SIMD, chaque instruction doit être exécutée pour chaque élément que vous traitez. (Il y a une exception à cette règle, mais cela aide rarement).

Ainsi, dans votre MinMaxroutine, non seulement chaque appel doit récupérer les trois instructions de branchement (même si en moyenne seulement 2,5 sont évaluées), mais chaque instruction d'affectation prend également un cycle (même si elle n'est pas réellement "exécutée") ).

Ce problème est parfois appelé divergence de thread . Si votre machine a quelque chose comme 32 voies d'exécution SIMD, elle n'aura toujours qu'une seule unité d'extraction. (Ici, le terme «thread» signifie essentiellement «voie d'exécution SIMD».) Ainsi, en interne, chaque voie d'exécution SIMD a un bit «Je suis activé / désactivé», et les branches ne font que manipuler ce bit. (L'exception est qu'au point où chaque voie SIMD devient désactivée, l'unité d'extraction passera généralement directement à la clause "else".)

Ainsi, dans votre code, chaque voie d'exécution SIMD fait:

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)

Il peut arriver que sur certains GPU, cette conversion des conditions en prédication soit plus lente si le GPU le fait lui-même. Comme l'a souligné @ PaulA.Clayton, si votre langage de programmation et votre architecture ont une opération de déplacement conditionnel prédite (en particulier une de la forme if (c) x = y else x = z), vous pourrez peut-être faire mieux. (Mais probablement pas beaucoup mieux).

De plus, il n'est pas nécessaire de placer le c < minconditionnel à l'intérieur elsede c > max. Cela ne vous économise certainement rien, et (étant donné que le GPU doit le convertir automatiquement en prédication), il peut être difficile de l'imbriquer dans deux conditions différentes.