Disposition des lignes par rapport aux colonnes par colonnes

16

Dans la programmation de calculs matriciels denses, y a-t-il une raison de choisir une disposition en ligne principale de la disposition sur la disposition en colonne principale?

Je sais qu'en fonction de la disposition de la matrice choisie, nous devons écrire le code approprié pour utiliser efficacement les mémoires cache à des fins de vitesse.

La disposition en ligne principale semble plus naturelle et plus simple (du moins pour moi). Mais les bibliothèques majeures comme LAPACK écrites en Fortran utilisent la disposition principale des colonnes, donc il doit y avoir une raison pour avoir fait ce choix.

Bouddha souriant
la source
Si nous considérons le calcul de b = A * x avec x vecteur de colonne, pour la ligne A majeure, nous pouvons utiliser les produits internes des vecteurs, A (i,:) ^ T x pour obtenir b (i); pour les colonnes majeures, nous ne pouvons avoir besoin que de vecteurs multiplicateurs scalaires, sum_i A (:, i) x (i). Il me semble que la colonne major est bien mieux! Qu'est-ce que tu penses?
Hui Zhang
Entraînez-vous à aimer la colonne majeure. C'est facile lorsque vous visualisez des vecteurs sous forme de colonnes ou leur transposition sous forme de lignes. Il rend la visualisation de la multiplication matricielle très simple et permet de suivre facilement de nombreuses mathématiques publiées.
Mike Dunlavey

Réponses:

18

La disposition principale des colonnes est le schéma utilisé par Fortran et c'est pourquoi il est utilisé dans LAPACK et d'autres bibliothèques.

En général, il est beaucoup plus efficace en termes d'utilisation de la bande passante mémoire et de performances du cache d'accéder aux éléments d'un tableau dans l'ordre dans lequel ils sont disposés en mémoire. Selon la façon dont vos matrices sont stockées, vous voudrez choisir des algorithmes qui en profitent.

stockage interne Stockage interne du format principal de colonne

Brian Borchers
la source
11

Dans le vide sans considérer aucun logiciel existant, il n'y a aucune raison de préférer le majeur de colonne au majeur de ligne du point de vue du code. Cependant, la plupart des publications mathématiques sont écrites de manière à regrouper les vecteurs dans une matrice en les stockant sous forme de colonnes plutôt que de lignes. Par exemple, lorsque vous écrivez l'équation de valeur propre complète , le XUNEX=XΛXmatrice contient tous les vecteurs propres écrits en colonnes. Vous ne le voyez jamais vraiment écrit dans l'autre sens (bien que j'entende que les statistiques aiment les vecteurs de ligne). Par conséquent, il était naturel que le premier logiciel prenne le format majeur de colonne de sorte que si vous avez une matrice qui est un ensemble de vecteurs, le stockage de tout vecteur unique est contigu. Ainsi, j'imagine que la tradition vient de se perpétuer jusqu'à nos jours, et si vous voulez interagir avec le vieux Fortran, vous voulez utiliser la colonne majeure. Donc, à peu près toutes les algèbres linéaires numériques très efficaces se font en colonnes majeures.

La raison pour laquelle C est la ligne principale est quelque peu une conséquence de sa syntaxe de tableau; vous déclarez un tableau de 3 lignes par 2 colonnes comme double a[3][2], et les indices ultérieurs varient plus rapidement que les indices précédents, ce qui, pour les tableaux 2D, le rend majeur. Combinez cela avec l'ordre de lecture occidental naturel de gauche à droite, cela rend la ligne principale plus naturelle.

