En informática , una matriz de estructuras (AoS) , una estructura de matrices (SoA) o una matriz de estructuras de matrices (AoSoA) son formas contrastantes de organizar una secuencia de registros en la memoria , con respecto al entrelazado , y son de interés en la programación SIMD y SIMT .
La estructura de matrices ( SoA ) es un diseño que separa los elementos de un registro (o 'struct' 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 ruta de datos interna amplia (por ejemplo, 128 bits ). Si solo se necesita una parte específica del registro, solo se deben iterar esas partes, lo que permite que quepan más datos en una sola línea de caché. La desventaja es que se requieren más vías de caché al recorrer los datos y un direccionamiento indexado ineficiente .
Por ejemplo, para almacenar N puntos en el espacio 3D utilizando una estructura de matrices:
estructura listapuntos3D { flotar x [ N ]; flotar y [ N ]; flotar z [ N ]; };estructura pointlist3D puntos ; float get_point_x ( int i ) { return puntos.x [ i ] ; } La matriz de estructuras ( AoS ) es el diseño opuesto (y más convencional), en el que se intercalan los datos de los diferentes campos. Esto suele ser más intuitivo y la mayoría de los lenguajes de programación lo admiten directamente .
Por ejemplo, para almacenar N puntos en el espacio 3D utilizando una matriz de estructuras:
estructura punto3D { flotar x ; flotar y ; flotar z ; };estructura point3D puntos [ N ]; float get_point_x ( int i ) { devolver puntos [ i ] .x ; } La matriz de estructuras de matrices ( AoSoA ) o matriz de estructuras en mosaico es un enfoque híbrido entre los diseños anteriores, en el que los datos de diferentes campos se intercalan utilizando mosaicos o bloques con un tamaño igual al tamaño del vector SIMD. Esto suele ser 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 puerto de carga de los procesadores modernos. [2] En particular, las solicitudes de memoria en los procesadores modernos deben cumplirse en un ancho fijo (por ejemplo, el tamaño de una línea de caché [3] ). El almacenamiento en mosaico de AoSoA alinea el patrón de acceso a la memoria con el ancho fijo de las solicitudes, lo que genera menos operaciones de acceso para completar una solicitud de memoria y, por lo tanto, aumenta la eficiencia. [4]
Por ejemplo, para almacenar N puntos en el espacio 3D utilizando una matriz de estructuras de matrices con un ancho de registro SIMD de 8 flotantes (o 8×32 = 256 bits):
estructura punto3Dx8 { flotar x [ 8 ]; flotar y [ 8 ]; flotador z [ 8 ]; };struct point3Dx8 puntos [( N + 7 ) / 8 ]; float get_point_x ( int i ) { devuelve puntos [ i / 8 ] .x [ i % 8 ]; } Es posible que se necesite un ancho diferente según el ancho real del registro SIMD. Las matrices interiores se pueden reemplazar con tipos SIMD, como en float32x8el caso de los idiomas que admiten este tipo de datos.
Es posible dividir un subconjunto de una estructura (en lugar de cada campo individual) en una matriz paralela , y esto puede realmente mejorar la localidad de referencia si se utilizan diferentes partes de campos en diferentes momentos en el programa (ver diseño orientado a datos ).
Algunas arquitecturas SIMD proporcionan instrucciones de carga y almacenamiento en pasos para cargar datos homogéneos del formato SoA. Otra opción utilizada en algunas bibliotecas Cell es desentrelazar datos del formato AoS al cargar fuentes en registros e intercalarlos al escribir resultados (facilitado por el problema superescalar de las permutaciones ). Algunas bibliotecas de matemáticas vectoriales alinean vectores 4D de punto flotante con el registro SIMD para aprovechar la ruta de datos e instrucciones asociadas, al mismo tiempo que brindan comodidad al programador, aunque esto no se escala a unidades SIMD más anchas que cuatro carriles.
La comparación entre AoS y SoA presenta una elección al considerar datos vectoriales 3D o 4D en máquinas con hardware SIMD de cuatro carriles. Las ISA SIMD suelen estar diseñadas para datos homogéneos, sin embargo, algunas proporcionan una instrucción de producto escalar [5] 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 GPU se ha alejado de las instrucciones 4D hacia tuberías SIMT escalares , [6] los núcleos de cómputo modernos que usan SoA en lugar de AoS aún pueden brindar un mejor rendimiento debido a la fusión de memoria. [7]
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 . Algunos ejemplos incluyen:
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. [8]