tipos sirve que para mis memoria informatica fotos definicion caracteristicas caché cache bueno borro borrar borran asynchronous f# functional-programming parallel-processing multicore

asynchronous - sirve - si borro la memoria cache se borran mis fotos



Prácticas recomendadas para la localidad de memoria caché en Paralelismo multinúcleo en F# (6)

No soy un experto en paralelismo, pero este es mi consejo de todos modos.

  1. Me gustaría esperar que un enfoque localmente mutable donde cada núcleo se le asigna un área de memoria que es tanto de lectura como escrita siempre supere un enfoque puro.
  2. Intente formular su algoritmo para que funcione secuencialmente en un área contigua de la memoria. Esto significa que si está trabajando con gráficos, puede valer la pena "aplanar" nodos en matrices y reemplazar referencias por índices antes del procesamiento. Independientemente de los problemas de ubicación de caché, esta es siempre una buena técnica de optimización en .NET, ya que ayuda a mantener la recolección de basura fuera del camino.

Estoy estudiando el paralelismo multinúcleo en F #. Debo admitir que la inmutabilidad realmente ayuda a escribir una implementación paralela correcta. Sin embargo, es difícil lograr una buena aceleración y una buena escalabilidad cuando crece la cantidad de núcleos. Por ejemplo, mi experiencia con el algoritmo de clasificación rápida es que muchos intentos para implementar clasificación rápida paralela de una manera puramente funcional y el uso de List o Array como la representación son fallidos. La creación de perfiles de esas implementaciones muestra que el número de errores de caché aumenta significativamente en comparación con los de las versiones secuenciales. Sin embargo, si uno implementa Quick Sort paralela usando mutación dentro de las matrices, se podría obtener una buena aceleración. Por lo tanto, creo que la mutación podría ser una buena práctica para optimizar el paralelismo multinúcleo.

Creo que la localidad de caché es un gran obstáculo para el paralelismo multinúcleo en un lenguaje funcional. La programación funcional implica la creación de muchos objetos efímeros; la destrucción de esos objetos puede destruir la propiedad de coherencia de las memorias caché de la CPU. He visto muchas sugerencias sobre cómo mejorar la ubicación del caché en idiomas imperativos, por ejemplo, here y here . Pero no tengo claro cómo se realizarían en la programación funcional, especialmente con estructuras de datos recursivas como árboles, etc., que aparecen con bastante frecuencia.

