o uso da largura de banda de memória eficiente para streaming

Question

Eu tenho um aplicativo que flui com 250 MB de dados, aplicação de um simples e função limite rápido neural-net para os blocos de dados (que são apenas 2 palavras de 32 bits cada). Com base no resultado do cálculo (muito simples), o pedaço é imprevisível empurrado para um dos 64 compartimentos. Portanto, é um fluxo grande e 64 mais curto (comprimento variável) flui para fora.

Esta é repetido muitas vezes com diferentes funções de detecção.

A computação é a largura de banda de memória limitada. Eu posso dizer isso porque não há nenhuma mudança de velocidade mesmo se eu usar uma função discriminante que é muito mais computacionalmente intensivas.

O que é a melhor maneira de estruturar as gravações dos novos fluxos para otimizar minha banda de memória? Estou especialmente a pensar que o uso de cache compreensão e tamanho da linha de cache pode desempenhar um grande papel nisso. Imagine que o pior caso onde eu tenho meus 64 fluxos de saída e pela má sorte, muitos mapa para a mesma linha de cache. Então, quando eu escrever os próximos 64 bits de dados a um fluxo, a CPU tem que expulsar uma linha obsoleto cache para a memória principal, e carga na linha de cache adequado. Cada um desses usos 64 bytes de largura de banda ... por isso a minha largura de banda aplicação limitada podem ser desperdiçando 95% da largura de banda de memória (neste pior caso hipotético, embora).

É difícil até tentar medir o efeito, para desenvolver maneiras de contornar isso é ainda mais vaga. Ou estou mesmo perseguindo um gargalo fantasma que de alguma forma o hardware otimiza melhor do que eu?

Eu estou usando processadores x86 Núcleo II se isso faz alguma diferença.

Edit: Aqui está um código de exemplo. Flui através de uma matriz e cópias seus elementos de várias matrizes de saída escolhidas pseudo-aleatoriamente. Executando o mesmo programa com diferentes números de caixas de destino dá diferentes tempos de execução, embora a mesma quantidade de computação e memória leituras e gravações foram feitas:

2 saída de córregos: 13 segundos
8 de saída córregos: 13 segundos
32 saída de córregos: 19 segundos
128 saída córregos: 29 segundos
512 fluxos de saída: 47 segundos

A diferença entre a utilização de 512 versus 2 saída fluxos é 4X, (provavelmente ??) causada por cima da linha de cache despejo.

#include <stdio.h>
#include <stdlib.h>
#include <ctime>

int main()
{
  const int size=1<<19;
  int streambits=3;
  int streamcount=1UL<<streambits; // # of output bins
  int *instore=(int *)malloc(size*sizeof(int));
  int **outstore=(int **)malloc(streamcount*sizeof(int *));
  int **out=(int **)malloc(streamcount*sizeof(int));
  unsigned int seed=0;

  for (int j=0; j<size; j++) instore[j]=j;

  for (int i=0; i< streamcount; ++i) 
    outstore[i]=(int *)malloc(size*sizeof(int));

  int startTime=time(NULL);
  for (int k=0; k<10000; k++) {
    for (int i=0; i<streamcount; i++) out[i]=outstore[i];
    int *in=instore;

    for (int j=0; j<size/2; j++) {
      seed=seed*0x1234567+0x7162521;
      int bin=seed>>(32-streambits); // pseudorandom destination bin
      *(out[bin]++)=*(in++);
      *(out[bin]++)=*(in++);
    }

  }
  int endTime=time(NULL);
  printf("Eval time=%ld\n", endTime-startTime);
}

Answer 1

Como você está escrevendo para as bandejas de saída 64, você estará usando muitas posições de memória diferentes. Se as caixas são preenchidos essencialmente ao acaso, isso significa que às vezes você vai ter duas caixas que couls compartilhar a mesma linha de cache. Não é um grande problema; o cache Core 2 L1 é de 8 vias associativo. Isso significa que você teria um problema apenas com a linha de cache 9ª. Com apenas 65 referências de memória ao vivo a qualquer momento (1 leitura / 64 write), 8-way associativa é OK.

O cache L2 é, aparentemente, de 12 maneira associativa (não 3/6 MB total, o modo 12 é que o número de um estranho). Assim, mesmo se você teria colisões em L1, as chances são boas bastante você ainda não está batendo memória principal.

No entanto, se você não gosta disso, re-organizar as caixas na memória. Em vez de stroing cada bin sequencialmente, intercalam-los. Para bin 0, armazenar segmenta 0-15 em deslocamentos 0-63, mas armazenam pedaços 16-31 no deslocamento 8192-8255. Para bin 1, store segmenta 0-15 em deslocamentos 64-127, etcetera. Isso leva apenas alguns turnos bit e máscaras, mas o resultado é que um par de bandejas compartilharem 8 linhas de cache.

Outra forma possível para acelerar o seu código neste caso é SSE4, especialmente no modo x64. Você deseja obter 16 registros x 128 bits, e você pode otimizar a leitura (MOVNTDQA) para a poluição da cache limite. Eu não tenho certeza se isso vai ajudar muito com a velocidade de leitura, embora - eu esperaria o prefetcher Core2 para pegar isso. Leitura inteiros sequenciais é o tipo mais simples de acesso possível, qualquer prefetcher deve otimizar isso.

Answer 2

Você tem a opção de escrever seus fluxos de saída como um único fluxo com metadados em linha para identificar cada 'pedaço'? Se você estava a ler um 'pedaço', executar a sua função threshhold sobre ele, então em vez de escrevê-lo a um fluxo de saída especial que você só iria escrever que transmiti-lo pertencia a (1 byte), seguido pelos dados originais, você seriamente reduzir a sua surra.

