F# Accelerator V2 : complément de README

Quand on est grognon, c’est pour la vie

Bon, c’est sympa de la part de Microsoft R & D de nous mettre à disposition leurs trouvailles, mais ça vaudrait le coup de passer un poil plus de temps à écrire le README. Ben oui, quitte à faire une documentation, autant la faire complète, ou carrément laisser l’utilisateur se débrouiller…

Introduction à F#, au GPGPU et à Accelerator

Que je vous explique : j’ai téléchargé Accelerator V2 pour tests. C’est une technologie qui permet de tirer partie de la carte graphique pour faire des calculs scientifiques. Comme un GPU est en gros 100 fois plus puissant qu’un CPU pour le calcul en virgule flottante, ça peut être extrêmement intéressant d’utiliser cette puissance. Jusqu’à il y a peu, ça voulait dire se lancer dans des API spéciales pour les GPU, comprendre la notion de pipeline de données, les différents niveaux de mémoire dans la carte, et tout le bazar. Ensuite, il y a eu du mieux avec CUDA et d’autres moyens d’utiliser ça en C/C++, mais personnellement, très peu pour moi : je ne suis pas passé à un langage de plus haut niveau comme le C# pour revenir au C++. J’en ai fait 3 ans, c’est déjà largement trop pour une vie.

Avec Accelerator, on a enfin une solution pour abstraire confortablement l’utilisation du GPU. Et ce dans un vrai langage. Un langage encore mieux que C#. Si, ça existe… Celui qui a dit “Java” prend la porte, merci 🙂 Ce langage est F#. Si vous êtes sur les blogs de DF, il y a de bonnes chances pour que ça vous dise quelque chose, mais au cas où, F# est un langage fonctionnel, c’est-à-dire qu’il permet de décrire un algorithme par ce qu’il doit faire au lieu de comment il doit le faire. L’exemple que je trouve assez parlant est le suivant : un swap de deux variables. En C#, vous écrivez :

Bref, vous décrivez à C# ce qu’il doit faire, comment il doit réaliser l’opération d’échange entre deux membres d’un tuple. En F#, et c’est fondamentalement différent, le code ressemble plutôt à ceci :

Simplissime, non ? Et ce n’est pas qu’une question de code plus court. En C, on peut faire du code court, mais abscons. Ici, rien de tout cela : un code simple, mais réduit au plus court seulement parce que F# se charge de la tringlerie. Vous ne lui dites pas comment la fonction doit faire son office, mais simplement “Je définis la fonction swap comme étant celle qui, quand je lui donne a suivi de b, me renvoie b suivi de a”. Comment ça marche derrière n’est pas votre problème. S’il a envie de transformer ça en utilisant un buffer pour stocker la version en cours d’inversion, tant mieux. S’il préfère utiliser une instruction du processeur réalisant un échange de cases mémoires, pareil.

Et c’est là que vient le lien avec les performances sur le GPGPU. Quand on programme sur une GPU, on a tous les problèmes du parallélisme, car il y a plusieurs pipelines de calcul, voire plusieurs dizaines actifs. Si vous avez déjà travaillé sur des programmes multithread, vous connaissez la difficulté de mise au point : gérer les threads, les locks, vérifier que la mémoire lue souvent est bien marquée comme volatile, etc. Bref, une sacrée galère parce que vous devez dire au code COMMENT il doit gérer le parallélisme. Au lieu de vous consacrer uniquement sur ce que vous voulez obtenir comme résultat. Vous voyez le truc : F# va nous débarrasser de toute cette problématique, et c’est en cela qu’il est le langage idéal pour du calcul en GPGPU.

Accelerator est le lien entre F# et les librairies pour utiliser le calcul sur GPGPU.

Retour sur le README

Bon, maintenant que je vous ai exposé le sujet, il faut que je revienne sur ce README que Microsoft donne à télécharger avec Accelerator. Je vous le recopie en entier, ça ne va pas faire sauter les serveurs, loin de là.

To use this Accelerator v2 F# sample you will need one of these two configurations:

* Visual Studio 2008 with the October 2009 F# CTP Add-in (http://go.microsoft.com/fwlink/?LinkId=151924), or
* Visual Studio 2010 Beta 2 with F# libraries installed

Build and run the sample by:

1)  Create a new F# Application Project in Visual Studio.
2)  Open the program.fs file from the Accelerator sample package.  Paste its contents into your F# Application Project’s program.fs file.
3)  Add these assembly references to your F# Application Project.
    – System.Drawing     – Microsoft.Accelerator.dll, which can be found in <Accelerator v2 install directory>\bin\Managed\{Release|Debug}

