¿Cómo se escribe el código que mejor utiliza el caché de la CPU para mejorar el rendimiento?

159

Esto puede sonar como una pregunta subjetiva, pero lo que estoy buscando son instancias específicas, que podría haber encontrado relacionadas con esto.

  1. ¿Cómo hacer que el código sea efectivo en caché / compatible con caché (más aciertos de caché, la menor cantidad de errores de caché posible)? Desde ambas perspectivas, el caché de datos y el caché del programa (caché de instrucciones), es decir, qué cosas en el código de uno, relacionadas con las estructuras de datos y las construcciones de código, deben cuidarse para que el caché sea efectivo.

  2. ¿Hay alguna estructura de datos en particular que uno deba usar / evitar, o hay una forma particular de acceder a los miembros de esa estructura, etc.? Para que el caché de código sea efectivo.

  3. ¿Hay alguna construcción de programa (if, for, switch, break, goto, ...), code-flow (for inside an if, if inside a for, etc ...) uno debería seguir / evitar en este asunto?

Tengo muchas ganas de escuchar experiencias individuales relacionadas con la creación de código eficiente de caché en general. Puede ser cualquier lenguaje de programación (C, C ++, Assembly, ...), cualquier objetivo de hardware (ARM, Intel, PowerPC, ...), cualquier sistema operativo (Windows, Linux, S ymbian, ...), etc. .

La variedad ayudará a comprenderlo mejor.

Goldenmean
fuente
1
Como introducción, esta charla ofrece una buena visión general youtu.be/BP6NxVxDQIs
schoetbi
La URL acortada anterior ya no parece funcionar, esta es la URL completa de la charla: youtube.com/watch?v=BP6NxVxDQIs
Abhinav Upadhyay

Respuestas:

119

El caché está allí para reducir la cantidad de veces que la CPU se detendrá esperando que se cumpla una solicitud de memoria (evitando la latencia de la memoria ) y, como segundo efecto, posiblemente para reducir la cantidad total de datos que deben transferirse (preservar ancho de banda de memoria ).

Las técnicas para evitar el sufrimiento de la latencia de recuperación de la memoria suelen ser lo primero que se debe tener en cuenta, y a veces son de gran ayuda. El ancho de banda de memoria limitado también es un factor limitante, particularmente para aplicaciones multinúcleo y multiproceso donde muchos hilos quieren usar el bus de memoria. Un conjunto diferente de técnicas ayuda a abordar este último problema.

Mejorar la localidad espacial significa que se asegura de que cada línea de caché se use por completo una vez que se ha asignado a un caché. Cuando hemos examinado varios puntos de referencia estándar, hemos visto que una fracción sorprendente de ellos no puede usar el 100% de las líneas de caché recuperadas antes de que las líneas de caché sean expulsadas.

Mejorar la utilización de la línea de caché ayuda en tres aspectos:

  • Tiende a encajar datos más útiles en la memoria caché, esencialmente aumentando el tamaño efectivo de la memoria caché.
  • Tiende a ajustar datos más útiles en la misma línea de caché, lo que aumenta la probabilidad de que los datos solicitados se puedan encontrar en el caché.
  • Reduce los requisitos de ancho de banda de memoria, ya que habrá menos recuperaciones.

Las técnicas comunes son:

  • Usa tipos de datos más pequeños
  • Organice sus datos para evitar agujeros de alineación (ordenar los miembros de su estructura disminuyendo el tamaño es unidireccional)
  • Tenga cuidado con el asignador de memoria dinámica estándar, que puede introducir agujeros y difundir sus datos en la memoria a medida que se calienta.
  • Asegúrese de que todos los datos adyacentes se usen realmente en los hot loops. De lo contrario, considere dividir las estructuras de datos en componentes calientes y fríos, para que los bucles activos utilicen datos activos.
  • evite algoritmos y estructuras de datos que exhiban patrones de acceso irregulares, y favorezca las estructuras de datos lineales.

También debemos tener en cuenta que hay otras formas de ocultar la latencia de la memoria que el uso de cachés.

CPU modernas: a menudo tienen uno o más captadores de hardware . Se entrenan en los errores en un caché e intentan detectar regularidades. Por ejemplo, después de algunas fallas en las líneas de caché posteriores, hw prefetcher comenzará a buscar líneas de caché en el caché, anticipándose a las necesidades de la aplicación. Si tiene un patrón de acceso regular, el prefetcher de hardware generalmente está haciendo un muy buen trabajo. Y si su programa no muestra patrones de acceso regulares, puede mejorar las cosas agregando instrucciones de captación previa usted mismo.

