el uso de ancho de banda para la transmisión eficiente de la memoria

Question

Tengo una aplicación que fluye a través de 250 MB de datos, la aplicación de una función de umbral red neuronal sencilla y rápida de los fragmentos de datos (que son sólo 2 palabras de 32 bits cada uno). Basándose en el resultado de los ordenador (muy simple), el trozo se empuja de manera impredecible en uno de los 64 bins. Así que es una gran corriente de 64 y más corto (longitud variable) fluye hacia fuera.

Esto se repite muchas veces con diferentes funciones de detección.

El cálculo es el ancho de banda de memoria limitada. Puedo decir esto porque no hay cambio de velocidad, incluso si uso una función discriminante que es mucho más computacionalmente intensivas.

¿Qué es la mejor manera de estructurar las escrituras de los nuevos flujos para optimizar mi ancho de banda de memoria? Estoy pensando especialmente en la comprensión de que el uso de caché y el tamaño de línea de caché puede jugar un papel importante en esto. Imaginar el peor de los casos donde tengo mis 64 flujos de salida y por la mala suerte, muchos mapa a la misma línea de caché. A continuación, cuando escribo los próximos 64 bits de datos a una corriente, la CPU tiene que eliminar una línea de caché rancio a la memoria principal, y la carga en la línea de caché adecuado. Cada uno de los que utiliza 64 bytes de ancho de banda ... así que mi aplicación limitada de ancho de banda se puede perder el 95% del ancho de banda de memoria (en este hipotético peor de los casos, sin embargo).

Es difícil incluso tratar de medir el efecto, por lo que el diseño de formas a su alrededor es aún más vaga. O estoy incluso persiguiendo a un cuello de botella de fantasmas que de alguna manera el hardware optimiza mejor que yo?

Estoy usando Core II procesadores x86, si hay alguna diferencia.

Edit: Aquí hay un código de ejemplo. Se filtra a través de una matriz y copias sus elementos para varios arrays de salida recogió pseudo-aleatoria. Al ejecutar el mismo programa con diferente número de bandejas de destino da diferentes tiempos de ejecución, a pesar de que la misma cantidad de cálculo y la memoria lee y se realizaron escribe:

2 flujos de salida: 13 segs
8 flujos de salida: 13 segs
32 flujos de salida: 19 segs
128 flujos de salida: 29 segundos
512 flujos de salida: 47 segundos

La diferencia entre el uso de 512 frente a 2 flujos de salida es 4X, (probablemente ??) causada por sobrecarga de línea de caché de desalojo.

#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

Mientras se escribe a las bandejas de salida 64, que va a utilizar muchas localizaciones de memoria diferentes. Si los contenedores se llenan esencialmente al azar, esto significa que hay veces que tiene dos compartimientos que couls comparten la misma línea de caché. No es un gran problema; el Core 2 caché L1 es de 8 vías asociativo. Eso significa que obtendría un problema sólo con la novena línea de caché. Con sólo 65 referencias de memoria en vivo en cualquier momento (1 Lectura / escritura 64), de 8 vías asociativo está bien.

La caché L2 es aparentemente 12-manera asociativa (3 / 6MB total de, por lo que 12 no es un número que raro). Así que incluso si usted tendría colisiones en L1, lo más probable es bastante bueno todavía no está golpeando la memoria principal.

Sin embargo, si no te gusta esto, re-organizar los contenedores en la memoria. En lugar de stroing cada bin secuencialmente, ellos intercalar. Por bin 0, almacenar trozos de 0-15 a 0-63 compensaciones, sino trozos de tiendas 16-31 en el offset 8.192 a 8.255. Para la bandeja 1, trozos de tiendas 0-15 en compensaciones 64-127, etcétera. Esto toma sólo unos desplazamientos de bit y máscaras, pero el resultado es que un par de bandejas comparten 8 líneas de caché.

Otra posible manera de acelerar su código en este caso es SSE4, especialmente en el modo de 64 bits. Te obtener 16 registros x 128 bits, y se puede optimizar la lectura (MOVNTDQA) para limitar la contaminación caché. No estoy seguro de si eso va a ayudar mucho con la velocidad de lectura, sin embargo - yo esperaría que la captura previa Core2 para coger esto. La lectura de números enteros consecutivos es el tipo más simple de acceso posible, cualquier prefetcher debe optimizar esa.

Answer 2

¿Tiene la opción de escribir sus flujos de salida como un único flujo en línea con los metadatos para identificar a cada 'trozo'? Si se va a leer un 'trozo' ejecutar su función de umbral en él, entonces en vez de escribirlo a un flujo de salida particular que le acaba de escribir que fluyen perteneció a (1 byte), seguido de los datos originales, que había en serio reducir su goleada.

No sugeriría esto, excepto por el hecho de que usted ha dicho que usted tiene que procesar estos datos muchas veces. En cada ejecución sucesiva, se lee el flujo de entrada para obtener el número de la bandeja (1 byte) y luego hacer lo que tiene que hacer para que bin en los siguientes 8 bytes.

