Otimização Super C ++ da multiplicação de matrizes com Armadillo

9

Estou usando o Tatu para fazer multiplicações de matriz muito intensivas com comprimentos laterais , onde pode ser de até 20 ou mais. Estou usando o Armadillo com o OpenBLAS para multiplicação de matrizes, o que parece estar fazendo um trabalho muito bom em núcleos paralelos, exceto que tenho um problema com o formalismo da multiplicação no Armadillo para super otimização de desempenho. n2nn

Digamos que eu tenho um loop no seguinte formato:

arma::cx_mat stateMatrix, evolutionMatrix; //armadillo complex matrix type
for(double t = t0; t < t1; t += 1/sampleRate)
{
    ...
    stateMatrix = evolutionMatrix*stateMatrix;
    ...
}

No C ++ fundamental, acho que o problema aqui é que o C ++ alocará um novo objeto de cx_matpara armazenar evolutionMatrix*stateMatrixe, em seguida, copie o novo objeto para stateMatrixwith operator=(). Isso é muito, muito ineficiente. É sabido que retornar classes complexas de grandes tipos de dados é uma má ideia, certo?

A maneira como vejo isso indo de maneira mais eficiente é com uma função que faz a multiplicação na forma:

void multiply(const cx_mat& mat1, const cx_mat& mat2, cx_mat& output)
{
    ... //multiplication of mat1 and mat2 and then store it in output
}

Dessa forma, não é necessário copiar objetos enormes com valor de retorno, e a saída não precisa ser realocada a cada multiplicação.

A pergunta : como posso encontrar um compromisso, no qual eu possa usar o Armadillo para multiplicação com sua bela interface do BLAS, e fazer isso de forma eficiente sem precisar recriar objetos de matriz e copiá-los a cada operação?

Isso não é um problema de implementação no Tatu?

O físico quântico
fonte
4
"Super otimização" é realmente algo que você provavelmente não quis se referir. É uma forma muito antiga e avançada de especialização de código em tempo de compilação que ainda não pegou.
Andrew Wagner
1
A maioria das respostas (e a própria pergunta!) Parece não entender que a multiplicação da matriz não é algo que você faz no lugar.
@hurkyl, o que você quer dizer com "no lugar"?
The Quantum Physicist
Quando você calcula , modifica "no lugar" no sentido de deixar o conteúdo de onde eles estão na memória e faz todo o trabalho modificando essa memória. ou não é computado dessa maneira. Não existe um algoritmo razoável para multiplicação que deixa onde está na memória e grava a saída da multiplicação na mesma memória que está sendo calculada. A atualização deve ser feita fora do lugar - a memória temporária deve ser usada de alguma maneira. A A A = A B A = B A AA=A+BAAA=ABA=BAA
Observando o código fonte do Tatu, a expressão stateMatrix = evolutionMatrix*stateMatrixnão fará nenhuma cópia. Em vez disso, o Armadillo faz uma alteração elegante no ponteiro da memória. A nova memória para o resultado ainda será alocada (não há como contornar isso), mas, em vez de copiar, a stateMatrixmatriz simplesmente usará a nova memória e descartará a memória antiga.
Mtall

Respostas:

14

No C ++ fundamental, acho que o problema aqui é que o C ++ alocará um novo objeto de cx_mat para armazenar evolutionMatrix * stateMatrix e, em seguida, copie o novo objeto para stateMatrix com o operador = ().

Acho que você está certo ao criar temporários, o que é muito lento, mas acho que a razão pela qual está fazendo isso está errada.

O Tatu, como qualquer boa biblioteca de álgebra linear C ++, usa modelos de expressão para implementar a avaliação atrasada de expressões. Quando você anota um produto da matriz como A*B, nenhum temporário é criado. Em vez disso, o Armadillo cria um objeto temporário ( x) que mantém referências Ae B, posteriormente, dada uma expressão como C = x, calcula o produto da matriz armazenando o resultado diretamente C, sem criar nenhum temporários.

Ele também usa essa otimização para lidar com expressões como A*B*C*D, onde, dependendo do tamanho da matriz, certas ordens de multiplicação são mais eficientes que outras.

Isso não é um problema de implementação no Tatu?

Se o Armadillo não estiver executando essa otimização, isso seria um bug no Armadillo que deveria ser relatado aos desenvolvedores.