Las instrucciones de reagrupamiento de tal manera que las que siempre faltan en la memoria caché se producen una cerca de la otra, la CPU a veces puede superponer estas recuperaciones para que la aplicación solo sufra un impacto de latencia ( paralelismo de nivel de memoria ).

Para reducir la presión general del bus de memoria, debe comenzar a abordar lo que se denomina localidad temporal . Esto significa que debe reutilizar los datos mientras aún no se hayan desalojado del caché.

La fusión de bucles que tocan los mismos datos ( fusión de bucles ) y el empleo de técnicas de reescritura conocidas como mosaico o bloqueo, se esfuerzan por evitar esas extracciones de memoria adicionales.

Si bien existen algunas reglas generales para este ejercicio de reescritura, generalmente debe considerar cuidadosamente las dependencias de datos transportados en bucle, para asegurarse de no afectar la semántica del programa.

Estas cosas son lo que realmente vale la pena en el mundo multinúcleo, donde normalmente no verá muchas mejoras de rendimiento después de agregar el segundo hilo.

Mats N
fuente
55
Cuando hemos examinado varios puntos de referencia estándar, hemos visto que una fracción sorprendente de ellos no puede usar el 100% de las líneas de caché recuperadas antes de que las líneas de caché sean expulsadas. ¿Puedo preguntar qué tipo de herramientas de creación de perfiles le brindan este tipo de información y cómo?
Dragon Energy
"Organice sus datos para evitar agujeros de alineación (ordenar los miembros de su estructura disminuyendo el tamaño es unidireccional)": ¿por qué el compilador no optimiza esto por sí mismo? ¿Por qué el compilador no siempre puede "ordenar los miembros disminuyendo el tamaño"? ¿Cuál es la ventaja de mantener a los miembros sin clasificar?
javapowered
No sé los orígenes, pero por un lado, el orden de los miembros es crucial en, digamos, la comunicación de red, donde es posible que desee enviar estructuras enteras byte a byte a través de la web.
Kobrar el
1
@javapowered El compilador puede hacer eso dependiendo del idioma, aunque no estoy seguro de si alguno de ellos lo hace. La razón por la que no puede hacerlo en C es que es perfectamente válido dirigirse a los miembros por dirección base + desplazamiento en lugar de por nombre, lo que significa que reordenar a los miembros interrumpiría completamente el programa.
Dan Bechard
56

No puedo creer que no haya más respuestas a esto. De todos modos, un ejemplo clásico es iterar una matriz multidimensional "al revés":

pseudocode
for (i = 0 to size)
  for (j = 0 to size)
    do something with ary[j][i]

La razón de que esto sea ineficiente en la memoria caché es porque las CPU modernas cargarán la línea de memoria caché con direcciones de memoria "cercanas" desde la memoria principal cuando acceda a una sola dirección de memoria. Estamos iterando a través de las filas "j" (externas) en la matriz en el bucle interno, por lo que para cada viaje a través del bucle interno, la línea de caché hará que se vacíe y cargue con una línea de direcciones cercanas a la [ j] [i] entrada. Si esto se cambia al equivalente:

for (i = 0 to size)
  for (j = 0 to size)
    do something with ary[i][j]

Correrá mucho más rápido.

1800 INFORMACIÓN
fuente
9
En la universidad teníamos una tarea de multiplicación de matrices. Resultó que era más rápido tomar primero una transposición de la matriz de "columnas" y multiplicar filas por filas en lugar de filas por columnas por esa razón precisa.
ykaganovich 01 de
11
en realidad, la mayoría de los compiladores modernos pueden resolver esto por sí mismos (con las optimizaciones activadas)
Ricardo Nolde
1
@ykaganovich Ese es también el ejemplo en el artículo de Ulrich Dreppers: lwn.net/Articles/255364
Simon Stender Boisen
No estoy seguro de que esto sea siempre correcto: si toda la matriz cabe dentro del caché L1 (¡a menudo 32k!), Ambas órdenes tendrán el mismo número de aciertos y errores de caché. Quizás la precarga de memoria podría tener algún impacto, supongo. Feliz de ser corregido, por supuesto.
Matt Parkins, el
¿Quién elegirá la primera versión de este código si el orden no importa?
silver_rocket
45