En cuanto al comportamiento Cacheing de este mecanismo, ya que sólo se está deslizando a través de dos flujos de datos y, en todo menos en el primer caso, escribir todos los datos que usted está leyendo, el hardware le dará toda la ayuda que posiblemente podría esperar en cuanto a la obtención previa, optimización línea de caché, etc.

Si tuviera que añadir que byte adicional cada vez que procesa los datos, su peor comportamiento caché caso es un caso medio. Si usted puede permitirse el golpe de almacenamiento, parece como una victoria para mí.

Answer 3

Aquí están algunas ideas si realmente desesperáis ...

Es posible considerar la actualización de hardware. Para aplicaciones de transmisión en cierto modo similares a la suya, he encontrado que tengo una gran mejora en la velocidad al cambiar a un procesador i7. Además, los procesadores AMD son supuestamente mejor que la base 2 para trabajos relacionados con la memoria (aunque no los he usado recientemente a mí mismo).

Otra solución podría considerar que está haciendo el procesamiento de una tarjeta gráfica utilizando un lenguaje como CUDA. Las tarjetas gráficas están en sintonía con un ancho de banda de memoria muy alta y rápida de hacer cálculos de coma flotante. Prepárese para pasar de 5x a 20x el tiempo de desarrollo de código CUDA con relación a una aplicación recta de avance no optimizado C.

Answer 4

Es posible que desee explorar a asignar los archivos en la memoria. De esta forma el núcleo puede hacerse cargo de la gestión de memoria para usted. El kernel por lo general sabe bien cómo manejar las memorias caché de páginas. Esto es especialmente cierto si su aplicación necesita para funcionar en más de una plataforma, como los sistemas operativos diferentes manejan la gestión de memoria de diferentes maneras.

Hay marcos como ACE ( http: //www.cs.wustl. edu / ~ schmidt / ACE.html ) o Boost ( http://www.boost.org ) que le permiten escribir código que hace la asignación de memoria de una manera independiente de la plataforma.

Answer 5

La verdadera respuesta para situaciones como ésta es codificar hasta varios enfoques y tiempo de ellos. Que obviamente ha hecho. Todas gente como yo pueden hacer es sugerir otros enfoques para probar.

Por ejemplo: incluso en ausencia de la cache (flujos de salida de su asignación a las mismas líneas de caché), si está escribiendo enteros de tamaño, con un tamaño = 1 << 19 y sizeof (int) = 4, 32-bits - es decir, si está escribiendo 8 MB de datos, en realidad se está leyendo 8 MB y luego escribir 8 MB. Porque si los datos están en WB memoria ordinaria (WriteBack) en un procesador x86, escribir en una línea primero hay que leer la vieja copia de la línea -. A pesar de que se va a lanzar a los datos leídos de distancia

Puede eliminar este innecesario-ORP leer el tráfico por (a) el uso de la memoria WC (probablemente un dolor de configurar) o (b) el uso de tiendas de transmisión de la ESS, también conocido como NT (no temporales) almacenes. MOVNT * - (. También hay un MOVNTDQA streaming de carga, aunque más doloroso para su uso) MOVNTQ, MOVNTPS, etc.

Me gusta mucho este trabajo que acabo de encontrar buscando en Google http://blogs.fau.de/hager/2008/09/04/a-case-for-the-non-temporal-store/

Ahora: MOVNT * aplicable a la memoria BM, pero funciona como la memoria WC, utilizando un pequeño número de buffers cmbining escritura. El número real varía según el modelo de procesador: sólo 4 estaban en el primer chip Intel tenerlos, P6 (también conocido como Pentium Pro). Uf ... de la niveladora 4K CMI (combinación de escritura de caché) básicamente proporciona la combinación de escritura 64 tampones, por http://semiaccurate.com/forums/showthread.php?t=6145&page=40 , aunque sólo hay 4 amortiguadores WC clásicos. Pero http: // www. intel.com/content/dam/doc/manual/64-ia-32-architectures-optimization-manual.pdf dice que algunos processos tienen 6 tampones WC, y algunos 8. en fin ... hay unos pocos , pero no muchos. Por lo general, no 64.

Pero aquí es algo que usted podría intentar: poner en práctica la combinación de escritura usted mismo.

a) escribir en un único conjunto de 64 (#streams) tampones, cada uno de tamaño 64B (tamaño de línea de caché), - o tal vez 128 o 256B. Deja que estos tampones estar en la memoria BM ordinaria. Puede acceder a ellos con tiendas ordinarias, aunque si se puede usar MOVNT *, muy bien.

Cuando uno de estos tampones se llena, copiarlo como un estallido al lugar de la memoria donde la corriente se supone realmente que ir. El uso de tiendas de streaming MOVNT *.

Esto va a terminar haciendo * N bytes almacenados en las memorias intermedias temporales, golpeando la caché L1 * 64 * 64 bytes leídos para llenar los buffers temporales * N bytes leídos desde los buffers temporales, golpeando la caché L1. * n bytes escritos a través de las tiendas de streaming -. básicamente ir directamente a la memoria

es decir N Bytes acierto de caché leer + n bytes de aciertos de caché de escritura + N bytes de error de caché

frente al N Bytes error de caché leer + N bytes leídos caché de escritura.

La reducción de los n bytes de lectura error de caché puede moe que compensa con creces la sobrecarga adicional.