See http://msdn.microsoft.com/en-us/fsharp/default.aspx for more information about Microsoft F# tools and documentation.

Bon, je ne vais pas trop me plaindre du fait qu’il y ait à peine plus de dix lignes. A cheval regardé, on ne regarde pas les dents. Simplement, quitte à donner des étapes pour l’installation, ça aurait été bien de ne pas oublier une des plus importantes : registrer la DLL Accelerator.dll dans la version que vous utilisez, sinon ça ne marche pas. Et oui, ce n’est pas le code managé tout seul qui va taper le GPGPU. Entre les deux, ça passe par une librairie native et du DirectX, qui a le bon goût d’être masqué au programmeur, mais qu’il faut quand même avoir.

Bref, pour compléter ce README, il faut aller dans C:\Program Files\Microsoft\Accelerator v2\bin ou équivalent en fonction de votre répertoire d’installation. Là-dedans, vous avez le répertoire Managed dont le README parle, mais aussi (et surtout) deux répertoires x86 et x64, qui contiennent les deux versions de la fameuse DLL obligatoire pour que ça marche, et dont on ne parle pas.

Une fois arrivé là, le plus simple est de recopier cette DLL dans votre répertoire exécutable : c’est encore le meilleur moyen pour que ça marche sans vous poser de problème, et surtout éviter l’affreux message “Unhandled Exception: System.DllNotFoundException: Unable to load DLL ‘Accelerator.dll’: Le module spécifié est introuvable. (Exception from HRESULT: 0x8007007E)”

On passe au piège suivant

Bon, vous êtes contents de voir que le code livré avec le README compile. Oui, Microsoft vous livre quand même un exemple avec, c’est gentil. Voici le code :

Bon, le commentaire en haut dégageant toute responsabilité, on est habitué, et c’est logique vu que c’est encore de la R & D, mais est-ce que c’était trop demandé de ne pas considérer par défaut qu’on était en 64 bits ? Parce que moi, quand je publie un exemple avec une API, je m’arrange pour le faire le plus simple et général possible. Le but est que n’importe qui qui n’ait aucune connaissance à priori puisse copier / coller, et tout de suite faire fonctionner. Si la première chose qui se passe est une erreur comme ci-dessous, c’est mal barré :

Et oui, il plante, mais sans rien dire. Sympa… Ca aide drôlement les gens qui souhaitent juste découvrir la technologie. Ben oui, je ne suis pas en 64 bits, donc il faut penser à changer les trois dernières lignes de code par les versions DX9. Le code aurait déjà pu être regroupé en deux sections complètes avec les trois lignes complètes chacune. Et puis pourquoi mettre le 64 bits par défaut ? En mettant DX9 par défaut, ça marchait pour tout le monde, et ensuite, une note pour expliquer que ça peut être optimisé pour les machines 64 bits, avec le code commenté, et ça roulait…

L’est pas très finaud, celui-là…

C’est certainement ce que vous vous dites en lisant la paragraphe précédent. C’est vrai que ce n’est pas très complexe de lire le code source, et de voir qu’il y a une version DX9. Mais le problème est dans la façon de prendre le problème : personnellement, ma façon d’aborder une nouvelle technologie est de faire fonctionner un exemple, et ensuite seulement de regarder comment ça marche. Je ne vais pas me casser la tête à essayer de comprendre le code si c’est pour me rendre compte 45 minutes plus tard qu’en fait, non, ça ne marche pas. Du coup, j’étais à deux doigts de me dire “on laisse tomber, c’est pas mûr, leur truc”. Et je trouve que c’est dommage. Si Microsoft publie ce genre de choses, c’est pour que les gens les testent. Si ils ne leur mettent pas le pied à l’étrier au minimum, ce n’est pas la peine. Surtout que vous en conviendrez, ce n’est vraiment pas grand chose à changer au README et à l’exemple pour que ça se passe mieux. Ou alors le but est de filtrer de façon à ne garder que les gens suffisamment motivés pour enquêter et faire fonctionner le bidule. J’espère que ce n’est pas le cas…

Allez, fini de râler !

On passe au code proprement dit. Je me propose de vous guider ligne par ligne sur ce que fait ce fameux exemple. Première chose, écrémer : je laisse de côté la déclaration du point d’entrée du programme, des constantes rawSize et filterSize. Si c’est évident pour moi, je pense que ça doit l’être pour la majorité.

Cette fonction crée un tableau, en bouclant rawSize fois sur un calcul où on multiplie