Las reglas básicas son en realidad bastante simples. Donde se pone difícil es en cómo se aplican a su código.

El caché funciona en dos principios: localidad temporal y localidad espacial. La primera es la idea de que si recientemente utilizó una determinada porción de datos, probablemente la necesitará nuevamente pronto. Esto último significa que si recientemente usó los datos en la dirección X, probablemente pronto necesitará la dirección X + 1.

El caché intenta acomodar esto recordando los fragmentos de datos utilizados más recientemente. Funciona con líneas de caché, generalmente de un tamaño de 128 bytes, por lo que incluso si solo necesita un solo byte, toda la línea de caché que lo contiene se extrae en la caché. Entonces, si necesita el siguiente byte después, ya estará en el caché.

Y esto significa que siempre querrá que su propio código explote estas dos formas de localidad tanto como sea posible. No saltes sobre la memoria. Haga todo el trabajo que pueda en un área pequeña, y luego pase a la siguiente, y haga todo el trabajo que pueda.

Un ejemplo simple es el recorrido de la matriz 2D que mostró la respuesta de 1800. Si lo atraviesa una fila a la vez, está leyendo la memoria secuencialmente. Si lo hace en forma de columna, leerá una entrada, luego saltará a una ubicación completamente diferente (el comienzo de la siguiente fila), leerá una entrada y saltará nuevamente. Y cuando finalmente regrese a la primera fila, ya no estará en el caché.

Lo mismo se aplica al código. Los saltos o ramas significan un uso de caché menos eficiente (porque no estás leyendo las instrucciones secuencialmente, sino saltando a una dirección diferente). Por supuesto, las sentencias if pequeñas probablemente no cambiarán nada (solo omite unos pocos bytes, por lo que aún terminará dentro de la región en caché), pero las llamadas a funciones generalmente implican que está saltando a una completamente diferente dirección que no se puede almacenar en caché. A menos que se haya llamado recientemente.

Sin embargo, el uso de la caché de instrucciones suele ser mucho menos problemático. De lo que generalmente debe preocuparse es del caché de datos.

En una estructura o clase, todos los miembros se presentan de forma contigua, lo cual es bueno. En una matriz, todas las entradas también se presentan de forma contigua. En las listas vinculadas, cada nodo se asigna a una ubicación completamente diferente, lo cual es malo. Los punteros en general tienden a apuntar a direcciones no relacionadas, lo que probablemente resultará en una pérdida de caché si la desreferencia.

Y si desea explotar múltiples núcleos, puede ser realmente interesante, ya que, por lo general, solo una CPU puede tener una dirección determinada en su caché L1 a la vez. Entonces, si ambos núcleos acceden constantemente a la misma dirección, se producirán errores constantes en la memoria caché, ya que están peleando por la dirección.

jalf
fuente
44
+1, buenos y prácticos consejos. Una adición: la localidad del tiempo y la localidad del espacio combinadas sugieren que, por ejemplo, para operaciones matriciales, podría ser aconsejable dividirlas en matrices más pequeñas que encajen completamente en una línea de caché, o cuyas filas / columnas encajen en líneas de caché. Recuerdo haberlo hecho para visualizar multidim. datos. Proporcionó una patada seria en los pantalones. Es bueno recordar que el caché contiene más de una 'línea';)
AndreasT
1
Usted dice que solo 1 CPU puede tener una dirección determinada en la caché L1 a la vez; supongo que se refiere a líneas de caché en lugar de a una dirección. También he oído hablar de problemas de uso compartido falso cuando al menos una de las CPU está haciendo escrituras, pero no si ambas solo están haciendo lecturas. Entonces, ¿por 'acceso' se refiere realmente a las escrituras?
Joseph Garvin el
2
@JosephGarvin: sí, quise decir escribe. Tiene razón, varios núcleos pueden tener las mismas líneas de caché en sus cachés L1 al mismo tiempo, pero cuando un núcleo escribe en estas direcciones, se invalida en todos los demás cachés L1, y luego tienen que volver a cargarlo antes de poder hacerlo. nada con eso. Perdón por la redacción imprecisa (incorrecta). :)
jalf
44

