Hispanopedia Wiki
Articulo de referencia

Patrón de acceso a la memoria

En informática , un patrón de acceso a memoria o patrón de acceso de E/S es el patrón con el que un sistema o programa lee y escribe en la memoria de almacenamiento secundario ....

Hispanopedia WikiContenido en espanolLectura gratuita

En informática , un patrón de acceso a memoria o patrón de acceso de E/S es el patrón con el que un sistema o programa lee y escribe en la memoria de 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 sistemas de memoria compartida . [ 4 ] Además, los problemas de coherencia de caché pueden afectar el rendimiento de los multiprocesadores , [ 5 ] lo que significa que ciertos patrones de acceso a memoria imponen un límite al paralelismo (que los enfoques de muchos núcleos buscan superar). [ 6 ]

La memoria de la computadora se suele describir como de " acceso aleatorio ", pero los recorridos del software aún exhiben patrones que pueden ser explotados para mejorar la 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 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 ocultar la actividad de un programa por razones de privacidad . [ 16 ] [ 17 ]

Ejemplos

Algunas publicaciones representan erróneamente los patrones secuenciales y lineales como contrapartes entre sí; mientras que las cargas de trabajo del mundo real contienen innumerables patrones. [ 18 ]

Secuencial

El extremo más simple es el patrón de acceso secuencial , donde los datos se leen, procesan y escriben con un direccionamiento incremental/decremental directo. Estos patrones de acceso son muy adecuados para la precarga .

dio zancadas

Los patrones de acceso 3D, 2D con pasos o simples (por ejemplo, recorrer matrices multidimensionales ) son igualmente fáciles de predecir y se encuentran en implementaciones de algoritmos de álgebra lineal y procesamiento de imágenes . El teselado de bucles es un enfoque eficaz. [ 19 ] Algunos sistemas con DMA proporcionaron un modo con pasos para transferir datos entre submatrices de matrices 2D más grandes y memoria de acceso rápido . [ 20 ]

Lineal

Un patrón de acceso lineal está estrechamente relacionado con el acceso con paso, donde una dirección de memoria se puede calcular a partir de una combinación lineal de algún índice. Recorrer los índices secuencialmente con un patrón lineal produce un acceso con paso . Un patrón de acceso lineal para escrituras (con cualquier patrón de acceso para lecturas no superpuestas) puede garantizar que un algoritmo se pueda paralelizar, lo cual se aprovecha en sistemas que admiten núcleos de cómputo .

vecino más cercano

Los patrones de acceso a memoria del vecino más cercano aparecen en las simulaciones y están relacionados con patrones secuenciales o con 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 simulaciones físicas 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 físicas que dependen de tales patrones de acceso local pueden paralelizarse con los datos particionados en nodos de clúster, con comunicación puramente de vecino más cercano entre ellos, lo que puede tener ventajas en cuanto a latencia y ancho de banda de comunicación. Este caso de uso se adapta bien a la topología de red de toro . [ 22 ]

2D espacialmente coherente

En la renderización 3D , los patrones de acceso para el mapeo de texturas y la rasterización de primitivas pequeñas (con distorsiones arbitrarias de superficies complejas) distan mucho de ser lineales, pero aún pueden exhibir localidad espacial (por ejemplo, en el espacio de la pantalla o en el espacio de textura ). Esto se puede convertir en una buena localidad de memoria mediante alguna combinación de orden de Morton [ 23 ] y teselado para mapas de texturas y datos de búfer de fotogramas (mapeo de regiones espaciales en líneas de caché), o mediante la clasificación de primitivas mediante renderización diferida basada en teselas . [ 24 ] También puede ser ventajoso almacenar matrices en orden de Morton en bibliotecas de álgebra lineal . [ 25 ]

Dispersión

Un patrón de acceso a memoria disperso combina lecturas secuenciales con direccionamiento indexado/aleatorio para escrituras. [ 26 ] En comparación con el patrón de recolección, puede generar menos carga en una jerarquía de caché, ya que un elemento de procesamiento puede enviar escrituras de manera "disparar y olvidar" (omitiendo por completo la caché), mientras utiliza precarga predecible (o incluso DMA) para sus datos de origen.