No entanto, no seu caso, há outro problema que é mais importante. Em uma expressão como A=B*Co armazenamento de Anão contém nenhum dado de entrada, se Anão houver alias Bou C. No seu caso, A = A*Bescrever qualquer coisa na matriz de saída também modificaria uma das matrizes de entrada.

Mesmo com a função sugerida

multiply(const cx_mat&, const cx_mat&, cx_mat&)

como exatamente essa função ajudaria na expressão multiply(A, B, A)? Para implementações mais comuns dessa função, isso levaria a um bug. Seria necessário usar algum armazenamento temporário por conta própria, para garantir que seus dados de entrada não estejam corrompidos. Sua sugestão é basicamente como o Armadillo já implementa a multiplicação de matrizes, mas acho que provavelmente tomamos o cuidado de evitar situações como a multiply(A, B, A)alocação temporária.

A explicação mais provável do motivo pelo qual o Armadillo não está fazendo essa otimização é que seria incorreto fazer isso.

Por fim, existe uma maneira muito mais simples de fazer o que você deseja, assim:

cx_mat *A, *Atemp, B;
for (;;) {
  *Atemp = (*A)*B;
  swap(A, Atemp);
}

Isso é idêntico ao

cx_mat A, B;
for (;;) {
  A = A*B;
}

mas aloca uma matriz temporária, em vez de uma matriz temporária por iteração.

Kirill
fonte
Essa "maneira muito mais simples de fazer isso" - além de parecer obscura (embora sim, trocar em vez de copiar é realmente um idioma C ++, felizmente pouco necessário desde o C ++ 11), e travar se você não o fizer new-inicializar Atemp- você não ganha nada: ainda envolve gerar uma nova matriz temporária (*A)*Be copiá-la *Atemp, a menos que o RVO a impeça.
usar o seguinte código
1
@leftaroundabout Não, se um temporário extra for criado no meu exemplo, isso é um bug do Tatu. Bibliotecas de álgebra linear que dependem de modelos de expressão explicitamente evitam criar temporários em resultados intermediários. O valor de não(*A)*B é uma matriz temporária, mas um objeto de expressão que controla a expressão e suas entradas. Tentei explicar por que essa otimização não é acionada no exemplo original e não tem nada a ver com o RVO (ou mover a semântica como em outra resposta). Eu pulei todo o código de inicialização, não é importante no exemplo, apenas mostrei os tipos.
30515 Kirill
Ok, eu entendo o que você está dizendo, mas isso ainda parece uma maneira muito tola e pouco confiável de fazer isso. Se os projetistas tivessem convivido com a opção de otimizar a multiplicação destrutiva dessa maneira, certamente a teriam implementado com um método dedicado, ou pelo menos forneceria um costume swappara que você não precise fazer esse tipo de malabarismo com ponteiros.
precisa saber é o seguinte
1
@leftaroundabout Além disso, o exemplo não troca matrizes, troca ponteiros para matrizes, para evitar qualquer cópia. Existem duas matrizes temporárias, e qual delas é considerada temporária alterna a cada iteração.
30915 Kirill
2
@leftaroundabout: Não há gerenciamento de memória acontecendo aqui com esse uso de ponteiros. É apenas um pequeno bloco de código onde você tem dois objetos e precisa acompanhar qual objeto está usando para qual finalidade.
8

O @BillGreene aponta para a "otimização do valor de retorno" como uma maneira de contornar o problema fundamental, mas isso na verdade ajuda apenas a metade dele. Suponha que você tenha um código deste formulário:

struct ExpensiveObject { ExpensiveObject(); ~ExpensiveObject(); };

ExpensiveObject operator+ (ExpensiveObject &obj1,
                           ExpensiveObject &obj2)
{
   ExpensiveObject tmp;
   ...compute tmp based on obj1 and obj2...
   return tmp;
}

void f() {
  ExpensiveObject o1, o2, o3;
  ...initialize o1, o2...;
  o3 = o1 + o2;
}

Um compilador ingênuo irá

  1. crie um slot para armazenar o resultado da operação mais (uma temporária),
  2. operador de chamada +,
  3. crie o objeto 'tmp' dentro do operador + (um segundo temporário),
  4. calcular tmp,
  5. copie tmp no slot de resultados,
  6. destrua o tmp,
  7. copie o objeto de resultado para o3
  8. destruir o objeto de resultado