Recomiendo leer el artículo de 9 partes Lo que todo programador debe saber sobre la memoria de Ulrich Drepper si está interesado en cómo interactúan la memoria y el software. También está disponible como PDF de 104 páginas .

Las secciones especialmente relevantes para esta pregunta pueden ser la Parte 2 (cachés de CPU) y la Parte 5 (Qué pueden hacer los programadores: optimización de caché).

Tomi Kyöstilä
fuente
16
Debe agregar un resumen de los puntos principales del artículo.
Azmisov
Gran lectura, pero otro libro que DEBE mencionarse aquí es Hennessy, Patterson, Computer Architecture, A Quantitiative Approach , que está disponible en su quinta edición hasta hoy.
Haymo Kutschbach el
15

Además de los patrones de acceso a datos, un factor importante en el código compatible con caché es el tamaño de los datos . Menos datos significa que más caben en el caché.

Esto es principalmente un factor con estructuras de datos alineadas con la memoria. La sabiduría "convencional" dice que las estructuras de datos deben estar alineadas en los límites de las palabras porque la CPU solo puede acceder a palabras completas, y si una palabra contiene más de un valor, debe realizar un trabajo adicional (lectura-modificación-escritura en lugar de una simple escritura) . Pero los cachés pueden invalidar por completo este argumento.

Del mismo modo, una matriz booleana de Java utiliza un byte completo para cada valor para permitir operar directamente en valores individuales. Puede reducir el tamaño de los datos en un factor de 8 si usa bits reales, pero luego el acceso a valores individuales se vuelve mucho más complejo, lo que requiere operaciones de cambio de bits y máscara (la BitSetclase lo hace por usted). Sin embargo, debido a los efectos de caché, esto puede ser considerablemente más rápido que usar un booleano [] cuando la matriz es grande. IIRC Una vez logré una aceleración por un factor de 2 o 3 de esta manera.

Michael Borgwardt
fuente
9

La estructura de datos más efectiva para un caché es una matriz. Los cachés funcionan mejor si su estructura de datos se presenta secuencialmente a medida que las CPU leen líneas de caché completas (generalmente 32 bytes o más) a la vez desde la memoria principal.

Cualquier algoritmo que acceda a la memoria en orden aleatorio destruye los cachés porque siempre necesita nuevas líneas de caché para acomodar la memoria a la que se accede aleatoriamente. Por otro lado, un algoritmo, que se ejecuta secuencialmente a través de una matriz, es mejor porque:

  1. Le da a la CPU la oportunidad de seguir leyendo, por ejemplo, especulativamente poner más memoria en la memoria caché, a la que se accederá más adelante. Esta lectura anticipada ofrece un gran aumento de rendimiento.

  2. Ejecutar un ciclo cerrado sobre una matriz grande también permite que la CPU guarde en caché el código que se ejecuta en el ciclo y, en la mayoría de los casos, le permite ejecutar un algoritmo completamente desde la memoria caché sin tener que bloquear el acceso a la memoria externa.

Grover
fuente
@Grover: Acerca de su punto 2. Entonces, ¿se puede decir que si dentro de un bucle cerrado, se llama a una función para cada recuento de bucles, entonces buscará un nuevo código por completo y provocará una pérdida de caché, en cambio si puede poner la función como un código en el bucle for en sí, sin llamada de función, ¿sería más rápido debido a menos errores de caché?
goldenmean
1
Si y no. La nueva función se cargará en la memoria caché. Si hay suficiente espacio en la memoria caché, en la segunda iteración ya tendrá esa función en la memoria caché, por lo que no hay razón para volver a cargarla. Por lo tanto, es un éxito en la primera llamada. En C / C ++, puede pedirle al compilador que coloque las funciones una al lado de la otra utilizando los segmentos apropiados.
grover
Una nota más: si llama fuera del bucle y no hay suficiente espacio en caché, la nueva función se cargará en caché independientemente. Incluso puede suceder que el bucle original se expulse de la memoria caché. En este caso, la llamada incurrirá en hasta tres penalizaciones por cada iteración: una para cargar el objetivo de la llamada y otra para recargar el bucle. Y un tercero si el cabezal del bucle no está en la misma línea de caché que la dirección de retorno de la llamada. En ese caso, saltar al cabezal del bucle también necesita un nuevo acceso a la memoria.
grover
8