Sin embargo, puede ser más difícil paralelizarlo ya que no hay garantía de que las escrituras no interactúen, [ 27 ] y muchos sistemas todavía se diseñan 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 leía secuencialmente la información de la textura de origen.

La consola PlayStation 2 utilizaba el mapeo inverso de texturas convencional, pero gestionaba el procesamiento de dispersión/recolección "en el chip" mediante EDRAM, mientras que el modelo 3D (y 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, en ocasiones, necesitaba gestionar las texturas "de antemano" en la lista de visualización .

Recolectar

En un patrón de acceso a memoria de recolecció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 texturas inversas , 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 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 superpongan. Por lo tanto, el enfoque de recolección es más común en la programación de GPGPU , [ 27 ] donde el encadenamiento masivo (habilitado por el paralelismo) se utiliza para ocultar las latencias de lectura. [ 27 ]

Recoger y dispersar combinados

Un algoritmo puede recopilar datos de una fuente, realizar cálculos en memoria local o en el chip, y distribuir los resultados en otro lugar. Este es, esencialmente, el funcionamiento completo de una canalización de GPU al realizar renderizado 3D : recopilar vértices y texturas indexados, y distribuir 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 y facilita la ejecución en paralelo. En el caso general, se necesitarían primitivas de sincronización.

Aleatorio

En el extremo opuesto se encuentra un patrón de acceso a memoria verdaderamente aleatorio. Algunos sistemas multiprocesador están especializados para manejar estos. [ 28 ] El enfoque PGAS puede ayudar ordenando las operaciones por datos sobre la marcha (útil cuando el problema es determinar la localidad de datos no ordenados). [ 21 ] Las estructuras de datos que dependen en gran medida del seguimiento 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 dividirlo (incluyendo etapas de dispersión o recolección, u otra ordenación intermedia) lo que puede mejorar la localidad general; esto suele ser un requisito previo para la paralelización .

Aproches

Diseño orientado a los datos

El diseño orientado a datos es un enfoque destinado a maximizar la localidad de referencia, organizando los datos según cómo se recorren en las distintas etapas de un programa, en contraste con el enfoque orientado a objetos más común (es decir, organizar de tal manera que la disposición de los datos refleje explícitamente el patrón de acceso). [ 1 ]

Contraste con la localidad de referencia

La localidad de referencia se refiere a una propiedad que exhiben los patrones de acceso a la memoria. Un programador modificará el patrón de acceso a la memoria (reelaborando algoritmos) para mejorar la localidad de referencia [ 29 ] 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 [ 30 ] [ 31 ] .

En el paralelismo, surgen consideraciones diferentes para los patrones de acceso a la memoria, más allá de la localidad de referencia, concretamente la separación de lecturas y escrituras. Por ejemplo: incluso si las lecturas y escrituras son "perfectamente" locales, puede resultar imposible paralelizarlas debido a las dependencias ; separar las lecturas y escrituras en áreas distintas genera un patrón de acceso a la memoria diferente, que puede parecer peor inicialmente 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 para 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 ).

Véase también

