algorithm - paralelos - programacion paralela
¿Algoritmos de caché no aplicable para programación paralela? (3)
He leído mucho sobre los algoritmos de caché no aplicable y los árboles de transmisión, etc. Entiendo que lo básico que todavía no puedo ver es ¿por qué son buenos para la programación paralela? Creo que vi a John Harrop decir que son revolucionarios para eso.
En el artículo http://www.1024cores.net/home/parallel-computing/cache-oblivious-algorithms
Ellos señalan que
La idea detrás de los algoritmos de memoria caché es el uso eficiente de cachés de procesadores y la reducción de los requisitos de ancho de banda de memoria. Ambas cosas son igualmente importantes para los algoritmos de subproceso único, pero especialmente cruciales para los algoritmos paralelos, ya que el ancho de banda de memoria disponible suele compartirse entre los subprocesos de hardware y con frecuencia se convierte en un cuello de botella para la escalabilidad.
El acceso a la memoria puede ser un cuello de botella en algoritmos paralelos, por lo que tener algoritmos que intenten utilizar la memoria en caché puede ser más eficiente.
En el mismo artículo, describen cómo los algoritmos de caché inconscientes aprovechan el caché disponible:
Los algoritmos sin memoria caché funcionan dividiendo recursivamente el conjunto de datos de un problema en partes más pequeñas y luego haciendo la mayor cantidad posible de cómputos de cada parte. Eventualmente, el conjunto de datos de subproblemas encaja en la memoria caché, y podemos hacer una gran cantidad de cálculos sin tener que acceder a la memoria
Los procesadores multinúcleo tienen menos memoria caché por núcleo. La memoria caché en el procesador dedicado de un solo núcleo ocupa una gran cantidad de espacio en el silicio. Puedes verlo solo con la búsqueda de imágenes en google; encontrará que los tamaños de la memoria caché son enormes, por ejemplo, http://www.bit-tech.net/hardware/memory/2007/11/15/the_secrets_of_pc_memory_part_1/2
Por lo tanto, si tiene 20 núcleos y cada uno tiene 1/20 de la memoria caché de un procesador normal, será mejor que sus algoritmos funcionen bien sin un caché gigante. =)
Solo quiero señalar que su pregunta es particularmente importante dentro de la arquitectura multinúcleo donde los procesadores múltiples tienen sus propios cachés privados y cachés compartidos entre varios núcleos. Para poder lograr alta eficiencia y escalabilidad, un algoritmo paralelo tiene que demostrar una buena localidad espacial y localidad temporal en cachés de datos.
Antes de la tesis de maestría de Harald Prokop , los algoritmos y las estructuras de datos se diseñaron en una forma consciente de memoria caché para reducir la proporción de errores de caché, por ejemplo, B-tree es un ejemplo bien conocido de estructuras de datos con memoria caché en que el parámetro B se sintoniza usando el tamaño de caché de la CPU. En el modelo de caché inconsciente, debido a la naturaleza recursiva de los algoritmos, los subproblemas eventualmente encajan en cachés y la manipulación de dichos subproblemas incurre en un pequeño número de fallas de caché.
Algunas propiedades agradables de los algoritmos de caché ajena son independientes de los tamaños de caché de la CPU, funcionan bien en cualquier jerarquía de memoria y han demostrado ser óptimos en la complejidad de la caché. En el aumento del paralelismo multinúcleo, los algoritmos de memoria caché pueden jugar un papel importante en la obtención de programas paralelos de rendimiento. También veo una discusión interesante sobre estructuras de datos recursivas y algoritmos de memoria caché en el siguiente artículo http://blogs.msdn.com/b/devdev/archive/2007/06/12/cache-oblivious-data-structures.aspx .