Un ejemplo que vi usado en un motor de juego fue mover datos de objetos a sus propias matrices. Un objeto del juego que estaba sujeto a la física también podría tener muchos otros datos adjuntos. Pero durante el ciclo de actualización de física, todo lo que le importaba al motor eran los datos sobre posición, velocidad, masa, cuadro delimitador, etc. Así que todo eso se colocó en sus propios arreglos y se optimizó lo más posible para SSE.

Entonces, durante el bucle de física, los datos de física se procesaron en orden de matriz usando matemática vectorial. Los objetos del juego usaron su ID de objeto como índice en las diversas matrices. No era un puntero porque los punteros podrían quedar invalidados si las matrices debían ser reubicadas.

En muchos sentidos, esto violó los patrones de diseño orientado a objetos, pero hizo que el código fuera mucho más rápido al colocar datos muy juntos que debían ser operados en los mismos bucles.

Este ejemplo probablemente esté desactualizado porque espero que la mayoría de los juegos modernos usen un motor de física precompilado como Havok.

Zan Lynx
fuente
2
+1 Nada desactualizado. Esta es la mejor manera de organizar los datos para los motores de juegos: haga que los bloques de datos sean contiguos y realice todo un tipo de operación (por ejemplo, AI) antes de pasar a la siguiente (por ejemplo, física) para aprovechar la proximidad / localidad del caché referencia.
Ingeniero
Vi este ejemplo exacto en un video en algún lugar hace un par de semanas, pero desde entonces he perdido el enlace / no recuerdo cómo encontrarlo. ¿Recuerdas dónde viste este ejemplo?
será el
@will: No, no recuerdo exactamente dónde fue esto.
Zan Lynx
Esta es la idea misma de un sistema de componentes de entidad (ECS: en.wikipedia.org/wiki/Entity_component_system ). Almacene los datos como estructuras de estructuras en lugar de las estructuras de estructuras más tradicionales que las prácticas de OOP fomentan.
BuschnicK
7

Solo una publicación lo tocó, pero surge un gran problema al compartir datos entre procesos. Desea evitar que varios procesos intenten modificar la misma línea de caché simultáneamente. Algo a tener en cuenta aquí es el intercambio "falso", donde dos estructuras de datos adyacentes comparten una línea de caché y las modificaciones a una invalidan la línea de caché para la otra. Esto puede hacer que las líneas de caché se muevan innecesariamente de un lado a otro entre los cachés de procesador que comparten los datos en un sistema multiprocesador. Una forma de evitarlo es alinear y rellenar las estructuras de datos para colocarlas en diferentes líneas.

RussellH
fuente
7

Un comentario al "ejemplo clásico" por el usuario 1800 INFORMACIÓN (demasiado largo para un comentario)

Quería verificar las diferencias de tiempo para dos órdenes de iteración ("outter" e "inner"), así que hice un experimento simple con una gran matriz 2D:

measure::start();
for ( int y = 0; y < N; ++y )
for ( int x = 0; x < N; ++x )
    sum += A[ x + y*N ];
measure::stop();

y el segundo caso con los forbucles intercambiados.

La versión más lenta ("x primero") fue de 0,88 segundos y la más rápida, de 0,06 segundos. Ese es el poder del almacenamiento en caché :)

Solía gcc -O2y todavía los bucles no estaban optimizados. El comentario de Ricardo de que "la mayoría de los compiladores modernos pueden resolver esto por sí mismos" no es válido

Jakub M.
fuente
No estoy seguro de entender esto. En ambos ejemplos, todavía está accediendo a cada variable en el bucle for. ¿Por qué es un camino más rápido que el otro?
ed-
en última instancia, intuitivo para mí entender cómo afecta :)
Laie
@EdwardCorlew Es por el orden en que se accede a ellos. El primer orden y es más rápido porque accede a los datos secuencialmente. Cuando se solicita la primera entrada, el caché L1 carga una línea de caché completa, que incluye el int solicitado más los siguientes 15 (suponiendo una línea de caché de 64 bytes), por lo que no hay pérdida de CPU esperando los próximos 15. La x -primer orden es más lento porque el elemento al que se accede no es secuencial, y presumiblemente N es lo suficientemente grande como para que la memoria a la que se accede siempre esté fuera de la caché L1 y, por lo tanto, todas las operaciones se bloquean.
Matt Parkins, el
4