Referencias

  1. 1 2 "Introducción al diseño orientado a datos" (PDF) . Archivado del original (PDF) el 16 de noviembre de 2019.
  2. ↑ Jang, Byunghyun; Schaa, Dana; Mistry, Perhaad y Kaeli, David (27 de mayo de 2010). "Aprovechamiento de patrones de acceso a memoria para mejorar el rendimiento de la memoria en arquitecturas de datos paralelos". IEEE Transactions on Parallel and Distributed Systems . 22 (1). Nueva York: IEEE : 105–118 . doi : 10.1109/TPDS.2010.107 . eISSN 1558-2183 . ISSN 1045-9219 . S2CID 15997131. NLM unique id 101212014.   
  3. ↑ Jeffers, James; Reinders, James; Sodani, Avinash (31 de mayo de 2016). Programación de alto rendimiento del procesador Intel Xeon Phi: Edición Knights Landing (2.ª ed.). Morgan Kaufmann. ISBN  9780128091951.
  4. ↑ Jana, Siddhartha; Schuchart, Joseph; Chapman, Barbara (6 de octubre de 2014). «Análisis de la energía y el rendimiento de los patrones de acceso a datos basados ​​en PGAS» (PDF) . Actas de la 8.ª Conferencia Internacional sobre Modelos de Programación de Espacio de Direcciones Globales Particionados . PGAS '14. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 1-10 . doi : 10.1145/2676870.2676882 . ISBN  978-1-4503-3247-7.
  5. ↑ Marandola, Jussara; Louise, Stéphane; Cudennec, Loïc; Acquaviva, Jean-Thomas; Bader, David (11 de octubre de 2012). «Mejora de las arquitecturas coherentes de caché con patrones de acceso para sistemas multinúcleo embebidos» . Simposio Internacional de 2012 sobre Sistemas en Chip (SoC) (PDF) . IEEE. págs. 1–7 . doi : 10.1109/ISSoC.2012.6376369 . ISBN  978-1-4673-2896-8.
  6. ↑ "Intel Terascale" (PDF) .
  7. ↑ Brown, Mary; Jenevein, Roy M.; Ullah, Nasr (29 de noviembre de 1998). Análisis de patrones de acceso a la memoria . WWC '98: Actas de la Caracterización de la carga de trabajo: Metodología y estudios de caso (publicado el 29 de noviembre de 1998). pág. 105. ISBN  9780769504506.
  8. ↑ Ostadzadeh, S. Arash; Meeuws, Roel J.; Galuzzi, Carlo; Bertels, Koen (2010). "QUAD – Un analizador de patrones de acceso a memoria" (PDF) . En Sirisuk, Phaophak; Morgan, Fearghal; El-Ghazawi, Tarek; Amano, Hideharu (eds.). Computación reconfigurable: arquitecturas, herramientas y aplicaciones . Lecture Notes in Computer Science. Vol. 5992. Berlín, Heidelberg: Springer. pp. 269–281 . doi : 10.1007/978-3-642-12133-3_25 . ISBN   978-3-642-12133-3.
  9. ↑ Che, Shuai; Sheaffer, Jeremy W.; Skadron, Kevin (12 de noviembre de 2011). "Dymaxion: Optimización de patrones de acceso a memoria para sistemas heterogéneos" (PDF) . Actas de la Conferencia Internacional de 2011 sobre Computación de Alto Rendimiento, Redes, Almacenamiento y Análisis . SC '11. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 1–11 . doi : 10.1145/2063384.2063401 . ISBN  978-1-4503-0771-0.
  10. ↑ Harrison, Luddy (1996-01-01). «Examen de un esquema de clasificación de acceso a memoria para programas numéricos y con uso intensivo de punteros» . Actas de la 10.ª conferencia internacional sobre supercomputación - ICS '96 . Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 133–140 . doi : 10.1145/237578.237595 . ISBN  978-0-89791-803-9.
  11. ↑ Matsubara, Yuki; Sato, Yukinori (2014). "Análisis de patrones de acceso a memoria en línea en una herramienta de perfilado de aplicaciones". Segundo Simposio Internacional de Computación y Redes de 2014. págs. 602–604 . doi : 10.1109/CANDAR.2014.86 . ISBN  978-1-4799-4152-0. S2CID 16476418 . 
  12. ↑ "Organizando tus datos y código: Datos y diseño" .
  13. ↑ Kim, Yooseong; Shrivastava, Aviral (5 de junio de 2011). "CuMAPz: Una herramienta para analizar patrones de acceso a memoria en CUDA" . Actas de la 48.ª Conferencia de Automatización del Diseño . DAC '11. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 128–133 . doi : 10.1145/2024724.2024754 . ISBN  978-1-4503-0636-2.
  14. ↑ Kim, Yooseong; Shrivastava, Aviral (5 de junio de 2011). "CuMAPz: Una herramienta para analizar patrones de acceso a memoria en CUDA" . Actas de la 48.ª Conferencia de Automatización del Diseño . DAC '11. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 128–133 . doi : 10.1145/2024724.2024754 . ISBN  978-1-4503-0636-2.
  15. ^ Canteau, Anne; Lauradoux, Cédric; Seznec, André (2006). Comprender los ataques de caché (informe de tesis). INRIA. ISSN 0249-6399 . 
  16. ↑ Hardesty, Larry (2 de julio de 2013). "Protección de datos en la nube" . Noticias del MIT .
  17. ↑ Rossi, Ben (24-09-2013). "Mejorando la seguridad en la nube con RAM inconsciente" . Information Age .
  18. ↑ Chuck Paridon. "Directrices para la 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 de E/S son tan numerosos como las estrellas.
  19. ↑ Kennedy, Ken; McKinley, Kathryn S. (1992-08-01). "Optimizing for parallelism and data localidad" (PDF) . Actas de la 6.ª conferencia internacional sobre supercomputación - ICS '92 . Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 323–334 . doi : 10.1145/143369.143427 . ISBN  978-0-89791-485-7.
  20. ↑ Saidi, Selma; Tendulkar, P.; Lepley, Thierry; Maler, O. (2012). "Particionamiento óptimo de datos 2D para transferencias DMA en MPSoCs" (PDF) . 15.ª Conferencia Euromicro de 2012 sobre diseño de sistemas digitales . IEEE. págs. 584–591 . doi : 10.1109/DSD.2012.99 . ISBN  978-0-7695-4798-5.
  21. 1 2 CITRIS y el Instituto Banatao (05-09-2013). Programación de espacio de direcciones globales particionado - Kathy Yelick . Recuperado el 02-11-2024 – vía YouTube.Cubre casos en los que PGAS es una solución, donde los datos pueden no estar ordenados previamente, por ejemplo, al tratar con gráficos complejos; véase "la ciencia en todo el espectro de irregularidades".
  22. ↑ Weinberg, Jonathan; McCracken, Michael O.; Snavely, Allan; Strohmaier, Erich (12–18 de noviembre de 2005). «Cuantificación de la localidad en los patrones de acceso a la memoria de las aplicaciones HPC» (PDF) . Conferencia ACM/IEEE SC 2005 (SC'05) . Seattle, WA, EE. UU.: IEEE. pág. 50. doi : 10.1109/SC.2005.59 . ISBN  1-59593-061-2Archivado del original (PDF) el 3 de agosto de 2016.menciona los patrones de acceso del vecino más cercano en los clústeres.
  23. ↑ Hakura, Ziyad S.; Gupta, Anoop (1997-05-01). "Diseño y análisis de una arquitectura de caché para mapeo de texturas" (PDF) . Actas del 24.º simposio internacional anual sobre arquitectura de computadoras . ISCA '97. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 108–120 . doi : 10.1145/264107.264152 . ISBN  978-0-89791-901-2.
  24. ↑ Nocentino, Anthony E.; Rhodes, Philip J. (15 de abril de 2010). "Optimización del acceso a la memoria en GPU mediante indexación de orden Morton" (PDF) . Actas de la 48.ª Conferencia Regional Anual del Sudeste . ACMSE '10. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 1-4 . doi : 10.1145/1900008.1900035 . ISBN  978-1-4503-0064-3Archivado del original (PDF) el 8 de diciembre de 2022.
  25. ↑ Wise, David S.; Frens, Jeremy D. (1999). "Las matrices de orden Morton merecen el apoyo de los compiladores. Informe técnico 533". S2CID 17192354 . {{cite journal}}: Para citar una revista se requiere |journal=( ayuda )
  26. 1 2 3 4 Harris, Mark (abril de 2005). "GPU Gems 2" . 31.1.3 Comunicación de flujo: Recopilación vs. Dispersión. Archivado del original el 14 de junio de 2016. Recuperado el 13 de junio de 2016 .
  27. 1 2 3 Joyas de la GPU . Elsevier. 13 de enero de 2011. ISBN 9780123849892.En el texto se abordan los "patrones de acceso a memoria dispersos" y los "patrones de acceso a memoria agrupados".
  28. ↑ Wichmann, Nathan (2005). Cray y HPCC : Desarrollos de referencia y resultados del año pasado (PDF) . Actas de CUG 2005. Consulte los resultados de acceso aleatorio global para Cray X1. Arquitectura vectorial para ocultar latencias, no tan sensible a la coherencia de la caché.
  29. ↑ "optimizar-estructuras-de-datos-y-patrones-de-acceso-a-memoria-para-mejorar-la-localidad-de-los-datos" .
  30. ↑ "Motor de acceso a memoria basado en plantillas para aceleradores en SoC" (PDF) .
  31. ↑ "Vectorización multiobjetivo con la biblioteca genérica MTPS C++" (PDF) .una biblioteca de plantillas de C++ para producir patrones de acceso a memoria optimizados