Disposition des lignes par rapport aux colonnes par colonnes

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.

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 du format principal de colonne

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 $AX=X\Lambda$$X$matrice 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.

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.

$m\times n$ matrice est agencée de façon linéaire:

• $m_{i,j}$$i \times m + j$ si l'ordre de ligne principale est utilisé
• $m_{i,j}$$j \times n + i$ 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)

$i \times 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 ...)