Puedo responder (2) diciendo que en el mundo C ++, las listas vinculadas pueden matar fácilmente el caché de la CPU. Las matrices son una mejor solución siempre que sea posible. No hay experiencia sobre si lo mismo se aplica a otros idiomas, pero es fácil imaginar que surgirían los mismos problemas.

Andrés
fuente
@ Andrew: ¿Qué hay de las estructuras? ¿Son eficientes en caché? ¿Tienen alguna restricción de tamaño para ser eficiente en caché?
goldenmean
Una estructura es un solo bloque de memoria, por lo que siempre que no exceda el tamaño de su caché no verá un impacto. Solo cuando tenga una colección de estructuras (o clases) verá los resultados de la memoria caché y dependerá de la forma en que organice la colección. Una matriz une los objetos entre sí (bien), pero una lista vinculada puede tener objetos en todo el espacio de direcciones con enlaces entre ellos, lo que obviamente es malo para el rendimiento de la memoria caché.
Andrew
Una forma de usar listas vinculadas sin eliminar el caché, lo más eficaz para listas no grandes, es crear su propio grupo de memoria, es decir, asignar una gran matriz. luego, en lugar de 'malloc' (o 'new'ing en C ++) de memoria para cada pequeño miembro de la lista vinculada, que puede asignarse en un lugar completamente diferente en la memoria y desperdicia espacio de administración, le da memoria de su grupo de memoria, Al aumentar considerablemente las probabilidades de que los miembros de la lista se cierren lógicamente, estarán juntos en la memoria caché.
Liran Orevi
Claro, pero es mucho trabajo obtener std :: list <> et al. para usar tus bloques de memoria personalizados. Cuando era un joven whippersnapper, absolutamente seguí ese camino, pero en estos días ... demasiadas otras cosas para abordar.
Andrew
4

La caché está organizada en "líneas de caché" y la memoria (real) se lee y se escribe en fragmentos de este tamaño.

Las estructuras de datos que están contenidas dentro de una sola línea de caché son, por lo tanto, más eficientes.

Del mismo modo, los algoritmos que acceden a bloques de memoria contiguos serán más eficientes que los algoritmos que saltan a través de la memoria en un orden aleatorio.

Desafortunadamente, el tamaño de la línea de caché varía drásticamente entre los procesadores, por lo que no hay forma de garantizar que una estructura de datos que sea óptima en un procesador sea eficiente en cualquier otro.

Alnitak
fuente
no necesariamente. solo ten cuidado con el intercambio falso. a veces tienes que dividir los datos en diferentes líneas de caché. qué tan efectivo es el caché siempre depende de cómo lo usas.
DAG
4

Preguntar cómo hacer un código, caché efectivo-amigable y la mayoría de las otras preguntas, generalmente es preguntar cómo optimizar un programa, eso es porque el caché tiene un impacto tan grande en el rendimiento que cualquier programa optimizado es uno que es caché efectivo de caché amigable.

Sugiero leer sobre Optimización, hay algunas buenas respuestas en este sitio. En términos de libros, recomiendo en Sistemas informáticos: la perspectiva de un programador que tiene un buen texto sobre el uso adecuado de la memoria caché.

(por cierto, por muy malo que pueda ser un error de caché, hay algo peor, si un programa está buscando desde el disco duro ...)

Liran Orevi
fuente
4

Ha habido muchas respuestas sobre consejos generales como selección de estructura de datos, patrón de acceso, etc. Aquí me gustaría agregar otro patrón de diseño de código llamado canalización de software que hace uso de la gestión activa de caché.

La idea es tomar prestado de otras técnicas de canalización, por ejemplo, canalización de instrucciones de CPU.

Este tipo de patrón se aplica mejor a los procedimientos que

  1. podría desglosarse en múltiples subpasos razonables, S [1], S [2], S [3], ... cuyo tiempo de ejecución es más o menos comparable con el tiempo de acceso a RAM (~ 60-70ns).
  2. toma un lote de entrada y realiza varios pasos antes mencionados para obtener el resultado.

Tomemos un caso simple donde solo hay un subprocedimiento. Normalmente el código le gustaría:

def proc(input):
    return sub-step(input))

Para tener un mejor rendimiento, es posible que desee pasar múltiples entradas a la función en un lote para amortizar la sobrecarga de llamadas de función y también aumente la localidad de caché de código.

