En informática , un patrón de acceso a la memoria o patrón de acceso de E / S es el patrón con el que un sistema o programa lee y escribe la memoria en el almacenamiento secundario . Estos patrones difieren en el nivel de localidad de referencia y afectan drásticamente el rendimiento de la caché , [1] y también tienen implicaciones para el enfoque del paralelismo [2] [3] y la distribución de la carga de trabajo en los sistemas de memoria compartida . [4] Además, los problemas de coherencia de la caché pueden afectar el rendimiento del multiprocesador , [5]lo que significa que ciertos patrones de acceso a la memoria ponen un techo al paralelismo (que muchos enfoques básicos buscan romper). [6]
La memoria de la computadora generalmente se describe como " acceso aleatorio ", pero los recorridos por software aún exhibirán patrones que pueden explotarse para mayor eficiencia. Existen varias herramientas para ayudar a los diseñadores de sistemas [7] y programadores a comprender, analizar y mejorar el patrón de acceso a la memoria, incluyendo VTune y Vectorization Advisor , [8] [9] [10] [11] [12] incluyendo herramientas para abordar el acceso a la memoria de la GPU patrones [13]
Los patrones de acceso a la memoria también tienen implicaciones para la seguridad , [14] [15] lo que motiva a algunos a intentar disfrazar la actividad de un programa por razones de privacidad . [16] [17]
Ejemplos de
Secuencial
El extremo más simple es el patrón de acceso secuencial , donde los datos se leen, procesan y escriben con direccionamiento incrementado / decrementado sencillo. Estos patrones de acceso son muy fáciles de obtener previamente .
Strided
Los patrones de acceso 2D, 3D, escalonados o simples (por ejemplo, paso a paso a través de matrices multidimensionales ) son igualmente fáciles de predecir y se encuentran en implementaciones de algoritmos de álgebra lineal y procesamiento de imágenes . El mosaico en bucle es un enfoque eficaz. [19] Algunos sistemas con DMA proporcionaron un modo escalonado para transferir datos entre sutiles de matrices 2D más grandes y memoria de scratchpad . [20]
Lineal
Un patrón de acceso lineal está estrechamente relacionado con "strided", donde una dirección de memoria puede calcularse a partir de una combinación lineal de algún índice. Pasar por índices secuencialmente con un patrón lineal produce un acceso escalonado . Un patrón de acceso lineal para escrituras (con cualquier patrón de acceso para lecturas que no se superponen) puede garantizar que un algoritmo pueda ser paralelizado, lo cual se explota en sistemas que soportan núcleos de computación .
Vecino más cercano
Los patrones de acceso a la memoria del vecino más cercano aparecen en la simulación y están relacionados con patrones secuenciales o escalonados. Un algoritmo puede atravesar una estructura de datos utilizando información de los vecinos más cercanos de un elemento de datos (en una o más dimensiones) para realizar un cálculo. Estos son comunes en las simulaciones de física que operan en redes. [21] El vecino más cercano también puede referirse a la comunicación entre nodos en un clúster; Las simulaciones físicas que se basan en tales patrones de acceso local se pueden paralelizar con los datos divididos en nodos de clúster, con comunicación puramente del vecino más cercano entre ellos, lo que puede tener ventajas para la latencia y el ancho de banda de comunicación. Este caso de uso se relaciona bien con la topología de la red toroide . [22]
2D espacialmente coherente
En la representación 3D , los patrones de acceso para el mapeo de texturas y la rasterización de pequeñas primitivas (con distorsiones arbitrarias de superficies complejas) están lejos de ser lineales, pero aún pueden exhibir una localidad espacial (por ejemplo, en el espacio de la pantalla o el espacio de textura ). Esto se puede convertir en una buena localidad de memoria a través de alguna combinación de orden morton [23] y mosaico para mapas de textura y datos de búfer de cuadros (mapeando regiones espaciales en líneas de caché), o clasificando primitivas mediante renderizado diferido basado en mosaicos . [24] También puede ser ventajoso almacenar matrices en orden Morton en bibliotecas de álgebra lineal . [25]
Dispersión
Un patrón de acceso a la memoria de dispersión combina lecturas secuenciales con direccionamiento indexado / aleatorio para escrituras. [26] En comparación con la recopilación, puede colocar menos carga en una jerarquía de caché, ya que un elemento de procesamiento puede enviar escrituras de una manera de "disparar y olvidar" (omitiendo una caché por completo), mientras utiliza una captura previa predecible (o incluso DMA) para su fuente. datos.
Sin embargo, puede ser más difícil de paralelizar ya que no hay garantía de que las escrituras no interactúen, [27] y muchos sistemas todavía están diseñados asumiendo que una caché de hardware fusionará muchas escrituras pequeñas en otras más grandes.
En el pasado, el mapeo de texturas directo intentaba manejar la aleatoriedad con "escrituras", mientras se leía secuencialmente la información de textura de origen.
La consola PlayStation 2 usó mapeo de textura inversa convencional, pero manejó cualquier procesamiento de dispersión / recolección "en chip" usando EDRAM, mientras que el modelo 3D (y una gran cantidad de datos de textura) de la memoria principal fue alimentado secuencialmente por DMA. Esta es la razón por la que carecía de soporte para primitivas indexadas y, a veces, necesitaba administrar texturas "por adelantado" en la lista de visualización .
Recolectar
En un patrón de acceso a memoria recopilada , las lecturas se direccionan o indexan aleatoriamente, mientras que las escrituras son secuenciales (o lineales). [26] Un ejemplo se encuentra en el mapeo de textura inversa , donde los datos se pueden escribir linealmente a través de las líneas de exploración , mientras que las direcciones de textura de acceso aleatorio se calculan por píxel .
En comparación con la dispersión, la desventaja es que el almacenamiento en caché (y eludir latencias) ahora es esencial para lecturas eficientes de elementos pequeños, sin embargo, es más fácil de paralelizar ya que se garantiza que las escrituras no se superpondrán. Como tal, el enfoque de recopilación es más común para la programación de gpgpu , [27] donde el subproceso masivo (habilitado por el paralelismo) se usa para ocultar las latencias de lectura. [27]
Recolectar y dispersar combinados
Un algoritmo puede recopilar datos de una fuente, realizar algunos cálculos en la memoria local o en el chip y dispersar los resultados en otra parte. Esta es esencialmente la operación completa de una canalización de GPU cuando se realiza una representación 3D : recopilar vértices y texturas indexadas y dispersar píxeles sombreados en el espacio de la pantalla . La rasterización de primitivas opacas usando un búfer de profundidad es "conmutativa", lo que permite el reordenamiento, lo que facilita la ejecución en paralelo. En el caso general, se necesitarían primitivas de sincronización.
Aleatorio
En el extremo opuesto hay un patrón de acceso a la memoria verdaderamente aleatorio. Algunos sistemas multiprocesador están especializados para lidiar con estos. [28] El enfoque PGAS puede ayudar clasificando las operaciones por datos sobre la marcha (útil cuando el problema * es * averiguar la ubicación de los datos no clasificados). [21] Las estructuras de datos que dependen en gran medida de la búsqueda de punteros a menudo pueden producir una localidad de referencia deficiente , aunque la clasificación a veces puede ayudar. Dado un patrón de acceso a la memoria verdaderamente aleatorio, es posible dividirlo (incluidas las etapas de dispersión o recopilación, u otra clasificación intermedia), lo que puede mejorar la localidad en general; esto suele ser un requisito previo para la paralelización .
Enfoques
Diseño orientado a datos
El diseño orientado a datos es un enfoque destinado a maximizar la localidad de referencia, mediante la organización de los datos de acuerdo con la forma en que se atraviesan en varias etapas de un programa, en contraste con el enfoque orientado a objetos más común (es decir, organizar de tal manera que el diseño de datos refleje explícitamente el patrón de acceso). [29]
Contraste con la localidad de referencia
La localidad de referencia se refiere a una propiedad exhibida por patrones de acceso a la memoria. Un programador cambiará el patrón de acceso a la memoria (reelaborando algoritmos) para mejorar la localidad de referencia, [30] y / o aumentar el potencial de paralelismo. [26] Un programador o diseñador de sistemas puede crear marcos o abstracciones (por ejemplo, plantillas C ++ o funciones de orden superior ) que encapsulan un patrón de acceso a la memoria específico. [31] [32]
En el paralelismo aparecen diferentes consideraciones para los patrones de acceso a la memoria más allá de la localidad de referencia, a saber, la separación de lecturas y escrituras. Por ejemplo: incluso si las lecturas y escrituras son "perfectamente" locales, puede ser imposible paralelizar debido a las dependencias ; separar las lecturas y escrituras en áreas separadas produce un patrón de acceso a la memoria diferente, tal vez inicialmente parezca peor en términos de localidad pura, pero deseable para aprovechar el hardware paralelo moderno. [26]
La localidad de referencia también puede referirse a variables individuales (por ejemplo, la capacidad de un compilador de almacenarlas en caché en registros ), mientras que el término patrón de acceso a la memoria solo se refiere a los datos almacenados en una memoria indexable (especialmente la memoria principal ).
Ver también
- Gather-scatter (direccionamiento vectorial)
- Localidad de referencia
- Computación paralela
- Conjunto de trabajo
Referencias
- ^ "diseño orientado a datos" (PDF) .
- ^ Jang, Byunghyun; Schaa, Dana; Mistry, Perhaad y Kaeli, David (27 de mayo de 2010). "Explotación de patrones de acceso a la memoria para mejorar el rendimiento de la memoria en arquitecturas paralelas de datos". Transacciones IEEE en sistemas paralelos y distribuidos . Nueva York: IEEE . 22 (1): 105-118. doi : 10.1109 / TPDS.2010.107 . eISSN 1558-2183 . ISSN 1045-9219 . S2CID 15997131 . ID único de NLM 101212014.
- ^ Jeffers, James; Reinders, James; Sodani, Avinash (31 de mayo de 2016). Optimización de xeon phi . ISBN 9780128091951.
- ^ "Análisis de energía y rendimiento de transformaciones de código para patrones de acceso a datos basados en PGAS" (PDF) .
- ^ "Mejora de las arquitecturas coherentes de caché con patrones de acceso a la memoria para sistemas integrados de muchos núcleos" (PDF) .
- ^ "intel terascale" (PDF) .
- ^ "análisis de patrones de acceso a la memoria" .
- ^ "QUAD un analizador de patrones de acceso a la memoria" (PDF) .
- ^ "Dymaxion: optimización de patrones de acceso a la memoria para sistemas heterogéneos" (PDF) .
- ^ "Evaluación de un esquema de clasificación de acceso a la memoria para programas numéricos y con uso intensivo de punteros". CiteSeerX 10.1.1.48.4163 . Cite journal requiere
|journal=
( ayuda ) - ^ Matsubara, Yuki; Sato, Yukinori (2014). "Análisis de patrones de acceso a memoria en línea en una herramienta de creación de perfiles de aplicaciones". 2014 Segundo Simposio Internacional de Computación y Redes . págs. 602–604. doi : 10.1109 / CANDAR.2014.86 . ISBN 978-1-4799-4152-0. S2CID 16476418 .
- ^ "Poniendo sus datos y código en orden: datos y diseño" .
- ^ "CuMAPz: una herramienta para analizar patrones de acceso a la memoria en CUDA" .
- ^ "Protección de patrones de acceso a la memoria para dispositivos con recursos limitados" (PDF) .
- ^ "comprensión de los ataques de caché" (PDF) .
- ^ "protección de datos en la nube" .
- ^ "aumentar-la-seguridad-en-la-nube-con ---- oblivious-ram" .diseño de RAM propuesto para evitar vulnerabilidades de patrones de acceso a la memoria
- ^ Chuck Paridon. "Pautas de evaluación comparativa del rendimiento del almacenamiento - Parte I: Diseño de la carga de trabajo" (PDF) .
En la práctica, los patrones de acceso IO son tan numerosos como las estrellas
- ^ "optimización de la ubicación de datos y mosaico" (PDF) .el papel cubre el mosaico de bucle y la implicación para el código paralelo
- ^ "Partición óptima de datos 2D para transferencias DMA en MPSoCs" (PDF) .
- ^ a b "Programación del espacio de direcciones global particionado" .cubre casos en los que PGAS es una ventaja, en los que es posible que los datos no estén ya ordenados, por ejemplo, al tratar con gráficos complejos; consulte "ciencia en todo el espectro de irregularidades".
- ^ "Cuantificación de la localidad en los patrones de acceso a la memoria de las aplicaciones HPC" (PDF) .menciona los patrones de acceso del vecino más cercano en grupos
- ^ "El diseño y análisis de una arquitectura de caché para el mapeo de texturas" (PDF) .ver orden de morton, patrón de acceso a la textura
- ^ "Orden de morton para acelerar el texturizado" (PDF) .
- ^ "Las matrices de orden de Morton merecen el informe técnico de soporte de los compiladores 533" (PDF) .analiza la importancia del orden de Morton para las matrices
- ^ a b c d "dispersión gpgpu vs recopilación" . Archivado desde el original el 14 de junio de 2016 . Consultado el 13 de junio de 2016 .
- ^ a b c Gemas de GPU . 2011-01-13. ISBN 9780123849892.trata sobre "patrones de acceso a la memoria dispersa" y "recopilar patrones de acceso a la memoria" en el texto
- ^ "Cray y HPCC: desarrollos de referencia y resultados del año pasado" (PDF) .consulte los resultados globales de acceso aleatorio para Cray X1. arquitectura vectorial para ocultar latencias, no tan sensible a la coherencia de la caché
- ^ "diseño orientado a datos" (PDF) .
- ^ "optimizar-estructuras-de-datos-y-patrones-de-acceso-a-memoria-para-mejorar-la-localidad-de-datos" .
- ^ "Motor de acceso a memoria basado en plantillas para aceleradores en SoC" (PDF) .
- ^ "Vectorización de objetivos múltiples con biblioteca genérica MTPS C ++" (PDF) .una biblioteca de plantillas C ++ para producir patrones de acceso a memoria optimizados