Pourquoi l'efficacité du travail est-elle souhaitée dans la programmation GPU?

J'ai lu l'article suivant sur la façon de faire un scan parallèle dans CUDA:

https://developer.nvidia.com/gpugems/GPUGems3/gpugems3_ch39.html

Dans cet article, l'accent est mis sur le fait que l'analyse soit "efficace". En d'autres termes, un algorithme GPU ne devrait pas effectuer plus d'ajouts qu'un algorithme CPU, O (n). Les auteurs présentent deux algorithmes, un "naïf" qui fait des ajouts d'O (nlogn), et un qu'ils considèrent "efficace au travail". Cependant, l'algorithme efficace fonctionne deux fois plus d'itérations de boucle.

D'après ma compréhension, les GPU sont simplement des processeurs SIMD géants et devraient fonctionner en mode verrouillé. Faire deux fois plus de boucles dans l'algorithme "efficace au travail" semble impliquer que de nombreux threads seront inactifs et diminueront les performances à long terme. Qu'est-ce que je rate?

Tout d'abord, re: "Les GPU sont simplement des processeurs SIMD géants et devraient fonctionner en mode verrouillé", c'est un peu plus compliqué que cela. L' ensemble du GPU ne s'exécute pas en boucle. Les threads de shader sont organisés en groupes de 32 appelés "warps" (sur NVIDIA; sur AMD ce sont des groupes de 64 appelés "fronts d'onde", mais même concept). Au sein d'une chaîne, tous les threads s'exécutent en même temps qu'un tableau SIMD. Cependant, différentes chaînes ne sont pas en phase les unes avec les autres. De plus, certains warps peuvent être en cours d'exécution tandis que d'autres peuvent être suspendus, tout comme les threads CPU. Les warps peuvent être suspendus soit parce qu'ils attendent quelque chose (comme des transactions de mémoire à retourner ou des barrières à effacer), soit parce qu'il n'y a pas

Maintenant, revenons à votre question. Je peux voir de deux manières que l'algorithme "efficace au travail" de ce document semble être plus efficace que l'algorithme "naïf".

1. La version efficace au travail nécessite deux fois moins de threads pour commencer. Dans l'algorithme naïf, ils ont un thread par élément de tableau; mais dans la version efficace, chaque thread fonctionne sur deux éléments adjacents du tableau et n'a donc besoin que de la moitié du nombre de threads du tableau. Moins de fils signifie moins de chaînes, et donc une plus grande partie des chaînes peut être active.

2. Bien que la version efficace nécessite plus d'étapes, cela est compensé par le fait que le nombre de threads actifs diminue plus rapidement et que le nombre total de threads actifs sur toutes les itérations est considérablement plus petit. Si une chaîne n'a pas de threads actifs pendant une itération, cette chaîne passera simplement à la barrière suivante et sera suspendue, permettant aux autres chaînes de s'exécuter. Ainsi, avoir moins de chaînes actives peut souvent être rentable en temps d'exécution. (Cela implique implicitement que le code GPU doit être conçu de manière à ce que les threads actifs soient regroupés dans le moins de chaînes possible - vous ne voulez pas qu'ils soient dispersés de manière clairsemée, car même un thread actif forcera la chaîne entière pour rester actif.)

   Considérez le nombre de threads actifs dans l'algorithme naïf. En regardant la figure 2 de l'article, vous pouvez voir que tous les threads sont actifs à l' exception des 2 premiers ^k sur la k ème itération. Donc, avec N threads, le nombre de threads actifs va comme N - 2 ^k . Par exemple, avec N = 1024, le nombre de threads actifs par itération est:

   1023, 1022, 1020, 1016, 1008, 992, 960, 896, 768, 512
   

   Si je le convertis en nombre de chaînes actives (en divisant par 32 et en arrondissant), j'obtiens:

   32, 32, 32, 32, 32, 31, 30, 28, 24, 16
   

   pour une somme de 289. D'un autre côté, l'algorithme efficace commence avec deux fois moins de threads, puis réduit de moitié le nombre de threads actifs à chaque itération jusqu'à ce qu'il descende à 1, puis commence à doubler jusqu'à ce qu'il revienne à la moitié de la taille du tableau à nouveau:

    512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512
   

   Conversion de ceci en chaînes actives:

   16, 8, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 4, 8, 16
   

   La somme est de 71, ce qui n'est que le quart. Vous pouvez donc voir qu'au cours de toute l'opération, le nombre de chaînes actives est beaucoup plus petit avec l'algorithme efficace. (En fait, pour une longue course au milieu, il n'y a qu'une poignée de chaînes actives, ce qui signifie que la majeure partie de la puce n'est pas occupée. S'il y a des tâches de calcul supplémentaires en cours d'exécution, par exemple à partir d'autres flux CUDA, elles pourraient s'étendre pour remplir cette espace inoccupé.)

Cela étant dit, il est regrettable que l'article sur les gemmes de GPU n'explique pas clairement tout cela, se concentrant plutôt sur l'analyse du "nombre d'ajouts" de big-O qui, bien que pas totalement hors de propos, manque beaucoup de détails sur la raison pour laquelle cet algorithme est plus rapide.