def batch_proc(inputs):
    results = []
    for i in inputs:
        // avoids code cache miss, but still suffer data(inputs) miss
        results.append(sub-step(i))
    return res

Sin embargo, como se dijo anteriormente, si la ejecución del paso es aproximadamente la misma que el tiempo de acceso a RAM, puede mejorar aún más el código para algo como esto:

def batch_pipelined_proc(inputs):
    for i in range(0, len(inputs)-1):
        prefetch(inputs[i+1])
        # work on current item while [i+1] is flying back from RAM
        results.append(sub-step(inputs[i-1]))

    results.append(sub-step(inputs[-1]))

El flujo de ejecución se vería así:

  1. captación previa (1) pide a la CPU que prefetch la entrada [1] en la memoria caché, donde la instrucción de captación previa toma los ciclos P y regresa, y en el fondo la entrada [1] llegaría a la memoria caché después de los ciclos R.
  2. trabajos_en (0) fallo en frío en 0 y funciona en él, lo que requiere M
  3. captación previa (2) emite otra búsqueda
  4. trabajos_en (1) si P + R <= M, entonces las entradas [1] ya deberían estar en la caché antes de este paso, por lo tanto, evitar una pérdida de caché de datos
  5. trabajos_en (2) ...

Podría haber más pasos involucrados, luego puede diseñar una tubería de múltiples etapas siempre que el tiempo de los pasos y la latencia de acceso a la memoria coincidan, sufriría una pequeña falta de código / caché de datos. Sin embargo, este proceso debe ajustarse con muchos experimentos para descubrir la agrupación correcta de pasos y el tiempo de captación previa. Debido a su esfuerzo requerido, ve más adopción en el procesamiento de flujo de datos / paquetes de alto rendimiento. Se puede encontrar un buen ejemplo de código de producción en el diseño de la tubería DPDK QoS Enqueue: http://dpdk.org/doc/guides/prog_guide/qos_framework.html Capítulo 21.2.4.3. Enqueue Pipeline.

Se puede encontrar más información:

https://software.intel.com/en-us/articles/memory-management-for-optimal-performance-on-intel-xeon-phi-coprocessor-alignment-and

http://infolab.stanford.edu/~ullman/dragon/w06/lectures/cs243-lec13-wei.pdf

Wei Shen
fuente
1

Escriba su programa para tomar un tamaño mínimo. Es por eso que no siempre es una buena idea usar optimizaciones de -O3 para GCC. Ocupa un tamaño más grande. A menudo, -Os es tan bueno como -O2. Sin embargo, todo depende del procesador utilizado. YMMV.

Trabaje con pequeños fragmentos de datos a la vez. Es por eso que un algoritmo de clasificación menos eficiente puede ejecutarse más rápido que el ordenamiento rápido si el conjunto de datos es grande. Encuentre formas de dividir sus conjuntos de datos más grandes en conjuntos más pequeños. Otros han sugerido esto.

Para ayudarlo a explotar mejor la ubicación temporal / espacial de la instrucción, es posible que desee estudiar cómo su código se convierte en ensamblado. Por ejemplo:

for(i = 0; i < MAX; ++i)
for(i = MAX; i > 0; --i)

Los dos bucles producen códigos diferentes a pesar de que simplemente analizan una matriz. En cualquier caso, su pregunta es muy específica de la arquitectura. Por lo tanto, su única forma de controlar estrictamente el uso de la memoria caché es comprender cómo funciona el hardware y optimizar su código.

sybreon
fuente
Punto interesante ¿Las memorias caché anticipadas hacen suposiciones basadas en la dirección de un bucle / paso a través de la memoria?
Andrew
1
Hay muchas formas de diseñar cachés de datos especulativos. Los basados ​​en pasos miden la 'distancia' y la 'dirección' de los accesos a datos. Los basados ​​en contenido persiguen cadenas de punteros. Hay otras formas de diseñarlos.
sybreon
1

Además de alinear su estructura y campos, si su estructura si está asignada en el montón, es posible que desee utilizar asignadores que admitan asignaciones alineadas; como _aligned_malloc (sizeof (DATA), SYSTEM_CACHE_LINE_SIZE); de lo contrario, puede compartir falsos al azar; recuerde que en Windows, el montón predeterminado tiene una alineación de 16 bytes.

aracntido
fuente