Eu não sugeriria isso, exceto pelo fato de que você disse que você tem que processar esses dados muitas vezes. Em cada execução sucessiva, você ler o seu fluxo de entrada para obter o número bin (1 byte), em seguida, fazer o que você precisa fazer para que Bin nos próximos 8 bytes.

Quanto ao comportamento cacheing deste mecanismo, já que você só estão deslizando através de dois fluxos de dados e, em todos, mas o primeiro caso, escrever tantos dados quanto você está lendo, o hardware lhe dará toda a ajuda que possivelmente poderia esperar, tanto quanto pré-busca, otimização de linha de cache, etc.

Se você tivesse que acrescentar que byte extra cada vez que você processados ??os seus dados, o seu pior comportamento do cache caso é o caso médio. Se você pode pagar o hit de armazenamento, parece que uma vitória para mim.

Answer 3

Aqui estão algumas idéias se você realmente ficar desesperado ...

Você pode considerar hardware atualização. Para aplicações de streaming algo semelhante ao seu, eu descobri que eu tenho um grande aumento de velocidade, mudando para um processador i7. Além disso, os processadores AMD são supostamente melhor que o Core 2 para o trabalho de memória-bound (embora eu não tê-los usado recentemente eu).

Outra solução que você pode considerar está fazendo o processamento em uma placa de vídeo usando uma linguagem como CUDA. As placas gráficas são ajustados para ter largura de banda de memória muito alta e fazer rápido matemática de ponto flutuante. Espere gastar 5x a 20x o tempo de desenvolvimento de código CUDA em relação a uma implementação simples e direta não otimizado C.

Answer 4

Você pode querer explorar para mapear os arquivos na memória. Desta forma, o kernel pode cuidar do gerenciamento de memória para você. O kernel normalmente sabe melhor como lidar com caches de páginas. Isto é especialmente verdadeiro se suas necessidades de aplicação para rodar em mais de uma plataforma, como o gerenciamento de memória diferente alça Oses de maneiras diferentes.

Existem frameworks como ACE ( http: //www.cs.wustl. edu / ~ Schmidt / ACE.html ) ou aumento ( http://www.boost.org ) que permitem que você escrever código que faz o mapeamento de memória de uma forma independente de plataforma.

Answer 5

A verdadeira resposta para situações como esta é para o código-se várias abordagens e tempo eles. Que você têm, obviamente feito. Todas as pessoas como eu posso fazer é sugerir outras abordagens para tentar.

Por exemplo: mesmo na ausência de goleada cache (sua saída córregos mapeamento para as mesmas linhas de cache), se você estiver escrevendo ints tamanho, com size = 1 << 19 e sizeof (int) = 4, 32-bits - ou seja, se você está escrevendo 8MB de dados, na verdade você está lendo 8MB e depois escrevendo 8MB. Porque se os seus dados estão na memória comum WB (WriteBack) em um processador x86, de escrever para uma linha que você primeiro tem que ler a cópia antiga da linha -. Mesmo que você está indo jogar ler os dados afastado

Você pode eliminar essa desnecessária-RFO ler tráfego por (a) usando a memória WC (provavelmente uma dor de configurar) ou (b) usando lojas SSE de streaming, aka NT Lojas (Non-temporal). MOVNT * - MOVNTQ, MOVNTPS, etc. (. Há também um MOVNTDQA streaming de carga, embora mais doloroso para usar)

eu gosto bastante deste artigo eu só encontrei por googling http://blogs.fau.de/hager/2008/09/04/a-case-for-the-non-temporal-store/

Agora: MOVNT * aplicam-se a memória de WB mas o trabalho como a memória WC, usando um pequeno número de buffers de gravação cmbining. O número real varia consoante o modelo do processador: havia apenas 4 no primeiro chip Intel para tê-los, P6 (aka Pentium Pro). Ooof ... do Bulldozer 4K CMI (Write Combinando Cache), basicamente, fornece 64 combinando gravação buffers, por http://semiaccurate.com/forums/showthread.php?t=6145&page=40 , apesar de existirem apenas quatro buffers WC clássicos. Mas http: // www. intel.com/content/dam/doc/manual/64-ia-32-architectures-optimization-manual.pdf diz que alguns Processos tem 6 buffers WC, e alguns 8. Enfim ... há alguns , mas não muitos. Normalmente não 64.

Mas aqui é algo que você pode tentar: implementar a combinação de escrita si mesmo.

a) gravação para um único conjunto de 64 (#streams) buffers, cada um tamanho 64B (tamanho de linha de cache), - ou talvez 128 ou 256B. Deixe estas buffers estar na memória WB comum. Você pode acessá-los com lojas comuns, embora se você pode usar MOVNT *, ótimo.

Quando um desses buffers estiver cheio, copie-o como uma explosão para o local na memória onde o fluxo realmente é suposto ir. Usando MOVNT * streaming de lojas.

Isso vai acabar fazendo * N bytes armazenados para os tampões temporários, batendo a cache L1 * 64 * 64 bytes lidos para preencher os tampões temporários * N bytes lidos a partir dos tampões temporários, batendo a cache L1. * N bytes escritos através de streaming de lojas -., Basicamente, indo direto para a memória

ou seja N bytes de cache hit leia + N bytes de cache hit write + N bytes de cache falta

contra N bytes de cache falta leia + N bytes de cache de gravação de leitura.

A redução da N bytes de cache de falha de leitura pode moe do que compensar a sobrecarga extra.