Exploration du design Single Work-Item

La dernière fois nous avions parlé des différences entre les modèles d'exécution du FPGA et du GPU. Sur GPU, les kernels "single-workitem" (un seul workitem par workgroup) retourneraient une performance pauvre et n'utiliseraient qu'une faible partie de l'architecture.

En revanche le parallélisme de "pipeline" FPGA est idéal pour ce genre de design, Altera le recommande dès lors qu'on a des dépendances de données.

C'est donc par une approche single-workitem que nous commençons par prendre en main le SDK d'Altera ainsi que le cycle de développement et d'optimisation de kernels OpenCL pour FPGA, à travers l'exercice du cryptage de données par AES.

Premier jet : retour aux boucles

Dès lors qu'il commence à y avoir des dépendances de données ou des synchronisations nécessaires entre workitems, Altera encourage le design d'un kernel single-workitem, potentiellement plus adapté à l'architecture FPGA. Cela veut dire revenir à un design où un seul workitem fait le travail d'un workgroup entier et donc en pratique par un possible retour aux boucles.

Que l’on ait un design single-workitem ou un design avec des workgroups plus larges et opérations SIMD, les pipelines générés traduisent quelque part des séquences d’instructions très similaires. Il est donc raisonnable de penser que comprendre et optimiser le pipeline d'un design single-workitem, c'est potentiellement donner une meilleure base à d’éventuels designs plus élaborés (comme un design vectorisé).

C'est une opportunité pour nous de commencer à explorer différents paramètres influant sur le temps d'exécution et l'occupation de la carte FPGA, et de commencer à utiliser l'ensemble des outils Altera. Nous ré-écrivons donc les 4 fonctions subbytes, shiftrows, mixcolumns et addroundkey avec une boucle sur 16 caractères, afin qu'un seul workitem soit chargé de réaliser ces opérations sur un state entier.

Nous indiquons également une taille de workgroup requise de 1 workitem, en précédant la définition de notre kernel par la ligne d’attribut

__attribute__((reqd_work_group_size(1,1,1)))

Cette première approche présente les caractéristiques suivantes (chiffres obtenus grâce aux fichiers générés par le compilateur aoc, et la timeline visualisée sous aocl) :

