Layout de linha principal versus coluna principal de matrizes

Na programação de cálculos de matriz densa, existe alguma razão para escolher um layout de linha principal do layout acima da coluna?

Eu sei que, dependendo do layout da matriz escolhida, precisamos escrever o código apropriado para usar as memórias de cache efetivamente para fins de velocidade.

O layout principal da linha parece mais natural e mais simples (pelo menos para mim). Porém, grandes bibliotecas como o LAPACK, escritas em Fortran, usam o layout principal da coluna; portanto, deve haver algum motivo para ter feito essa escolha.

O layout principal da coluna é o esquema usado pelo Fortran e é por isso que é usado no LAPACK e em outras bibliotecas.

Em geral, é muito mais eficiente em termos de uso da largura de banda da memória e desempenho do cache acessar os elementos de uma matriz na ordem em que eles estão dispostos na memória. Dependendo de como suas matrizes são armazenadas, convém escolher algoritmos que tirem vantagem disso.

Armazenamento interno do formato principal da coluna

$AX=X\Lambda$$X$matriz contém todos os vetores próprios gravados em colunas. Você nunca vê isso escrito de outra maneira (embora eu ouça que o pessoal das estatísticas gosta de vetores de linha). Portanto, era natural que o software mais antigo assumisse o formato principal da coluna, de modo que, se você tiver uma matriz que é um conjunto de vetores, o armazenamento de qualquer vetor único é contíguo. Assim, imagino que a tradição tenha sido levada adiante até os dias atuais e, se você deseja interagir com o velho Fortran, deseja usar a coluna major. Portanto, praticamente toda álgebra linear numérica altamente eficiente é feita na coluna principal.

A razão de C ser a linha principal é uma conseqüência de sua sintaxe da matriz; você declara uma matriz de 3 linhas por 2 colunas como double a[3][2]e os índices posteriores variam mais rapidamente que os índices anteriores, o que para matrizes 2D torna a linha principal. Combine isso com a ordem de leitura ocidental natural da esquerda para a direita, fazendo com que as linhas principais pareçam mais naturais.

A ordem das colunas principais parece ser mais natural. Por exemplo, suponha que se você deseja salvar filme em arquivo imagem por imagem, você está usando a ordem das colunas, e isso é muito intuitivo e ninguém o salvaria na ordem das principais linhas.

Se você é programador em C / C ++, deve usar algumas bibliotecas de nível superior para matrizes (Eigen, Armadillo, ...) com a ordem principal da coluna padrão. Somente o maníaco usaria ponteiros C brutos com a ordem das linhas principais, embora o C / C ++ ofereça algo que lembre a indexação da matriz.

Por uma questão de simplicidade, tudo com ordem maior da linha deve ser considerado como formado pelo menos estranho. Fatia por fatia é simplesmente uma ordem natural e significa uma ordem principal da coluna (como Fortran). Nossos pais / mães tinham boas razões para escolherem.

Infelizmente, antes que se tornasse claro, várias bibliotecas interessantes foram criadas na ordem principal, provavelmente devido à falta de experiência.

Para esclarecer a definição da ordem da linha principal, onde o índice correto varia mais rapidamente em uma etapa da memória, por exemplo, A (x, y, z) é o índice z, significa que, na memória, pixels de diferentes fatias são adjacentes, o que não gostaríamos não quero. Para o filme A (x, y, t), o último índice é o tempo t. Não é difícil imaginar que é simplesmente impossível salvar um filme no modo principal.

$m\times n$

• $m_{i,j}$$i \times m + j$
• $m_{i,j}$$j \times n + i$

Agora imagine o seguinte algoritmo:

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

$i \times m + j$

Conclusões:

1. sim, isso tem uma importância, mas a escolha depende da maneira como os dados são acessados. Para o exemplo anterior, se a ordem das colunas for usada, o que você pode fazer é simplesmente trocar os dois loops.

2. regra prática: o índice de variação rápida deve ser mapeado para locais sucessivos na memória.

3. mais importante, medir / comparar o impacto da escolha é fundamental, pois depende de muitos parâmetros (o tamanho dos dados, o tamanho do cache, a maneira como a linguagem usada mapeia vários índices para um índice linear, a maneira como a operação sistema gerencia a memória virtual, a maneira como os loops são aninhados na biblioteca de álgebra linear que você usa ...)