Victor Liu
la source
2
Je pense que ce sont de mauvais arguments. Le fait que le dernier indice de '' 'double a [3] [2]' '' varie le plus rapidement n'est pas une coïncidence - c'était une décision de conception concise de la même manière que c'était une décision de conception consciente à Fortran de faites-le dans l'autre sens lorsque vous avez un tableau '' 'real (3,2)' ''.
Wolfgang Bangerth
1
De plus, il n'est plus vrai que presque toutes les algèbres linéaires numériques très efficaces soient des colonnes majeures. Cela peut encore être vrai pour BLAS et LAPACK, mais ce n'est pas du tout vrai pour toutes les bibliothèques d'algèbre linéaire majeures qui sont apparues au cours des 15 dernières années: par exemple, PETSc et Trilinos utilisent tous les deux des formats de stockage matriciels clairsemés.
Wolfgang Bangerth
Je sais que la convention C était une décision consciente, probablement basée sur un ordre de lecture naturel. Je voulais dire qu'il n'a probablement pas été conçu avec l'algèbre linéaire numérique à l'esprit, ce qui en fait une coïncidence qu'il s'agit d'une ligne majeure. Deuxièmement, je n'avais pas l'intention d'argumenter pour des matrices clairsemées, seulement denses. Pour clairsemé, c'est un peu mélangé, avec des formats de lignes et de colonnes compressés.
Victor Liu
5
Pour ne pas trop expliquer le point, mais C était à l'origine un langage système, basé sur les langages précédents B et BCPL, fonctionnant sur des systèmes comme le PDP-11 qui n'avaient pas à l'origine de nombres à virgule flottante. Dire qu'ils l'ont conçu avec des chiffres à l'esprit est un peu exagéré.
Victor Liu
7
Été là, etc. La raison pour laquelle les matrices en C déplacent le dernier index le plus rapidement est parce que C n'a pas de matrices. Il a des vecteurs de vecteurs, qui peuvent être implémentés de manière transparente comme des blocs solides de mémoire, ou comme des tableaux de pointeurs vers des tableaux. Rendre l'ordre des index compatible avec Fortran n'était (je suppose) même pas sur le radar de Dennis Ritchie.
Mike Dunlavey
2

L'ordre des colonnes majeures semble être plus naturel. Par exemple, supposez que si vous souhaitez enregistrer un film dans un fichier image par image, vous utilisez l'ordre des colonnes, ce qui est très intuitif et personne ne l'enregistrera dans l'ordre des lignes principales.

Si vous êtes programmeur en C / C ++, vous devez utiliser des bibliothèques de niveau supérieur pour les matrices (Eigen, Armadillo, ...) avec un ordre de colonne majeur par défaut. Seul le maniaque utiliserait des pointeurs C bruts avec un ordre de rang majeur, bien que C / C ++ offre quelque chose qui rappelle l'indexation matricielle.

Pour plus de simplicité, tout ce qui a un ordre de rang majeur doit être considéré comme au moins étrange. Tranche par tranche est simplement un ordre naturel et cela signifie un ordre de colonne majeur (comme Fortran). Nos pères / mères avaient de très bonnes raisons pour lesquelles ils l'ont choisi.

Malheureusement, avant qu'il ne devienne clair, plusieurs bibliothèques intéressantes ont été créées dans l'ordre des lignes principales, probablement en raison du manque d'expérience.

Pour clarifier, rappelez-vous la définition de l'ordre des lignes principales où l'index droit varie plus rapidement en une seule étape dans la mémoire, par exemple A (x, y, z), il s'agit de l'index z, cela signifie que dans la mémoire, les pixels de différentes tranches sont adjacents, ce que nous ne veux pas. Pour le film A (x, y, t), le dernier index est le temps t. Il n'est pas difficile d'imaginer qu'il est tout simplement impossible d'enregistrer un film en mode ligne principale.

Paul
la source
2

m×n matrice est agencée de façon linéaire:

  • mje,jje×m+j si l'ordre de ligne principale est utilisé
  • mje,jj×n+je si l'ordre des colonnes est utilisé

Imaginez maintenant l'algorithme suivant:

for i from 1 to m
   for j from 1 to n
      do something with m(i,j)

je×m+j

Conclusions:

  1. oui, cela a une importance, mais le choix dépend de la façon dont les données sont accédées. Pour l'exemple précédent, si l'ordre des colonnes est utilisé, ce que vous pouvez faire est simplement de permuter les deux boucles.

  2. règle générale: l'index à variation rapide doit être mappé sur des emplacements successifs en mémoire.

  3. plus important encore, la mesure / l'analyse comparative de l'impact du choix est fondamentale, car elle dépend de nombreux paramètres (la taille des données, la taille du cache, la façon dont le langage utilisé mappe plusieurs indices à un index linéaire, la façon dont le fonctionnement système gère la mémoire virtuelle, la façon dont les boucles sont imbriquées dans la bibliothèque d'algèbre linéaire que vous utilisez ...)

BrunoLevy
la source