A otimização do valor de retorno pode unificar apenas o objeto 'tmp' e o slot 'result', mas não remove a necessidade de uma cópia. Portanto, você ainda fica com a criação de um temporário, a operação de cópia e a destruição de um temporário.

A única maneira de contornar isso é o operador + não retorna um objeto, mas um objeto de alguma classe intermediária que, quando atribuído a um ExpensiveObject, realiza a operação de adição e cópia. Essa é a abordagem típica usada nas bibliotecas de modelos de expressão .

Wolfgang Bangerth
fonte
Obrigado por esta informação. Você poderia fornecer um exemplo que eu possa usar com o Tatu para evitar esse problema?
A Quantum Físico
E eu gostaria de perguntar: Este é um problema de implementação em Tatu, certo? Quero dizer, não é realmente tão inteligente fazer dessa maneira ... pelo menos eles precisam dar o resultado à opção de referência. Direita?
The Quantum Physicist
6
A parte chave desta resposta é o fim. O Tatu usa modelos de expressão para avaliar expressões preguiçosamente quando possível. Isso reduz o número de temporários criados. A principal coisa que o OP deve ter em mente é executar um criador de perfil para determinar onde estão ocorrendo lentidão e, em seguida, focar na otimização. Freqüentemente, teorias sobre códigos que "deveriam ser lentos" não se tornam verdadeiras.
Jason R
Não acredito que quaisquer temporários sejam criados para este exemplo quando compilados com um compilador C ++ moderno. Eu criei um exemplo simples que mostra isso e atualizei minha postagem. Não discordo do valor da técnica de modelo de expressão, em geral, mas é irrelevante para uma expressão simples de operador único como a mostrada acima.
Bill Greene
@ BillGreene: Crie uma classe com um construtor, construtor de cópias, operador de atribuição e destruidor e compile o exemplo. Você verá que um temporário é criado. Além disso: precisa ser criado porque o compilador não pode eliminá-lo sem mesclar o operador de cópia, o construtor e o destruidor. Isso simplesmente não é possível para operações não triviais, como alocação de memória.
Wolfgang Bangerth
5

