AoS and SoA

From Wikipedia, the free encyclopedia
  (Redirected from AOS and SOA)
Jump to navigation Jump to search

In computing, Array of Structures (AoS), Structure of Arrays (SoA) and Array of Structures of Arrays (AoSoA) refer to contrasting ways to arrange a sequence of records in memory, with regard to interleaving, and are of interest in SIMD and SIMT programming.

Structure of Arrays[edit]

Structure of arrays (or SoA) is a layout separating elements of a record (or 'struct' in the C programming language) into one parallel array per field[1]. The motivation is easier manipulation with packed SIMD instructions in most instruction set architectures, since a single SIMD register can load homogeneous data, possibly transferred by a wide internal datapath (e.g. 128-bit). If only a specific part of the record is needed, only those parts need to be iterated over, allowing more data to fit onto a single cache line. The downside is requiring more cache ways when traversing data, and inefficient indexed addressing (see also: planar image format).

For example, to store N points in 3D space using a Structure of Arrays:

1 struct pointlist3D {
2     float x[N];
3     float y[N];
4     float z[N];
5 };
6 struct pointlist3D points;
7 float get_point_x(int i) { return points.x[i]; }

Array of Structures[edit]

Array of structures (or AoS) is the opposite (and more conventional) layout, in which data for different fields is interleaved. This is often more intuitive, and supported directly by most programming languages.

For example, to store N points in 3D space using an Array of Structures:

1 struct point3D {
2     float x;
3     float y;
4     float z;
5 };
6 struct point3D points[N];
7 float get_point_x(int i) { return points[i].x; }

Array of Structures of Arrays[edit]

Array of Structures of Arrays (or AoSoA) is a hybrid approach between the previous layouts, in which data for different fields is interleaved using tiles or blocks with size equal to the SIMD vector size. This is often less intuitive, but can achieve the memory throughput of the SoA approach, while being more friendly to the cache locality and load port architectures of modern processors[2].

For example, to store N points in 3D space using an Array of Structures of Arrays with a SIMD register width of 8:

1 struct point3Dx8 {
2     float x[8];
3     float y[8];
4     float z[8];
5 };
6 struct point3Dx8 points[(N+7)/8];
7 float get_point_x(int i) { return points[i/8].x[i%8]; }

Alternatives[edit]

It is possible to split some subset of a structure (rather than each individual field) into a parallel array – this can actually improve locality of reference if different pieces of fields are used at different times in the program (see data oriented design).

Some SIMD architectures provide strided load/store instructions to load homogeneous data from SoA format. Yet another option used in some Cell libraries is to de-interleave data from AoS format when loading sources into registers, and interleave when writing out results (facilitated by superscalar issue of permutes). Some vector maths libraries align floating point 4D vectors with the SIMD register to leverage the associated data path and instructions, whilst still providing programmer convenience, although this does not scale to SIMD units wider than four lanes.

4D vectors[edit]

AoS vs SoA presents a choice when considering 3D or 4D vector data on machines with 4-lane SIMD hardware. SIMD ISAs are usually designed for homogeneous data, however some provide a dot product instruction[3] and additional permutes making the AoS case easier to handle. Although most GPU hardware has moved away from 4D instructions to scalar SIMT pipelines,[4] modern compute kernels using SoA can still give better performance due to memory coalescing [5].

Software support[edit]

Most languages support the AoS format more naturally by combining records and various array abstract data types. The experimental JAI programming language is a recent attempt to provide language level SoA support.[6] Julia language, supports multi-dimensional arrays, with AoS, or SoA (through a package). The Datadraw code generator creates SoA data structures for the C language.

References[edit]

  1. ^ "How to Manipulate Data Structure to Optimize Memory Use". Intel. 2012-02-09. Retrieved 2019-03-17.
  2. ^ "Memory Layout Transformations". Intel. 2019-03-26. Retrieved 2019-06-02.
  3. ^ "Intel SSE4 Floating Point Dot Product Intrinsics". Intel. Retrieved 2019-03-17.
  4. ^ "Modern GPU Architecture (See Scalar Unified Pipelines)" (PDF). NVIDIA. Retrieved 2019-03-17.
  5. ^ Kim, Hyesoon (2010-02-08). "CUDA Optimization Strategies" (PDF). CS4803 Design Game Consoles. Retrieved 2019-03-17.
  6. ^ Blow, Jonathan (2015-01-21). "Data oriented demo: SoA, composition". Retrieved 2019-03-17. Demonstration of data-oriented and SoA features in the JAI language, also explaining the motivation.