Basic Linear Algebra Subprograms

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Basic Linear Algebra Subprograms (BLAS) sont un ensemble de fonctions standardisées (interface de programmation) réalisant des opérations de base de l'algèbre linéaire comme des additions de vecteurs ou des multiplications de matrices. Ces fonctions ont d'abord été publiées en 1979 et sont utilisées dans des bibliothèques plus développées comme LAPACK. Largement utilisées pour le calcul haute performance, ces fonctions ont été développées de manière très optimisée par des constructeurs de calculateurs comme Intel et AMD, ou encore par d'autres auteurs (Goto (en) BLAS et ATLAS (en) - une version portable de BLAS - en sont des exemples). Les tests de performance LINPACK utilisent massivement la fonction multiplication de matrices générales (DGEMM) de BLAS.

Nécessité de BLAS[modifier | modifier le code]

Jusqu'au début des années 1970, les codes de calcul rapide utilisaient des routines optimisées codées directement en langage machine pour l'évaluation de certaines fonctions[1]. Entre 1972 et 1978, on identifia les fonctions les plus couramment appelées dans ces programmes. Ainsi, en 1964, alors qu'il travaillait sur le projet de l'IBM 7030, Sweeney[2] rassembla des statistiques sur les calculs en virgule flottante les plus fréquemment exécutés sur les IBM 704, et s'aperçut que les sommations simples représentaient 11% de l'effectif[3]. De ces programmes, on fit des subroutines à nom générique, afin qu'on puisse les utiliser en boîte noire : ainsi, les programmes devenaient plus facile à lire et à débugger, tandis qu'on continuait à accélérer le temps d'exécution de ces routines.

Certains ordinateurs permettaient d'accélérer le calcul d'opérations (sommes ou produits de nombres en virgule flottante) dès qu'on enchaînait plus d'une dizaine de ces opérations à la suite (architecture pipeline) ; d'autres, tels le RS/6000, disposaient d'une architecture leur permettant de calculer à la même vitesse (avec le même nombre de cycles d'horloge) un produit suivi d'une addition (x*y +z) , qu'un produit simple (x*y) ou une addition (x + y)[1] ; d'autres spécificités-machine (présence de coprocesseurs, etc.) apparaissaient sur le marché, qu'il fallait exploiter. C'est ainsi qu'entre 1984 et 1986, BLAS fut augmentée d'opérations de niveau 2 (produits matrice-vecteur = BLAS 2). Les progrès du calcul parallèle montraient que l'architecture mémoire joue un rôle critique sur le temps d'accès aux données ; que plusieurs ordinateurs utilisent une mémoire cache, à accès rapide : une ré-écriture des algorithmes, localisant au maximum les calculs dans le cache, provoque une accélération spectaculaire. En 1987-88, les opérations de niveau 3 (produits et sommes matrice-matrice, BLAS 3) voyaient le jour : BLAS 3 incite les programmeurs à privilégier les calculs par blocs avec des blocs pleins (à minimum de termes nuls).

Trois niveaux de complexité[modifier | modifier le code]

Les opérations d'algèbre linéaire mises en œuvre dans BLAS sont réparties en 3 niveaux de complexité croissante.

Niveau 1
Ce niveau contient les opérations sur les vecteurs de la forme
y \leftarrow \alpha x + y,
\alpha est un scalaire et x et y sont des vecteurs ; ainsi que les opérations produit scalaire et norme, parmi tant d'autres.
Niveau 2
Ce niveau contient entre autres les opérations de type matrice-vecteur de la forme
y \leftarrow \alpha A x + \beta y,
\alpha et \beta sont des scalaires, x et y sont des vecteurs et A est une matrice ; ainsi que la résolution de T x = y en x lorsque T étant une matrice triangulaire.
Niveau 3
Ce niveau contient entre autres les opérations de type matrice-matrice de la forme
C \leftarrow \alpha A B + \beta C,
\alpha et \beta sont des scalaires et A, B et C sont des matrices ; ainsi que la résolution de B \leftarrow \alpha T^{-1} B pour des matrices triangulaires T. Le niveau 3 contient notamment la très usitée opération de multiplication de matrices générales (DGEMM).

Mises en œuvre[modifier | modifier le code]

ATLAS
Automatically Tuned Linear Algebra Software (en), une implémentation en source libre de BLAS pour les langages C (par interface de programmation) et Fortran 77. Voir [1]
BLAS de Goto
Mise en œuvre de BLAS de Kazushige Goto (en), sous licence BSD, adaptée en particulier aux architectures Intel Nehalem/Atom, VIA Nano, AMD Opteron. Voir [2]
BLAS de Netlib
C'est la mise en œuvre officielle, de référence, disponible sur le site Netlib, écrite en Fortran 77. Voir [3]
CBLAS de Netlib
Interfaçage de référence de BLAS pour le langage C. Il est également possible (et coutumier) d'appeler BLAS en Fortran, directement depuis un code écrit en C. Voir [4]
clAmdBlas
Une implémentation d'AMD en OpenCL des 3 niveaux, et optimisée pour les processeurs graphiques d'AMD supportant OpenCL. Voir [5]


Notes et références[modifier | modifier le code]

Notes[modifier | modifier le code]

  1. a et b Cf. Higham, Accuracy and Stability of Numerical Algorithms, Soc. Ind. Appl. Math.,‎ 1996, 690 p. (ISBN 0-89871-355-2), p. 60.
  2. D'après D. W. Sweeney, « An analysis of floating-point addition », IBM System Journal, no 4,‎ 1965, p. 31-42.
  3. Il porta ses efforts sur le décalage d'exposant préalable à l'addition des mantisses, et c'est ainsi que fut conçu le circuit shifter de l'IBM 7030. Cf. Higham, Accuracy and Stability of Numerical Algorithms, Soc. Ind. Appl. Math.,‎ 1996, 690 p. (ISBN 0-89871-355-2), p. 60.

Voir aussi[modifier | modifier le code]

Liens externes[modifier | modifier le code]