let rawData = [| for i in 1 .. rawSize –> float32 (random.NextDouble() * float (random.Next (1,100))) |]

un float32 pris au hasard entre 0.0 et 1.0 par un entier, converti en float, pris lui entre 1 et 100. Bref, ça vous donne un tableau de float32 compris entre 0.0 et 100.0 à la fin. Si vous utilisez une fonction printfn “%A” rawData, et que vous réduisez la taille de rawSize à 4 pour faciliter la visualisation, vous obtenez le résultat suivant (par exemple, vu que c’est pris au hasard) :

[|58.5019684f; 35.348053f; 27.9487534f; 73.6845932f|]

La ligne suivante est intéressante :

use rawArray = new FloatParallelArray(rawData)

On définit une instance de FloatParallelArray, qui provient du namespace Microsoft.ParallelArrays fourni par Accelerator. Il s’agit d’un array de flottants, mais spécial pour utilisation dans les GPGPU.

On passe une ligne plus loin :

let filter = [1.0f .. float32 filterSize]

La syntaxe, spécifique à F#, est tout-à-fait dans la ligne de la simplicité d’écriture du langage. Pourquoi vous forcer à écrire une boucle, alors que vous voulez simplement obtenir un array avec des valeurs qui vont de 1 à filterSize ? Ecrivez le tout simplement avec .. au milieu, et F# se charge du boulot.

Bref, cette ligne est équivalente à :

let filter = [1.0f 2.0f 3.0f 4.0f 5.0f]

Dernière ligne du code “métier”, mais la plus compliquée :

let rec expr i = let e = filter.[i] * ParallelArrays.Shift(rawArray, i)
if i = 0 then
    e
else
    e + expr (i-1)

Le mot clé rec sert à spécifier que la fonction est récursive. La fonction expr, qui prend un paramètre i, est donc récursive, et définie de la manière suivante : on crée une valeur locale e qui prend comme valeur la i-ème valeur de la liste filter multipliée par “ParallelArrays.Shift(rawArray, i)“. Si on est à la récursion 0, on renvoie cette valeur, et sinon, on la renvoie sommée avec la récursion suivante.