Stackoverflow ( https://stackoverflow.com/ ) é provavelmente um fórum de discussão melhor para esta pergunta. No entanto, aqui está uma resposta curta.

Duvido que o compilador C ++ esteja gerando código para esta expressão como você descreveu acima. Todos os compiladores C ++ modernos implementam uma otimização chamada "otimização do valor de retorno" ( http://en.wikipedia.org/wiki/Return_value_optimization ). Com a otimização do valor de retorno, o resultado de evolutionMatrix*stateMatrixé armazenado diretamente stateMatrix; nenhuma cópia é feita.

Obviamente, há uma considerável confusão sobre esse tópico e esse é um dos motivos pelos quais sugeri que o Stackoverflow poderia ser um fórum melhor. Existem muitos "advogados de linguagem" em C ++ lá, enquanto a maioria de nós aqui prefere gastar nosso tempo no CSE. ;-)

Criei o seguinte exemplo simples com base no post do professor Bangerth:

#ifndef NDEBUG
#include <iostream>

using namespace std;
#endif

class ExpensiveObject  {
public:
  ExpensiveObject () {
#ifndef NDEBUG
    cout << "ExpensiveObject  constructor called." << endl;
#endif
    v = 0;
  }
  ExpensiveObject (int i) { 
#ifndef NDEBUG
    cout << "ExpensiveObject  constructor(int) called." << endl;
#endif
    v = i; 
  }
  ExpensiveObject (const ExpensiveObject  &a) {
    v = a.v;
#ifndef NDEBUG
    cout << "ExpensiveObject  copy constructor called." << endl;
#endif
  }
  ~ExpensiveObject() {
#ifndef NDEBUG
    cout << "ExpensiveObject  destructor called." << endl;
#endif
  }
  ExpensiveObject  operator=(const ExpensiveObject  &a) {
#ifndef NDEBUG
    cout << "ExpensiveObject  assignment operator called." << endl;
#endif
    if (this != &a) {
      return ExpensiveObject (a);
    }
  }
  void print() const {
#ifndef NDEBUG
    cout << "v=" << v << endl;
#endif
  }
  int getV() const {
    return v;
  }
private:
  int v;
};

ExpensiveObject  operator+(const ExpensiveObject  &a1, const ExpensiveObject  &a2) {
#ifndef NDEBUG
  cout << "ExpensiveObject  operator+ called." << endl;
#endif
  return ExpensiveObject (a1.getV() + a2.getV());
}

int main()
{
  ExpensiveObject  a(2), b(3);
  ExpensiveObject  c = a + b;
#ifndef NDEBUG
  c.print();
#endif
}

Parece mais complicado do que realmente é porque eu queria remover completamente todo o código da impressão ao compilar no modo otimizado. Quando executo a versão compilada com uma opção de depuração, obtenho a seguinte saída:

ExpensiveObject  constructor(int) called.
ExpensiveObject  constructor(int) called.
ExpensiveObject  operator+ called.
ExpensiveObject  constructor(int) called.
v=5
ExpensiveObject  destructor called.
ExpensiveObject  destructor called.
ExpensiveObject  destructor called.

A primeira coisa a notar é que nenhum temporário é construído - apenas a, bec. O construtor padrão e o operador de atribuição nunca são chamados porque não são necessários neste exemplo.

O professor Bangerth mencionou modelos de expressão. De fato, essa técnica de otimização é muito importante para obter um bom desempenho em uma biblioteca de classes matriciais. Mas é importante apenas quando as expressões de objeto são mais complicadas do que simplesmente a + b. Se, por exemplo, meu teste fosse:

  ExpensiveObject  a(2), b(3), c(9);
  ExpensiveObject  d = a + b + c;

Eu obteria a seguinte saída:

ExpensiveObject  constructor(int) called.
 ExpensiveObject  constructor(int) called.
 ExpensiveObject  constructor(int) called.
 ExpensiveObject  operator+ called.
 ExpensiveObject  constructor(int) called.
 ExpensiveObject  operator+ called.
 ExpensiveObject  constructor(int) called.
 ExpensiveObject  destructor called.
 v=14
 ExpensiveObject  destructor called.
 ExpensiveObject  destructor called.
 ExpensiveObject  destructor called.
 ExpensiveObject  destructor called.

Este caso mostra a construção indesejável de um temporário (5 chamadas para o construtor e duas chamadas do operador +). O uso adequado de modelos de expressão (um tópico muito além do escopo deste fórum) impediria isso temporariamente. (Para os altamente motivados, uma discussão particularmente legível dos modelos de expressão pode ser encontrada no capítulo 18 de http://www.amazon.com/C-Templates-The-Complete-Guide/dp/0201734842 ).

Finalmente, a verdadeira "prova" do que o compilador está realmente fazendo vem do exame do código de montagem gerado pelo compilador. Para o primeiro exemplo, quando compilado no modo otimizado, esse código é surpreendentemente simples. Todas as chamadas de funções foram otimizadas e o código de montagem carrega essencialmente 2 em um registro, 3 em um segundo e as adiciona.

Bill Greene
fonte
Na verdade, eu estava hesitando em colocá-lo aqui ou no stackoverflow ... Eu tenho certeza que se eu o tivesse colocado no stackoverflow, alguém teria comentado que eu deveria colocá-lo aqui :-). De qualquer forma; a otimização do valor de retorno é uma boa notícia e eu não sabia disso antes (+1). Obrigado por isso. Infelizmente, não sei nada no código de montagem, portanto não é uma verificação que posso fazer.
A Quantum Físico
1
Se não me engano, mesmo considerando a otimização do valor de retorno, o compilador trabalha com três matrizes na memória, não duas. "Multiplique A e B e coloque o resultado em C" é uma função diferente de "multiplique A e B e substitua B pelo resultado".
Federico Poloni
Ponto interessante. Eu estava focando o desejo do pôster de ter uma implementação de multiplicação de matrizes tão eficiente quanto a função multiply (), mas com a boa sobrecarga do operador de multiplicação. Existe uma maneira de implementar uma matriz geral multiplicada sem três matrizes? O RVO, é claro, elimina a necessidade de ter uma cópia da matriz de saída.
Bill Greene
A referência da @ BillGreene à otimização do valor de retorno evita apenas a necessidade de um segundo temporário, mas ainda é necessário. Vou comentar sobre isso em outra resposta.
precisa saber é o seguinte
1
@ BillGreene: Seu exemplo é muito simples. A otimização de algumas tarefas, a criação de temporários etc. é possível porque não há efeitos colaterais que o compilador tenha que acomodar. Em essência, você está apenas trabalhando em um único escalar. Tente um exemplo em que, em vez de um único escalar, a classe exija alocação e exclusão de memória. Neste caso, você tem que chamar malloce freee o compilador não pode otimizar afastado pares deles sem tropeçar até monitores de memória etc.
Wolfgang Bangerth
5

O(n2.8)O(n2)n

Ou seja, a menos que você incorra em uma constante enorme na cópia - o que na verdade não é tão exagerado, porque a versão com cópia é muito mais cara em outro aspecto: ela precisa de muito mais memória. Portanto, se você precisar trocar de e para o disco rígido, a cópia poderá se tornar um gargalo. No entanto, mesmo se você não copiar nada, um algoritmo fortemente paralelizado poderá fazer algumas cópias por conta própria. Realmente, a única maneira de garantir que não seja usada muita memória em cada etapa é dividir a multiplicação em colunas destateMatrix , para que apenas pequenas multiplicações sejam feitas por vez. Por exemplo, você pode definir

class HChunkMatrix // optimised for destructive left-multiplication updates
{
  std::vector<arma::cx_mat> colChunks; // e.g. for an m×n matrix,
                                      //  use √n chunks, each an m×√n matrix
 public:
  ...

  HChunkMatrix& operator *= (const arma::cx_mat& lhMult) {
    for (&colChunk: colChunks) {
      colChunk = lhMult * colChunk;
    }
    return *this;
  }
}

Você também deve considerar se precisa evoluir isso stateMatrixcomo um em primeiro lugar. Se você basicamente quer apenas uma evolução no tempo independente dos nkets de estado, pode evoluí-los um por um, o que é muito menos dispendioso em termos de memória. Em particular, se evolutionMatrixfor escasso , você definitivamente deve conferir! Pois isso é basicamente apenas um hamiltoniano, não é? Os hamiltonianos são frequentemente esparsos ou aproximadamente esparsos.


O(n2.38)

leftaroundabout
fonte
1
Esta é a melhor resposta; os outros perdem o ponto importante de que a multiplicação da matriz não é realmente o tipo de coisa que você faz no local.
5

O C ++ moderno tem uma solução para o problema usando "mover construtores" e "referências de valor".

Um "mover construtor" é um construtor para uma classe, por exemplo, uma classe matricial, que pega outra instância da mesma classe e move os dados da outra instância para a nova instância, deixando a instância original vazia. Normalmente, um objeto de matriz terá dois números para o tamanho e um ponteiro para os dados. Onde um construtor normal duplicaria os dados, um construtor de movimentação copiará apenas os dois números e o ponteiro, portanto isso é muito rápido.

Uma "referência de valor", escrita por exemplo como "matriz &&" em vez da "matriz &" usual é usada para variáveis ​​temporárias. Você declararia uma multiplicação de matriz como retornando uma matriz &&. Ao fazer isso, o compilador garantirá que um construtor de movimentação muito barato seja usado para obter o resultado da função que o chama. Portanto, uma expressão como resultado = (a + b) * (c + d) onde a, b, c, d são enormes objetos matriciais, ocorrerá sem nenhuma cópia.

Ao pesquisar no Google "referências de rvalue e mover construtores", você encontrará exemplos e tutoriais.

gnasher729
fonte
0

vMMMMMMMMMMv

Então, novamente, entendo que o OpenBLAS tem uma coleção maior de otimizações específicas da arquitetura, portanto o Eigen pode ou não ser uma vitória para você. Infelizmente, não existe uma biblioteca de álgebra linear tão impressionante que você nem precise considerar os outros ao lutar pelos "últimos 10%" do desempenho. Os invólucros não são uma solução 100%; a maioria (todos?) deles não pode tirar proveito da capacidade da eigen de mesclar cálculos dessa maneira.

Andrew Wagner
fonte
note, existem ~ bibliotecas específicas de aplicativos que fazem coisas mais sofisticadas; Acho API da Apple é para composição de imagem fazem coisas semelhantes ao que eigen faz, além de mapear a computação na GPU ... E imagino bibliotecas fluxo de áudio fazer otimizações semelhantes ...
Andrew Wagner