Aujourd’hui, nous parlons un peu des subtilités qui font qu’un FPGA … ne peut pas fonctionner comme un GPU, même si vous en avez très envie.

Il existe d’une part des différences dans leur modèle d’exécution, mais il y a aussi des aspects du SDK OpenCL FPGA d’Altera (pardon, je veux dire Intel !) qui limitent les tentatives, puisqu’il vous faudra commencer par convaincre le compilateur que votre cause est juste et louable. L’ensemble de ces observations permet de nous aiguiller dans le choix de notre première approche du design FPGA.

Il est important de comprendre que dès lors qu’on a une application non-triviale, i.e réalisant un certain nombre d’opérations sur les données en entrée, le degré de parallélisme le plus naturel et le plus puissant extrait par le FPGA est celui dicté par la longueur du pipeline d’instructions généré par le design. Une application performante sur FPGA sera sans doute une application qui permettra « un bon écoulement » du flux des données à travers ce pipeline.

On en déduit qu’on peut déjà extraire un parallélisme significatif d’un code séquentiel, dès lors qu’il y a des boucles de calcul sur un ensemble de données. Les éléments sont alors traités en parallèle, non pas sur un modèle SIMD (Single Instruction Multiple Data) mais assimilable à du MIMD (Multiple Instructions Multiple data) : c’est-à-dire qu’à un cycle donné, à un étage donnée du pipeline, une instruction est réalisée sur des données. Mais d’un étage à l’autre du pipeline ni ces données ni ces instructions ne sont les mêmes. Un kernel OpenCL séquentiel efficace muni de quelques directives peut donc constituer une bonne base dont la logique pourra être dupliquée par la suite (vectorisation sur la « largeur » du pipeline, ou réplication du pipeline entier).

Design multi-workitem et opérations SIMD : un équivalent au modèle GPU ?

Un kernel « single workitem » s’exécute avec un unique workitem par workgroup, à l’inverse d’un kernel « multi-workitem ». Si vous avez déjà touché au GPU, alors vous aurez naturellement envie d’utiliser des kernels multi-workitems. Pourquoi? Parce que faire des kernels avec un seul workitem (ou encore « thread ») c’était n’utiliser qu’une infime partie de l’architecture, qui devenait alors moins performante que votre CPU. Sur FPGA, on pourrait imaginer que les workgroups et les workitems s’enquillent dans un pipeline d’instructions les uns derrière les autres, et du coup l’idée d’avoir un design single-workitem ne semble pas spécialement choquante si on a plein de workgroups qui s’exécutent.

Il est même possible d’utiliser des opérations SIMD sur FPGA et donc de proposer des designs vectoriels appliquant une opération donnée sur plusieurs workitems d’un même workgroup simultanément, au travers d’un design nécessairement multi-workitem. Le guide Altera mentionne que la taille limite d’une opération vectorielle est 16, ce qui correspond à la taille d’un demi-warp GPU. On peut alors se demander à quel point le FPGA rejoint le modèle d’exécution GPU dans ce cas.

Sur GPU, un workgroup est exécuté sur un multiprocesseur (Streaming Multiprocessor en terminologie NVidia) et l’ensemble des instructions de ses workitems est exécuté par groupes de 16 ou 32 threads (« warps ») à coup d’instructions SIMD. Ces warps sont schédulés sur les différents coeurs du multiprocesseur en question et tant que le SMP trouve des warps dont les instructions sont exécutables, quitte a passer d’un warp à un autre pour recouvrir une synchronization ou une requête mémoire, on utilise notre architecture efficacement.

La problématique de la synchronisation sur FPGA est en revanche plus forte. En particulier, le compilateur fait savoir que:
– si une barrière / synchronisation est requise, alors un workgroup ne peut comporter qu’au maximum 256 workitems.
– s’il estime que les workitems peuvent atteindre une barrière dans le désordre, alors seulement 2 workgroups pourront être simultanément dans le pipeline.

Ces restrictions pourraient s’avérer catastrophiques pour la performance et découragent fortement l’utilisation de designs n’allant pas dans le sens de l’architecture.