¿Hay alguna técnica para mejorar la localidad de caché en un lenguaje funcional impuro (específicamente F #) ? Cualquier consejo o ejemplo de código son más que bienvenidos.

Para escribir aplicaciones escalables, la ubicación de la memoria caché es primordial para la velocidad de su aplicación. Los principios están bien explicados por la charla de Scott Meyers . La inmutabilidad no funciona bien con la localidad de caché, ya que crea nuevos objetos en la memoria, lo que obliga a la CPU a volver a cargar los datos del nuevo objeto. Como se menciona en la charla, incluso en las CPU modernas, la memoria caché L1 tiene solo 32 KB de tamaño que se comparte para el código y los datos entre todos los núcleos. Si usa múltiples hilos, debe tratar de consumir la menor cantidad de memoria posible (adiós a la inmutabilidad) para permanecer en el caché más rápido. La memoria caché L2 es de aproximadamente 4-8 MB, que es mucho más grande pero aún pequeña en comparación con los datos que está tratando de ordenar.

Si logras escribir una aplicación que consuma la menor cantidad de memoria posible (localidad de caché de datos), puedes obtener aceleraciones de 20 o más. Pero si gestionas esto para 1 núcleo, podría ser muy útil que escalar a más núcleos perjudicará el rendimiento, ya que todos los núcleos compiten por el mismo caché L2.

Para sacar el máximo provecho de esto, los chicos de C ++ usan PGA (Optimizaciones Guiadas por Perfil) que les permite perfilar su aplicación que se usa como datos de entrada para que el compilador emita un código mejor optimizado para el caso de uso específico.

Puede mejorar en cierta medida en un código administrado, pero dado que hay tantos factores que influyen en su localidad de memoria caché, no es probable que vea una aceleración de 20 en el mundo real debido a la localidad de memoria caché total. Este sigue siendo el régimen de C ++ y compiladores que utilizan datos de generación de perfiles.

Permitir la mutabilidad dentro de las funciones en F # es una bendición, pero solo debe usarse al optimizar el código. El estilo puramente funcional a menudo produce una implementación más intuitiva y, por lo tanto, es preferible.

Esto es lo que devolvió una búsqueda rápida: Parallel Quicksort en Haskell . Mantengamos el debate sobre el rendimiento centrado en el rendimiento. Elija un procesador y luego ajústelo con un algoritmo específico.

Para responder a su pregunta sin detalles, diría que el enfoque de Clojure para implementar STM podría ser una lección en general sobre cómo desacoplar las rutas de ejecución en procesadores multinúcleo y mejorar la ubicación del caché. Pero solo es efectivo cuando el número de lecturas supera el número de escrituras.

Por lo que puedo entender, la clave para ubicar la localidad (multiproceso o no) es

  • Mantenga las unidades de trabajo en un bloque contiguo de RAM que se ajustará a la memoria caché

Para tal fin ;

  • Evitar objetos donde sea posible
    • Los objetos se asignan en el montón y pueden rociarse por todos lados, dependiendo de la fragmentación del montón, etc.
    • Tiene esencialmente cero control sobre la ubicación de la memoria de los objetos, en la medida en que el GC pueda moverlos en cualquier momento.
  • Usa arreglos. Las matrices son interpretadas por la mayoría de los compiladores como un bloque contiguo de memoria.
    • Otros tipos de datos de colección pueden distribuir cosas en cualquier lugar: las listas vinculadas, por ejemplo, están compuestas de punteros.
  • Usa matrices de tipos primitivos. Los tipos de objeto se asignan en el montón, por lo que una matriz de objetos es solo una matriz de punteros a objetos que pueden distribuirse por todo el montón.
  • Usa matrices de estructuras, si no puedes usar primitivas. Las estructuras tienen sus campos organizados secuencialmente en la memoria, y los compiladores .NET los tratan como primitivos.
  • Calcula el tamaño de la memoria caché en la máquina en la que la ejecutarás
    • Las CPU tienen cachés L2 de diferentes tamaños
    • Puede ser prudente diseñar su código para escalar con diferentes tamaños de caché
    • O más simplemente, escriba el código que se ajustará dentro del menor tamaño de caché común en el que se ejecutará su código
  • Calcula lo que debe sentarse cerca de cada dato
    • En la práctica, no vas a encajar todo tu conjunto de trabajo en el caché L2
    • Examine (o rediseñe) sus algoritmos para que las estructuras de datos que está utilizando mantengan los datos que se necesitan "próximos" cerca de los datos que se necesitaban anteriormente.

En la práctica esto significa que puede terminar usando estructuras de datos que no son ejemplos teóricos perfectos de la informática, pero está bien, las computadoras tampoco son ejemplos teóricos perfectos de la informática.

Un buen documento académico sobre el tema es Cache-Efficient String Sorting Using Copying

Un buen enfoque es dividir el trabajo en secciones más pequeñas e iterar sobre cada sección en cada núcleo.

Una opción con la que comenzaría es buscar mejoras en la ubicación del caché en un solo núcleo antes de ir en paralelo, simplemente debería ser una cuestión de subdividir el trabajo nuevamente para cada núcleo. Por ejemplo, si está haciendo cálculos matriciales con matrices grandes, entonces podría dividir los cálculos en secciones más pequeñas.

Aquí hay un gran ejemplo de eso: Cache Locality For Performance

Hubo algunas secciones excelentes en el libro de Tomas Petricek, Programación funcional Real Work ; consulte el Capítulo 14, Escritura de programas funcionales paralelos, puede encontrar el procesamiento paralelo de un árbol binario de particular interés.