Tableaux multi-dimensionnels efficients : mythe ou réalité ?

Outre les types de données standards, les tableaux constituent l’un des meilleurs outils du développeur. Dès lors, qu’il faut structurer une série de données, on fait appel aux tableaux et bien souvent aux tableaux multi-dimensionnels. L’algèbre linéaire illustre parfaitement cette importance avec les matrices. De fait, une mauvaise implémentation des tableaux influence directement les performances des applications. De nombreuses bibliothèques ont ainsi été développées pour l’algèbre linéaire et la gestion des opérations matrice-matrice. A titre d’exemple, on peut citer Eingen, MTL4, Blitz, NT2, HPClib, etc. Ces dernières soulèvent l’importance du stockage, de la façon d’accéder aux éléments et l’ordre de parcours des tableaux.  Aussi, ajoutons qu’il est nécessaire, pour des raisons de performance, d’adapter les algorithmes en fonction des formats de stockages.

Cet article est le premier d’une série que nous intitulons « vers une bibliothèque de tableaux multi-dimensionnels efficace et facile d’utilisation en C++ ». De fait, cette série abordera diverses notions nécessaires à l’implémentation des tableaux multi-dimensionnels efficients en C++. Nous insisterons particulièrement sur les critères de facilité d’utilisation, d’efficacité et de performance.  Nous décrivons ci-dessous le cahier des charges de notre bibliothèque.

Cahier des charges

Un tableau multi-dimensionnel contient les propriétés { T, Dim, N } suivantes :

  • Le type des éléments : T ;
  • Le nombre de dimensions : Dim (entier positif) ;
  • La taille dans chacune des dimensions : N (tableau 1D de Dim entiers).

Il est possible de faire les opérations suivantes :

  • Accès aux éléments
    • Par un index entier
      • Renvoie un élément si le tableaux a une seule dimension
      • Renvoie un tableau multi-dimensionnel de dimension (Dim-1) sinon
    • Par un index multi-dimensionnel (de type entier et de dimension Dim’ <= Dim)
      • Renvoie un entier si Dim’ = Dim
      • Renvoie un tableau multi-dimensionnel (une « tranche ») de dimension (Dim – Dim’) sinon
  • Opérations binaires : arithmétique (addition, division, etc.), logique (et, ou) et de comparaison (inférieur, égale, etc)
    • Avec des scalaires de type T’ si l’opération s’applique à T et T’ et renvoie R
      • Renvoie un tableau de taille N et de type R
    • Avec un tableau caractérisé par { T’, Dim’, N’ } tel que
      • L’opération s’applique à T et T’ et renvoie R
      • N=N’ ou s’ils sont de taille différente : N est inclus dans N’ ou réciproquement, par exemple N=(1,2,3,4) et N’=(1,2)
      • Renvoie un tableau de la taille du plus des deux arguments, et de type R
  • Application de fonctions mathématiques à un argument
    • Par exemple sin, cos ou racine carré
    • Uniquement lorsque l’opération est définie sur T et renvoie R
    • Renvoie un tableau de même taille et de type R
  • Application de la transposée généralisée : permutation des dimensions
    • Par exemple transformer un tableau de taille (1,2,3) en tableau de taille (2,1,3)
  • Application de fonctions matricielles quand D=2
  • Application de fonctions arbitraires dans des « squelettes » de type map/reduce
    • Par exemple inversion matricielle de toutes les « tranches » 2D d’un tableau 3D en faisant map(inverse)

Objectifs

Objectif 1 : facilité d’utilisation

Comme mentionné en introduction, notre implémentation devrait être facile d’utilisation. L’exemple ci-dessous illustre ce que nous sous-entendons par « facilité d’utilisation ».

Exemples de résultat souhaité :
array<int, 2> ints = { {4,9,16,25} , {10,20,30,40} }; // initialise les valeurs
assert( sqrt(ints[0]) == array<int, 1> { 2,3,4,5 } ); // vérifie la racine carrée
array<float, 3> floats(4,2,2); // initialise la taille
floats = ints; // valide selon les règles ci-dessus pour les opérateurs binaires : (4,2,2) et (4,2) sont compatibles
floats[0] = 0; // floats(0, 0..2, 0..2) = 0
assert( floats == array<float,3> { {{0,9,16,25} , {0,20,30,40}}, {{0,9,16,25} , {0,20,30,40}} });

Objectif 2 : performance

Comme évoqué plutôt,  une attention particulière sera portée aux performances de notre bibliothèque. En effet, comme le montrent plusieurs travaux (Goto, Gottschling, Drepper), le stockage des tableaux est un élément essentiel  pour la performance. Un stockage adapté à la problématique de l’application et aux caractéristiques machines permet de réduire les défauts de mémoire cache et surtout les défauts de TLB (Translation lookaside buffer).  Nous souhaitons donc allier cette optimisation des modes de stockage et la facilité d’utilisation des tableaux :

      • optimisation de l’ordre de stockage des éléments en mémoire pour améliorer l’utilisation des caches;
      • overhead le plus petit possible lié à la facilité d’utilisation. Par exemple l’utilisation de vue lors de l’indexation partielle.

Conclusion

Cet article résume ainsi le cahier des charges de notre bibliothèque dédiée à la gestion de tableaux multi-dimensionnels. Deux difficultés majeures sont à noter pour la réalisation de ce projet :

      • traduction des contraintes du cahier des charges en code, par exemple faire une méthode qui renvoie un tableau ou un scalaire selon l’argument;
      • obtention de bonnes performances pendant l’utilisation.

A terme, nous souhaitons rendre notre implémentation compatible GPU et au Xeon Phi et l’intégrer à notre bibliothèque HPCLib. Les prochains articles de cette série détailleront les différentes étapes de nos développements et couvriront un large spectre du langage de programmation C++ (Expression templates, SFINAE, etc).

Références :

[Drepper, 2007] DREPPER, U. (2007). What every programmer should know about memory. http://people.redhat.com/drepper/cpumemory.pdf.

[Faverge, 2009] FAVERGE, M. (2009). Ordonnancement hybride statique-dynamique en algèbre linéaire creuse pour de grands clusters de machines NUMA et multi-coeurs. Thèse de doctorat, Université Sciences et Technologies-Bordeaux I

[Goto et van de Geijn, 2008a] GOTO, K. et VAN DE GEIJN, R. (2008a). Anatomy of high-performance matrix multiplication. ACM Transactions on Mathematical Software (TOMS), 34(3):12.

[Goto et van de Geijn, 2008b] GOTO, K. et VAN DE GEIJN, R. (2008b). High-performance implementation of the level-3 BLAS. ACM Transactions on Mathematical Software (TOMS), 35(1):4.

[Gottschling et al., 2009] GOTTSCHLING, P.,WISE, D. et JOSHI, A. (2009). Generic support of algorithmic and structural recursion for scientific computing. International Journal of Parallel, Emergent and Distributed Systems, 24(6):479–503.

[Van Zee et van de Geijn, 2012] Van ZEE, F. G. et van de GEIJN, R. A. (2012). BLIS : A Framework for Generating BLAS-like Libraries. FLAME Working Note #66. Technical Report TR-12-30, The University of Texas at Austin.

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *