En informática , un patrón de acceso a memoria o patrón de acceso IO es el patrón con el que un sistema o programa lee y escribe memoria en el almacenamiento secundario . Estos patrones difieren en el nivel de localidad de referencia y afectan drásticamente el rendimiento de la memoria caché , [1] y también tienen implicaciones para el enfoque del paralelismo [2] [3] y la distribución de la carga de trabajo en sistemas de memoria compartida . [4] Además, los problemas de coherencia de la memoria caché pueden afectar el rendimiento de los multiprocesadores , [5] lo que significa que ciertos patrones de acceso a la memoria imponen un límite al paralelismo (que muchos enfoques centrales buscan romper). [6]
La memoria de la computadora suele describirse como de " acceso aleatorio ", pero los recorridos por software aún exhibirán patrones que pueden aprovecharse para lograr eficiencia. Existen varias herramientas para ayudar a los diseñadores de sistemas [7] y a los 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 los patrones de acceso a la memoria de la GPU [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]
El extremo más simple es el patrón de acceso secuencial , en el que los datos se leen, procesan y escriben con un direccionamiento incremental o decremental sencillo. Estos patrones de acceso son muy fáciles de precargar .
Los patrones de acceso 2D y 3D simples o escalonados (por ejemplo, el 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 de bucles es un enfoque eficaz. [19] Algunos sistemas con DMA proporcionaron un modo escalonado para transferir datos entre submosaicos de matrices 2D más grandes y la memoria de borrador . [20]
Un patrón de acceso lineal está estrechamente relacionado con el "acceso por pasos", en el que una dirección de memoria puede calcularse a partir de una combinación lineal de algún índice. El paso a paso por los índices secuencialmente con un patrón lineal produce un acceso por pasos . Un patrón de acceso lineal para escrituras (con cualquier patrón de acceso para lecturas no superpuestas) puede garantizar que un algoritmo pueda paralelizarse, lo que se aprovecha en sistemas que admiten núcleos de cómputo .
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 de pasos. Un algoritmo puede recorrer 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 cuadrículas. [21] El vecino más cercano también puede referirse a la comunicación entre nodos en un clúster; las simulaciones de física que dependen de dichos patrones de acceso local se pueden paralelizar con los datos divididos en nodos del clúster, con una comunicación puramente de vecino más cercano entre ellos, lo que puede tener ventajas para la latencia y el ancho de banda de la comunicación. Este caso de uso se corresponde bien con la topología de red de toros . [22]
En la representación 3D , los patrones de acceso para el mapeo de texturas y la rasterización de primitivos pequeños (con distorsiones arbitrarias de superficies complejas) están lejos de ser lineales, pero aún pueden exhibir localidad espacial (por ejemplo, en el espacio de pantalla o en 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 texturas y datos de búfer de cuadros (mapeo de regiones espaciales en líneas de caché), o mediante la clasificación de primitivos a través de una representación diferida basada en mosaicos . [24] También puede ser ventajoso almacenar matrices en orden Morton en bibliotecas de álgebra lineal . [25]
Un patrón de acceso a memoria dispersa 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 "disparar y olvidar" (omitiendo un caché por completo), mientras usa prefetching predecible (o incluso DMA) para sus datos de origen.
Sin embargo, puede ser más difícil 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 un caché de hardware fusionará muchas escrituras pequeñas en otras más grandes.
En el pasado, el mapeo de textura hacia adelante intentaba manejar la aleatoriedad con "escrituras", mientras leía secuencialmente la información de textura de origen.
La consola PlayStation 2 utilizaba un mapeo de textura inverso convencional, pero manejaba cualquier procesamiento de dispersión/recolección "en el chip" utilizando EDRAM, mientras que el modelo 3D (y una gran cantidad de datos de textura) de la memoria principal se alimentaba secuencialmente mediante DMA. Por eso carecía de soporte para primitivas indexadas y, a veces, necesitaba administrar texturas "por adelantado" en la lista de visualización .
En un patrón de acceso a memoria de recopilación , 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 inverso , donde los datos se pueden escribir linealmente a través de líneas de escaneo , mientras que las direcciones de textura de acceso aleatorio se calculan por píxel .
En comparación con el método scatter, la desventaja es que el almacenamiento en caché (y la omisión de latencias) ahora es esencial para lecturas eficientes de elementos pequeños, sin embargo, es más fácil 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 gpgpu , [27] donde el subprocesamiento masivo (habilitado por el paralelismo) se utiliza para ocultar las latencias de lectura. [27]
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 otros lugares. Esta es esencialmente la operación completa de una tubería de GPU al realizar renderizado 3D : recopilar vértices indexados y texturas y dispersar píxeles sombreados en el espacio de la pantalla . La rasterización de primitivas opacas mediante un búfer de profundidad es "conmutativa", lo que permite la reordenación, lo que facilita la ejecución en paralelo. En el caso general, se necesitarían primitivas de sincronización.
En el extremo opuesto se encuentra un patrón de acceso a memoria verdaderamente aleatorio. Unos pocos sistemas multiprocesador están especializados para lidiar con estos. [28] El enfoque PGAS puede ayudar al ordenar las operaciones por datos sobre la marcha (útil cuando el problema *es* averiguar la localidad de datos no ordenados). [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 ordenación a veces puede ayudar. Dado un patrón de acceso a memoria verdaderamente aleatorio, puede ser posible descomponerlo (incluyendo etapas de dispersión o recopilación u otra ordenación intermedia) que puede mejorar la localidad en general; esto es a menudo un prerrequisito para la paralelización .
El diseño orientado a datos es un enfoque destinado a maximizar la localidad de referencia, organizando los datos de acuerdo a cómo se recorren en varias etapas de un programa, en contraste con el enfoque orientado a objetos más común (es decir, organizar de manera que el diseño de los datos refleje explícitamente el patrón de acceso). [29]
La localidad de referencia se refiere a una propiedad que exhiben los patrones de acceso a la memoria. Un programador cambiará el patrón de acceso a la memoria (mediante la reelaboración de algoritmos) para mejorar la localidad de referencia, [30] y/o para aumentar el potencial de paralelismo. [26] Un programador o diseñador de sistemas puede crear marcos o abstracciones (por ejemplo, plantillas de C++ o funciones de orden superior ) que encapsulen un patrón de acceso a la memoria específico. [31] [32]
En el paralelismo, más allá de la localidad de referencia, aparecen diferentes consideraciones para los patrones de acceso a la memoria, 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, que puede parecer inicialmente peor en términos de localidad pura, pero es 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 ).
{{cite journal}}: Requiere citar revista |journal=( ayuda )En la práctica, los patrones de acceso de E/S son tan numerosos como las estrellas.