Considérons 2 fonctions successives appliquées sur un workgroup entier de taille n*k dont l’output de la première (un tableau n*k données) est l’input de la seconde et où chaque workitem doit modifier une unique entrée de ce tableau. En considérant une taille d’opération vectorielle de k, le workgroup s’étale donc sur n étages successifs du pipeline.

Une synchronisation de l’ensemble des workitems requièrerait que la première fonction ait été appliquée aux n*k données du workgroup avant que la seconde ne puisse être appliquée à une quelconque donnée sortante. En supposant qu’un étage du pipeline consomme un cycle, ceci peut se traduire par une période de (n-1) cycles entre le moment où la première instruction et la seconde ont été exécutées, et peut-être donc une surconsommation des ressources hardware créant ces (n-1) étages « d’attente ».

De manière générale, toute rétro-dépendance ou complexité de ce type est mauvaise pour l’écoulement des données à travers un pipeline d’instructions. Altera décourage fortement ces designs exhibant ce genre de comportements, et préconise l’utilisation d’un kernel single-workitem à la place. C’est là que réside la différence fondamentale entre l’approche FPGA et GPU.

« Ouais mais moi je veux vectoriser des trucs ! »

Oui: la vectorisation, c’est le bien. On le redécouvre d’ailleurs toutes les semaines dans les articles publiés sur Linkedin, et c’est ce que les constructeurs et les éditeurs de logiciel de profiling se tuent à nous rappeler. Du « bête » CPU au GPU en passant par le MIC d’Intel, tous soulignent les bienfaits de la vectorisation: c’est dans le manuel qui va avec et la formule magique pour calculer la puissance crête.

En réalité, ce qu’on raconte ce n’est pas qu’il faut absolument des kernels single-workitem, mais qu’il faudrait idéalement accoucher d’un design où il n’y a pas de rétro-dépendances des données s’écoulant dans le pipeline. En particulier, si dans l’exemple de la figure 1 ci-dessus avec nos fonctions 1 et 2 on se retrouve avec une taille d’opération vectorielle égale à la taille du workgroup exécuté, c’est gagné: le workgroup ne s’étale que sur un unique étage du pipeline et avance « cadencé », sans rétro-dépendance de données. Mais est-ce facile à mettre en oeuvre avec OpenCL et ce SDK?

En effet, le compilateur ne semble pas pouvoir générer un design vectorisé dès lors qu’il y a une ambigüité sur la charge de travail de chaque thread (c’est-à-dire que les instructions réalisées dépendent de l’indice du thread). Cette problématique est de taille, puisqu’on va la rencontrer naturellement dans toute parallélisation du travail sur les indices d’une boucle parcourant par exemple les indices d’un tableau en input dans notre kernel.

Sur GPU, le branching dû à une instruction conditionnelle implique « seulement » une séquentialisation de l’exécution des différentes branches. C’est-à-dire que dans un warp « divergeant », on exécute à tour de rôle les différentes branches empruntées durant le run, à coup d’instructions SIMT sur les threads concernés. Sur FPGA, ceci est apparemment rédhibitoire d’un point de vue vectorisation, ce que nous verrons en pratique dans un prochain billet.

En particulier on peut se poser des questions quant à des instructions du type :

for (i=idx ; i<ARRAY_SIZE ; i+= 16) (…)

for (i=idx ; i <4096 ; i+= grid_size)

où idx est l’indice d’un workitem, ARRAY_SIZE une variable indiquant la valeur d’un tableau en input, et grid_size la taille d’un stride permettant typiquement de distribuer de manière cyclique un grand nombre d’itération sur un plus petit nombre de workitems.

Ces instructions apparaissent typiquement lorsque l’ensemble des workitems doit travailler sur un tableau dont la taille peut ne pas être connue à la compilation, et pourrait excéder le nombre de workitems utilisés (ou utilisables).

Sachant que le kernel OpenCL est compilé à part, comment le compilateur peut-il savoir à ce stade que les workitems auront le même nombre d’itérations à traiter, vu qu’il ne connait pas le nombre de workitems ou workgroups? Comment l’aider?

Nous poursuivrons dans le prochain billet avec l’optimisation de ce design Single Work-Item.

La suite de la série FPGA est disponible ici.

Crédit : Damien DUBUC