En informática , Array of Structures (AoS) , Structure of Arrays (SoA) y Array of Structures of Arrays (AoSoA) se refieren a formas contrastantes de organizar una secuencia de registros en la memoria , con respecto al entrelazado , y son de interés en SIMD y Programación SIMT .
Estructura de matrices
La estructura de matrices ( SoA ) es un diseño que separa los elementos de un registro (o 'estructura' en el lenguaje de programación C ) en una matriz paralela por campo . [1] La motivación es una manipulación más fácil con instrucciones SIMD empaquetadas en la mayoría de las arquitecturas de conjuntos de instrucciones , ya que un solo registro SIMD puede cargar datos homogéneos , posiblemente transferidos por una amplia ruta de datos interna (por ejemplo, 128 bits ). Si solo se necesita una parte específica del registro, solo se deben iterar esas partes, lo que permite que más datos quepan en una sola línea de caché. La desventaja es que se requieren más formas de caché al atravesar datos y un direccionamiento indexado ineficiente .
Por ejemplo, para almacenar N puntos en el espacio 3D usando una estructura de matrices:
struct pointlist3D { flotar x [ N ]; flotar y [ N ]; flotar z [ N ];};estructura pointlist3D puntos ;float get_point_x ( int i ) { puntos de retorno . x [ i ]; }
Matriz de estructuras
La matriz de estructuras ( AoS ) es el diseño opuesto (y más convencional), en el que se intercalan datos para diferentes campos. A menudo, esto es más intuitivo y es compatible directamente con la mayoría de los lenguajes de programación .
Por ejemplo, para almacenar N puntos en el espacio 3D usando una matriz de estructuras:
struct point3D { flotar x ; flotar y ; flotar z ;};estructura point3D puntos [ N ];float get_point_x ( int i ) { puntos de retorno [ i ]. x ; }
Matriz de estructuras de matrices
Array of Structures of Arrays ( AoSoA ) o Tiled Array of Structs es un enfoque híbrido entre los diseños anteriores, en el que los datos para diferentes campos se intercalan utilizando mosaicos o bloques con un tamaño igual al tamaño del vector SIMD. Esto a menudo es menos intuitivo, pero puede lograr el rendimiento de memoria del enfoque SoA, al mismo tiempo que es más amigable con la localidad de caché y las arquitecturas de puertos de carga de los procesadores modernos. [2]
Por ejemplo, para almacenar N puntos en el espacio 3D usando una matriz de estructuras de matrices con un ancho de registro SIMD de 8 flotadores (u 8 × 32 = 256 bits):
struct point3Dx8 { flotar x [ 8 ]; flotar y [ 8 ]; flotar z [ 8 ];};struct point3Dx8 puntos [( N + 7 ) / 8 ];float get_point_x ( int i ) { puntos de retorno [ i / 8 ]. x [ i % 8 ]; }
Puede ser necesario un ancho diferente dependiendo del ancho real del registro SIMD. Las matrices interiores pueden reemplazarse con tipos SIMD, como float32x8
para idiomas con dicho soporte.
Alternativas
Es posible dividir algún subconjunto de una estructura (en lugar de cada campo individual) en una matriz paralela , y esto realmente puede mejorar la localidad de referencia si se usan diferentes partes de campos en diferentes momentos en el programa (ver diseño orientado a datos ).
Algunas arquitecturas SIMD proporcionan instrucciones de carga / almacenamiento escalonadas para cargar datos homogéneos desde el formato SoA. Otra opción más utilizada en algunas bibliotecas de Cell es desintercalar datos del formato AoS cuando se cargan fuentes en registros e intercalar cuando se escriben los resultados (facilitado por el problema superescalar de las permutaciones ). Algunas bibliotecas de matemáticas vectoriales alinean los vectores 4D de punto flotante con el registro SIMD para aprovechar la ruta de datos y las instrucciones asociadas, al tiempo que brindan comodidad al programador, aunque esto no se escala a unidades SIMD de más de cuatro carriles.
Vectores 4D
AoS vs. SoA presenta una opción cuando se consideran datos vectoriales 3D o 4D en máquinas con hardware SIMD de cuatro carriles. Los ISA de SIMD generalmente están diseñados para datos homogéneos, sin embargo, algunos proporcionan una instrucción de producto de puntos [3] y permutaciones adicionales, lo que hace que el caso de AoS sea más fácil de manejar.
Aunque la mayoría del hardware de la GPU se ha alejado de las instrucciones 4D a las canalizaciones SIMT escalares , [4] los núcleos informáticos modernos que utilizan SoA en lugar de AoS aún pueden ofrecer un mejor rendimiento debido a la unión de la memoria. [5]
Soporte de software
La mayoría de los lenguajes admiten el formato AoS de forma más natural al combinar registros y varios tipos de datos abstractos de matriz .
SoA se encuentra principalmente en lenguajes, bibliotecas o herramientas de metaprogramación que se utilizan para respaldar un diseño orientado a datos . Ejemplos incluyen:
- Las características orientadas a SIMD del lenguaje de programación experimental Jai son un intento reciente de proporcionar soporte SoA a nivel de lenguaje. [6]
- Los "marcos de datos" de R y Python's NumPy y Pandas, Julia 's
StructsOfArrays.jl
son ejemplos de interfaces para acceder a SoA como AoS; - Generadores de código para el lenguaje C, incluidos Datadraw y la técnica X Macro .
La creación automatizada de AoSoA es más compleja. Un ejemplo de AoSoA en metaprogramación se encuentra en la biblioteca Cabana de LANL escrita en C ++; asume un ancho de vector de 16 carriles por defecto. [7]
Referencias
- ^ "Cómo manipular la estructura de datos para optimizar el uso de la memoria" . Intel. 2012-02-09 . Consultado el 17 de marzo de 2019 .
- ^ "Transformaciones de diseño de memoria" . Intel. 2019-03-26 . Consultado el 2 de junio de 2019 .
- ^ "Intrínsecos del producto de punto flotante Intel SSE4" . Intel. Archivado desde el original el 24 de junio de 2016 . Consultado el 17 de marzo de 2019 .
- ^ "Arquitectura de GPU moderna (ver canalizaciones unificadas escalares)" (PDF) . NVIDIA. Archivado desde el original (PDF) el 17 de mayo de 2018 . Consultado el 17 de marzo de 2019 .
- ^ Kim, Hyesoon (8 de febrero de 2010). "Estrategias de optimización CUDA" (PDF) . Consolas de juegos de diseño CS4803 . Consultado el 17 de marzo de 2019 .
- ^ Golpe, Jonathan (21 de enero de 2015). "Demostración orientada a datos: SoA, composición" . Consultado el 17 de marzo de 2019 . Demostración de características orientadas a datos y SoA en el lenguaje JAI, también explicando la motivación.
- ^ "ECP-copa / Cabana: AoSoA" . GitHub .