On précise que cette première implémentation suit les recommandations d'Altera, favorisant une meilleure performance, notamment sur les points suivants :
- utilisation des qualificateurs « restrict » pour les pointeurs de tableaux disjoints
- alignement mémoire des tableaux texte à transférer depuis le host (grosse différence en temps d'exécution !)

Le profiler invoqué avec aocl nous révèle qu’il n’y a pas de stalling dans notre design et que l’occupancy des instructions est faible (pas mal sont en dessous de 20%). Ceci rejoint le fait que la performance de ce design semble mauvaise, mais ne nous aide pas à comprendre pourquoi. En revanche il montre quelque chose d’intéressant : la lecture / écriture des states en mémoire globale est efficace à 100% (burst-rate maximale correspondant à des transactions mémoires de 16 éléments simultanés); alors que la lecture de la sbox et des roundkeys n’est qu’à une burst-rate de 2. C’est inattendu, puisque ces requêtes mémoire sont similaires à la première, qui fonctionne très bien. On accède en effet à des adresses contigües en mémoire globale (256 et 16*11 éléments dépendamment de la table).

Bien plus tard nous remarquerons que bien qu’il n’y ait pas de différences dans le kernel en lui-même, les deux tableaux précédents n’étaient pas alignés en mémoire sur l’host. Ceci pouvait expliquer la maigre performance de ces boucles, mais n’a pas pu être vérifié puisque nous n’avions plus accès à la carte FPGA sur la machine à distance prêtée par Bittware.

Aocl n’a aucune information à nous rapporter sur des instructions faisant intervenir le modulo ou la division entière, qui devraient être a priori couteux.

Enfin, on constate que le temps d’initialisation de la board à un coût : elle doit se configurer de la façon dictée par le design .aocx qui lui est passé durant le run. Ce coût de 190 ms pour notre kernel ne représente qu’une fraction du temps d’exécution pour le moment. Mais on peut se demander quel sera son poids une fois le kernel optimisé, dont le temps d’exécution pourrait être en dessous.

Le B.A.-ba de l'optimisation FPGA

Le déroulage de boucle est l'optimisation la plus "évidente" sur FPGA. Pour extraire plus de parallélisme sur les étages du pipeline, rien de tel effectivement que d'en dérouler des parties: cela devrait bien améliorer la performance de notre design FPGA.

Considérons un ensemble de données devant passer par une boucle à n itérations, dont le pipeline généré pour chaque itération serait de profondeur k. Sans déroulage, on aurait jusqu'à k données traitées en parallèle dans un pipeline traduisant une itération de la boucle et ces mêmes données seront ré-injectées n fois au total. Pendant ce temps là, les données suivantes sont bloquées et cela cause du « stalling » (mauvais écoulement du flux de données) [figure 1]. En déroulant la boucle sur n itérations, on aurait un pipeline de profondeur n*k traitant autant de données en parallèle [figure 2], sans stalling, au prix d'une utilisation de hardware accrue.

Ce déroulage de boucle se fait à l’aide d’un pragma à l'entrée de celle-ci, indiquant le facteur de déroulage p (compris entre 1 et n).

#pragma unroll p
for (i=0 ; i<n ; i++) {...}

Pour autant, l'impact du déroulage de boucle sur le temps d'exécution d'une application FPGA n'est pas si aisé à comprendre et a déjà fait l'objet de recherches dans le passé (surtout les boucles imbriquées). Notre kernel single-workitem exhibe jusqu'à 3 niveaux de boucles imbriquées, présentées approximativement comme suit :

[in kernel :: loop 3]
for (round=0 ; round <9 ; round ++)
. [in mixcolumns :: loop 2]
. for (workitem=0 ; workitem<16 ; workitem++)
. [in gmul :: loop 1]
. for (bit=0 ; bit<8 ; bit ++)
. (...)

où gmul est la multiplication dans le corps G(2^8), dont la structure est utilisée par l'AES.

Remarque l’opération gmul pourrait être tabulée, étant une opération binaire sur des caractères (65k entrées possibles). Nous avons choisi de comparer initialement les deux architectures en leur demandant de passer par le calcul, à base d’opérations logiques de shift essentiellement.

Cette configuration présente déjà énormément de combinaisons possibles d'unrolling de boucle (déroulage partiel ou total, à un seul ou sur plusieurs niveaux de boucles imbriquées). Chaque essai requiérant une compilation coûteuse en temps, nous ne pouvons les explorer au hasard. La quantité d'appels à l'opération gmul suggère qu'une amélioration du pipeline généré pour celle-ci pourrait avoir un impact significatif sur le temps d'exécution de notre application.

Nous testons arbitrairement 3 designs, unroll1, unroll2 et unroll3, déroulant respectivement les boucles jusqu'au niveau 1, 2 ou 3 (par exemple unroll2 déroule les boucles 1 et 2), chacune avec un déroulage total. Nous obtenons les résultats suivants :

Cette première étude permet de montrer que le déroulage de boucle peut avoir un impact très important sur une application FPGA : les designs unroll1 et unroll2 présentent un speedup de presque x5, avec peu de différence en occupation des ressources. Elle montre aussi qu'il n'est pas aisé de prédire l'impact du déroulage de boucle sur l’application dans son ensemble : bien que le design unroll3 ait déroulé les boucles à tous les niveaux, il est le plus lent et le plus coûteux en utilisation de la carte FPGA. A l'inverse le design unroll1 est le plus rapide mais aussi moins coûteux en ressources que notre design initial, ce qui est contre-intuitif dans ce contexte de déroulage de boucles.

Le profiler ne montre toujours pas de stalling dans ces designs, ce qui est un peu étrange. En revanche on constate que l’occupation des instructions de unroll1 est aux alentours de 60% pour la plupart, contre moins de 20% pour le design initial, un maigre 4% pour unroll2 et moins de 1% pour unroll3. Considérant les performances très proches d’unroll1 et unroll2, cette différence dans la métrique « occupation » des instructions est inattendue.

Celui-ci n'utilisant qu'environ 20% au maximum des composants de chaque catégorie présente sur le hardware, on se pose naturellement la question de la scalabilité de ces chiffres par rapport au nombre de copies de ce pipeline que nous pourrons faire tenir sur la board.

Optimiser l'utilisation des ressources FPGA pour scaler

Après quelques essais, nous avons abouti à un design avec une efficacité bien meilleure que celle du design initial. Il est probablement améliorable, mais nous nous demandons déjà quelle performance nous pouvons atteindre en utilisant la totalité du hardware en réplicant le pipeline d'instructions associé. La scalabilité est un facteur important en HPC, et faire son étude dès maintenant est nécessaire afin d’avoir une idée plus précise d’à quel point l’utilisation des ressources va guider le processus d’optimisation général. La réplication se met en œuvre à l'aide de la ligne suivante, positionnée juste la définition du kernel : __attribute__(compute_units(k)) , k étant un nombre entier explicite. Ceci nous permet d'aller chercher un design jusqu'à k = 16 compute units (nombre déterminé empiriquement) et de visualiser les données.

Nous remarquons que l'utilisation des ressources ne croit pas de manière linéaire par rapport au nombre de répliques du pipeline, ce qui est quelque peu inattendu puisque le Guide d’Altera mentionnait que l’intégralité de la logique était répliquée. Du coup c'est pas facile de prédire non plus combien de compute units on peut utiliser au max... et il faudra compiler de multiples fois (joie).

Sur ce graphique nous pouvons voir que le facteur limitant du design est la RAM : le design ne peut réellement scaler au-delà de 16 cu car la quantité de blocs mémoires disponibles sur le FPGA est presque épuisée (92% utilisés). En revanche, les autres catégories de ressources de la carte ne sont exploitées qu’à environ 50% et ne posent pas de problème de scalabilité.

Un second graphique présente les temps d’exécution des kernels (en ms), ainsi que le speedup atteint par rapport au kernel 1cu.

Le design semble présenter une bonne scalabilité puisqu’avec 16 répliques du pipeline on obtient un speedup de presque 10 et ramenons le temps d’exécution du kernel à 228 ms. Cette scalabilité imparfaite s’explique par des phénomènes de contention I/O car tous les pipelines se partagent la bande-passante à la mémoire globale. Le profiler aocl nous informe que la burst rate moyenne pour la lecture / écriture des states est de 1, est que l’efficacité de ces transactions n’est que de 25% (comment est calculé ce dernier chiffre ?). Etrangement, la burst rate est toujours de 2 pour la sbox et les roundkeys…

La suite logique de l’optimisation de ce design single-workitem serait de tenter de réduire l’utilisation des ressources « RAM » du FPGA, qui est ici le facteur limitant de scalabilité. L’idée serait d’utiliser la mémoire constante au lieu de la mémoire partagée pour les look-up tables (sbox, roundkeys). Ne pas avoir à les copier depuis la mémoire globale devrait réduire la contention I/O, mais quel effet sur la performance des accès lors des calculs ainsi que la scalabilité du design?

Le prochain billet racontera donc nos aventures avec le design multi-workitem et mettra en évidence certaines limites du SDK...