AoS e SoA - AoS and SoA
In informatica , Array of Structures (AoS) , Structure of Arrays (SoA) e Array of Structures of Array (AoSoA) si riferiscono a modi contrastanti per organizzare una sequenza di record in memoria , per quanto riguarda l' interlacciamento , e sono di interesse in SIMD e Programmazione SIMT .
Struttura degli array
La struttura degli array ( SoA ) è un layout che separa gli elementi di un record (o 'struct' nel linguaggio di programmazione C ) in un array parallelo per campo . La motivazione è una manipolazione più semplice con istruzioni SIMD impacchettate nella maggior parte delle architetture di set di istruzioni , poiché un singolo registro SIMD può caricare dati omogenei , eventualmente trasferiti da un ampio datapath interno (ad esempio 128 bit ). Se è necessaria solo una parte specifica del record, solo quelle parti devono essere ripetute, consentendo a più dati di adattarsi a una singola linea di cache. Lo svantaggio è che richiedono più modalità di cache durante l'attraversamento dei dati e un indirizzamento indicizzato inefficiente .
Ad esempio, per memorizzare N punti nello spazio 3D utilizzando una struttura di matrici:
struct pointlist3D {
float x[N];
float y[N];
float z[N];
};
struct pointlist3D points;
float get_point_x(int i) { return points.x[i]; }
Matrice di strutture
L'array di strutture ( AoS ) è il layout opposto (e più convenzionale), in cui i dati per campi diversi sono intercalati. Questo è spesso più intuitivo e supportato direttamente dalla maggior parte dei linguaggi di programmazione .
Ad esempio, per memorizzare N punti nello spazio 3D utilizzando un array di strutture:
struct point3D {
float x;
float y;
float z;
};
struct point3D points[N];
float get_point_x(int i) { return points[i].x; }
Array di strutture di array
Array of Structures of Array ( AoSoA ) o Tiled Array of Structs è un approccio ibrido tra i layout precedenti, in cui i dati per campi diversi vengono interlacciati utilizzando tile o blocchi con dimensioni pari alla dimensione del vettore SIMD. Questo è spesso meno intuitivo, ma può raggiungere il throughput di memoria dell'approccio SoA, pur essendo più amichevole per la località della cache e le architetture delle porte di caricamento dei processori moderni.
Ad esempio, per memorizzare N punti nello spazio 3D utilizzando un array di strutture di array con una larghezza di registro SIMD di 8 float (o 8×32 = 256 bit):
struct point3Dx8 {
float x[8];
float y[8];
float z[8];
};
struct point3Dx8 points[(N+7)/8];
float get_point_x(int i) { return points[i/8].x[i%8]; }
Potrebbe essere necessaria una larghezza diversa a seconda della larghezza effettiva del registro SIMD. Gli array interni possono essere sostituiti con tipi SIMD come float32x8per le lingue con tale supporto.
alternative
È possibile dividere un sottoinsieme di una struttura (piuttosto che ogni singolo campo) in un array parallelo - e questo può effettivamente migliorare la località di riferimento se vengono utilizzati diversi pezzi di campi in momenti diversi nel programma (vedi progettazione orientata ai dati ).
Alcune architetture SIMD forniscono istruzioni di caricamento /memorizzazione a passi per caricare dati omogenei dal formato SoA. Ancora un'altra opzione utilizzata in alcune librerie Cell è quella di deinterlacciare i dati dal formato AoS quando si caricano le fonti nei registri e di interlacciare quando si scrivono i risultati (facilitato dal problema superscalare di permutes ). Alcune librerie di matematica vettoriale allineano i vettori 4D in virgola mobile con il registro SIMD per sfruttare il percorso e le istruzioni dei dati associati, pur fornendo la comodità del programmatore, sebbene ciò non si adatti alle unità SIMD più larghe di quattro corsie.
Vettori 4D
AoS vs. SoA rappresenta una scelta quando si considerano dati vettoriali 3D o 4D su macchine con hardware SIMD a quattro corsie. Gli ISA SIMD sono generalmente progettati per dati omogenei, tuttavia alcuni forniscono un'istruzione di prodotto standard e permute aggiuntive, rendendo il caso AoS più facile da gestire.
Sebbene la maggior parte dell'hardware GPU si sia spostata dalle istruzioni 4D alle pipeline SIMT scalari , i moderni kernel di elaborazione che utilizzano SoA anziché AoS possono ancora fornire prestazioni migliori grazie alla fusione della memoria.
Supporto software
La maggior parte dei linguaggi supporta il formato AoS in modo più naturale combinando record e vari tipi di dati astratti di array .
SoA si trova principalmente in linguaggi, librerie o strumenti di metaprogrammazione utilizzati per supportare un design orientato ai dati . Esempi inclusi:
- Le funzionalità orientate al SIMD del linguaggio di programmazione sperimentale Jai sono un recente tentativo di fornire supporto SoA a livello di linguaggio.
- I "frame di dati" di R e NumPy e Panda di Python, Julia s'
StructsOfArrays.jlsono esempi di interfacce per l'accesso SoA come AoS; - Generatori di codice per il linguaggio C, inclusi Datadraw e la tecnica X Macro .
La creazione automatizzata di AoSoA è più complessa. Un esempio di AoSoA nella metaprogrammazione si trova nella libreria Cabana di LANL scritta in C++; presuppone una larghezza vettoriale di 16 corsie per impostazione predefinita.