C’est sur le calcul de e que ça se complique. Si on tente un printfn “%A” rawArray, on voit juste le ToString() standard, à savoir le type, en l’occurrence “Microsoft.ParallelArrays.FloatParallelArray”. Du coup, pas facile de voir ce que fait cette fameuse fonction Shift. Les commentaires parlent d’une convolution, donc on va jeter un oeil sur internet, en entrant ce mot clé, ainsi que le code de la fonction. On trouve assez facilement : en fait, Shift renvoie juste un tableau décalé du second paramètre (http://tomasp.net/blog/accelerator-intro.aspx pour des explications simples, et http://blogs.msdn.com/satnam_singh/archive/2010/01/11/a-c-implementation-of-a-convolver-using-accelerator-for-gpgpu-and-multicore-targets-using-linq-operators.aspx ou http://blogs.msdn.com/satnam_singh/archive/2009/12/15/gpgpu-and-x64-multicore-programming-with-accelerator-from-f.aspx si vous êtes plus courageux).

Le premier lien est vraiment intéressant, car plus accessible (le second blog est très bien, mais on a vraiment l’impression qu’il ne s’adresse qu’à ses collègues). Un truc particulièrement utile pour comprendre ce qui se passe est l’explication que FloatParallelArray n’est pas une classe de stockage de données, mais plutôt la représentation d’un calcul. C’est le target qui va se charger de déclencher ce calcul. L’auteur fait un parallèle très intéressant avec Linq. Plus je lis cet article, plus je le trouve excellent… Bref, qu’est-ce que vous faites encore ici ? Allez le lire, je vous dis ! C’est sur http://tomasp.net/blog/accelerator-intro.aspx et ne revenez que si vous avez besoin d’un article encore plus introductif : si, comme pour moi, vous comprenez 80%, c’est que vous n’avez pas besoin de mon article, dont le but est plutôt d’amener les gens de 0 à cet article.

Encore là ?

Si vous êtes encore là, c’est que ça vous a paru encore un peu abstrait, alors je vais tenter de faire le lien. Le mieux dans ce cas là est de laisser tomber pour l’instant la compréhension de la fonction expr. Passons aux trois lignes finales de code, en les prenant dans la version DX9. Le X64, c’est pour utiliser le multicore, et comme son nom le précise, ça ne fonctionne qu’en 64 bits.

La dernière ligne sert juste à afficher le résultat du calcul. Celui-ci est réalisé par les deux lignes précédentes. La première déclare un target, c’est-à-dire en gros un moteur de calcul. Et c’est à ce moteur de calcul qu’on va demander d’évaluer la fonction expr(filterSize – 1), en l’occurrence pour nous la fameuse fonction récursive avec 5 – 1 = 4 comme paramètre.

Pour mieux comprendre, débarrassons nous en premier du hasard et d’un peu de complexité : on va laisser rawSize à 4, mais baisser filterSize à 3, et au lieu de prendre les valeurs de notre array rawData au hasard, on va utiliser la ligne suivante :

Ce qui va nous ramener un tableau avec [1.0f 2.0f 3.0f 4.0f].

Si on calcule récursivement la fonction en partant de filterSize – 1 = 2, le Shift du tableau par 2 va nous donner [3 4 4 4] (je ne mets pas les notations flottantes complètes pour que ça soit plus simple à lire) : le Shift décale les valeurs, mais en laissant les premières telles quelles.

Quand on multiplie par filter.[2], c’est-à-dire 3, on se retrouve avec [9 12 12 12]. Comme on est sur le niveau 2, il faut ajouter le niveau 1, puis récursivement le niveau 0. Au niveau 0, c’est simple, on renvoie simplement le tableau [1 2 3 4]. Au niveau 1, on peut faire exactement le même calcul de e, et on obtient [4 6 8 8]. Bref, en fin de récursion, quand on a ajouté tout ça, on se retrouve avec [14 20 23 24].

Ce que nous confirme le test :

Pour faire plus clair, on peut le prendre par l’autre bout : on met de côté la récursion, en considérant qu’elle va simplement ramener e(i=0) + e(i=1) + e(i=2).

Et si on prend les niveaux de récursion de manière séparée, on a :

e(i=0) => filter(0) * [1 2 3 4] = 1 * [1 2 3 4] = [1 2 3 4]

e(i=1) => filter(1) * Décalage de  [1 2 3 4] par 1 unité = 2 * [2 3 4 4] = [4 6 8 8]

e(i=2) => filter(2) * Décalage de [1 2 3 4] par 2 unités = 3 * [3 4 4 4] = [9 12 12 12]

Et si on somme tout ça, on a bien [9+4+1 12+6+2 12+8+3 12+8+4], soit [14 20 23 24].

Retour sur le target

On revient à l’explication initiale de F# : c’est le but du target de décider comment ce calcul va être fait. Dans le FloatParallelArray, vous ne faites que définir le calcul que j’ai détaillé ci-dessus. C’est ensuite la force de F# dans le target de décider comment il va utiliser le GPU pour réaliser le calcul. La seconde ligne du calcul consiste à déclarer au target qu’il doit évaluer expr(filterSize – 1), ou expr(2) sur l’exemple simplifié, puis renvoyer le résultat de ce calcul sous forme d’un array à une dimension. Le résultat peut ensuite être affiché.

Bref, et c’est le plus important à comprendre : on n’écrit pas l’algorithme, mais la définition du calcul à réaliser, et on passe ensuite cette définition de fonction un peu à la mode d’un pointeur de fonction / d’un delegate à la fonction du target qui se débrouille pour travailler avec ça.

Ce qui se passe derrière (en très gros)

Bon, je n’ai pas la prétention de comprendre ce qui se passe derrière, mais d’après ce que j’ai lu dans quelques blogs et docs sur les calculs par GPGPU, il semblerait que ce soient les pixel shaders des cartes qui soient utilisés pour simuler des vecteurs à 1 ou 2 dimensions. Schématiquement, comme les cartes GPU sont optimisées pour calculer des couleurs sur des points, on peut se servir des valeurs (de position ou de couleur, je ne sais pas) pour coder les valeurs de n’importe quel vecteur. Ensuite, le codage se fait d’une manière ou d’une autre en fonction de la librairie d’utilisation des GPGPU, et c’est justement le rôle des fonctions ToArray1D ou ToArray2D de l’API Accelerator.

Mais prenez ceci avec des pincettes : c’est la façon dont je le comprends, mais ce n’est pas encore très clair. J’essaierai de l’être plus dans un prochain article, quand je serai plus au point sur cette technologie, qui est pour moi essentielle. En attendant, j’espère avoir réussi à atteindre mon humble but, à savoir compléter le README de Microsoft et mieux documenter l’exemple de façon qu’une personne avec absolument 0 connaissance de F# et des GPGPU comprenne ce qui se passe dans l’exemple livré avec. Merci par avance de vos commentaires sur ce qui pourrait manquer pour atteindre ce but.