Por que minha escala de multiplicação de vetores matriciais não é?

15

Desculpe pelo longo post, mas eu queria incluir tudo o que achava relevante desde o início.

O que eu quero

Estou implementando uma versão paralela dos métodos de subespaço de Krylov para matrizes densas. Principalmente GMRES, QMR e CG. Percebi (após a criação de perfil) que minha rotina DGEMV era patética. Então eu decidi me concentrar nisso, isolando-o. Eu tentei executá-lo em uma máquina de 12 núcleos, mas os resultados abaixo são para um laptop Intel i3 de 4 núcleos. Não há muita diferença na tendência.

Minha KMP_AFFINITY=VERBOSEsaída está disponível aqui .

Eu escrevi um pequeno código:

size_N = 15000
A = randomly_generated_dense_matrix(size_N,size_N); %Condition Number is not bad
b = randomly_generated_dense_vector(size_N);
for it=1:n_times %n_times I kept at 50 
 x = Matrix_Vector_Multi(A,b);
end

Eu acredito que isso simula o comportamento do CG por 50 iterações.

O que eu tentei:

Tradução

Originalmente, eu escrevi o código em Fortran. Traduzi para C, MATLAB e Python (Numpy). Escusado será dizer que MATLAB e Python foram horríveis. Surpreendentemente, C foi melhor que FORTRAN em um ou dois segundos para os valores acima. Consistentemente.

Criação de perfil

Eu criei um perfil do meu código para executar e ele foi executado por 46.075segundos. Foi quando MKL_DYNAMIC foi definido comoFALSE e todos os núcleos foram usados. Se eu usei o MKL_DYNAMIC como verdadeiro, apenas (aprox.) Metade do número de núcleos estava em uso em um determinado momento. Aqui estão alguns detalhes:

Address Line    Assembly                CPU Time

0x5cb51c        mulpd %xmm9, %xmm14     36.591s

O processo mais demorado parece ser:

Call Stack                          LAX16_N4_Loop_M16gas_1
CPU Time by Utilization             157.926s
CPU Time:Total by Utilization       94.1%
Overhead Time                       0us
Overhead Time:Total                 0.0%    
Module                              libmkl_mc3.so   

Aqui estão algumas fotos:insira a descrição da imagem aqui insira a descrição da imagem aqui

Conclusões:

Sou iniciante em criação de perfil, mas percebo que a velocidade ainda não é boa. O código seqüencial (1 núcleo) termina em 53 segundos. Isso é uma velocidade menor que 1.1!

Pergunta real: O que devo fazer para melhorar minha aceleração?

Coisas que acho que podem ajudar, mas não tenho certeza:

  • Implementação de Pthreads
  • Implementação MPI (ScaLapack)
  • Ajuste manual (não sei como. Por favor, recomende um recurso, se você sugerir isso)

Se alguém precisar de mais detalhes (principalmente em relação à memória), informe-me o que devo executar e como. Eu nunca tenho memória perfilada antes.

Inquérito
fonte

Respostas:

20

Sua matriz é do tamanho 15.000 x 15.000, então você tem 225M elementos na matriz. Isso representa aproximadamente 2 GB de memória. Isso é muito mais do que o tamanho do cache do seu processador, portanto, ele precisa ser carregado completamente da memória principal em todas as multiplicações de matrizes, gerando aproximadamente 100 GB de transferências de dados, além do que você precisa para os vetores de origem e destino.

A largura de banda máxima de memória do i3 é de aproximadamente 21 GB / s, com base nas especificações da Intel, mas se você procurar na web, verá que no máximo metade disso está realmente disponível na realidade. Assim, no mínimo, você esperaria que sua referência durasse 10 segundos e sua medição real de 45 segundos não está tão longe dessa marca.

Ao mesmo tempo, você também está multiplicando e adicionando 10 bilhões de pontos flutuantes. Considerando, digamos, 10 ciclos de relógio para a combinação e a taxa de clock de 3 GHz, você sairá em ~ 30 segundos. Obviamente, eles podem executar simultaneamente com cargas especulativas de memória se o cache for inteligente.

Em suma, eu diria que você não está muito longe da realidade. O que você esperaria?

Wolfgang Bangerth
fonte
Não existe uma maneira de obter pelo menos uma aceleração de 2 a 3?
Inquérito
@ Nanoxic - Você pode comparar o desempenho da memória em seu sistema usando uma ferramenta como a SiSoftware Sandra. A análise de Wolfgangs parece certa para mim, se o seu aplicativo estiver vinculado à largura de banda da memória, a paralelização ajudará pouco ou nada. Além disso, observe todas as opções de economia de energia que você possa ter, pois podem estar prejudicando o desempenho da memória. Além disso, considere substituir sua memória por uma memória de maior qualidade; uma latência CAS menor, por exemplo, pode fazer uma grande diferença no seu tempo de parede.
Mark Booth
4

Como você está multiplicando o vetor de matriz? Um loop duplo à mão? Ou liga para BLAS? Se você estiver usando MKL, eu recomendo fortemente o uso das rotinas BLAS da versão encadeada.

Por curiosidade, você também pode compilar sua própria versão ajustada do ATLAS e ver como isso ocorre no seu problema.

Atualizar

Após a discussão nos comentários abaixo, verifica-se que o seu Intel Core i3-330M possui apenas dois núcleos "reais". Os dois núcleos ausentes são emulados com hyperthreading . Como nos núcleos com hyperthread, o barramento de memória e as unidades de ponto flutuante são compartilhadas, você não obterá nenhuma aceleração se algum dos dois for um fator limitante. De fato, o uso de quatro núcleos provavelmente atrasará as coisas.

Que tipo de resultado você obtém "apenas" dois núcleos?

Pedro
fonte
Eu tentei ATLAs, GoTo e Netlib BLAS. Todos são mais fracos que o MKL em desempenho. Isso é esperado ou estou fazendo algo errado? Compilei o ATLAS como mencionado no manual. Além disso, colei meu código (exato) aqui . Está chamando o BLAS do MKL.
Inquérito 23/03
Ok, e para o dimensionamento, você tem certeza de que, no seu caso de linha de base, o código está sendo executado apenas em uma única CPU? Por exemplo, se você fizer o benchmark, o histograma de uso da CPU mostra apenas um núcleo?
Pedro
Sim. O histograma da CPU mostra 1 núcleo.
Inquérito 23/03
Só por curiosidade novamente, o que você ganha por dois ou três núcleos? Sua máquina possui quatro núcleos físicos ou apenas dois núcleos com hyperthreading ?
Pedro
Como faço para descobrir isso? Eu incluí meu KMP_AFFINITY no principal.
Inquérito
0

Tenho a impressão de que a ordem das linhas principais é ideal para esse problema em relação aos tempos de acesso à memória, uso de linhas de cache e falhas no TLB. Eu acho que sua versão do FORTRAN usou a ordenação principal da coluna, o que poderia explicar por que é consistentemente mais lenta que a versão C.

b

Você também pode testar a velocidade se apenas resumir todos os elementos da matriz em um único loop, em vez da multiplicação do vetor da matriz. (Você pode desenrolar o loop por um fator 4, porque a não associação de adição pode impedir que o compilador faça essa otimização para você.)

Thomas Klimpel
fonte