AoS i SoA

W informatyce tablica struktur (AoS) , struktura tablic (SoA) i tablica struktur tablic (AoSoA) odnoszą się do kontrastujących sposobów porządkowania sekwencji rekordów w pamięci , w odniesieniu do przeplatania , i są interesujące w SIMD i programowanie SIMT .

Struktura tablic

Struktura tablic ( SoA ) to układ rozdzielający elementy rekordu ( lub „struktury” w języku programowania C ) na jedną tablicę równoległą na pole . Motywacją jest łatwiejsza manipulacja upakowanymi instrukcjami SIMD w większości architektur zestawów instrukcji , ponieważ pojedynczy rejestr SIMD może załadować jednorodne dane, prawdopodobnie przesyłane przez szeroką wewnętrzną ścieżkę danych (np. 128-bitową ). Jeśli potrzebna jest tylko określona część rekordu, tylko te części muszą zostać powtórzone, dzięki czemu więcej danych zmieści się w jednej linii pamięci podręcznej. Wadą jest konieczność korzystania z większej liczby pamięci podręcznych podczas przechodzenia przez dane oraz nieefektywne adresowanie indeksowane .

Na przykład, aby zapisać N punktów w przestrzeni 3D przy użyciu struktury tablic:

  
     
     
     

  
       struct  pointlist3D  {  float  x  [  N  ];  liczba zmiennoprzecinkowa  y  [  N  ];  liczba zmiennoprzecinkowa  z  [  N  ];  };  struct  pointlistpunkty  3D  ;  float  get_point_x  (  int  i  )  {  punkty  zwrotne  .  x  [  ja  ];  }

Tablica struktur

Tablica struktur ( AoS ) jest odwrotnym (i bardziej konwencjonalnym) układem, w którym przeplatane są dane dla różnych pól. Jest to często bardziej intuicyjne i obsługiwane bezpośrednio przez większość języków programowania .

Na przykład, aby zapisać N punktów w przestrzeni 3D za pomocą tablicy struktur:

  
     
     
     

  
       struct  point3D  {  float  x  ;  pływak  y  ;  liczba zmiennoprzecinkowa  z  ;  };  struct  point3D  points  [  N  ];  float  get_point_x  (  int  ja  )  {  punkty  zwrotu  [  i  ].  x  ;  }

Tablica struktur tablic

Tablica struktur tablic ( AoSoA ) lub kafelkowa tablica struktur to podejście hybrydowe pomiędzy poprzednimi układami, w którym dane dla różnych pól są przeplatane za pomocą kafelków lub bloków o rozmiarze równym rozmiarowi wektora SIMD. Jest to często mniej intuicyjne, ale może osiągnąć przepustowość pamięci charakterystyczną dla podejścia SoA, będąc jednocześnie bardziej przyjaznym dla lokalizacji pamięci podręcznej i architektur portów ładowania nowoczesnych procesorów. W szczególności żądania pamięci w nowoczesnych procesorach muszą być realizowane w stałej szerokości (np. rozmiar pamięci podręcznej). Przechowywanie kafelkowe AoSoA dopasowuje wzorzec dostępu do pamięci do stałej szerokości żądań, co prowadzi do mniejszej liczby operacji dostępu do wykonania żądania pamięci, a tym samym zwiększa wydajność.

Na przykład, aby przechowywać N punktów w przestrzeni 3D przy użyciu tablicy struktur tablic o szerokości rejestru SIMD wynoszącej 8 zmiennoprzecinkowych (lub 8 × 32 = 256 bitów):

  
     
     
     

  
       struct  point3Dx8  {  float  x  [  8  ];  pływak  y  [  8  ];  liczba zmiennoprzecinkowa  z  [  8  ];  };  struct  point3Dx8  points  [(  N  +  7  )  /  8  ];  float  get_point_x  (  int  ja  )  {  punkty  zwrotu  [  i  /  8  ].  x  [  i  %  8  ];  }

W zależności od rzeczywistej szerokości rejestru SIMD może być potrzebna inna szerokość. Tablice wewnętrzne można zastąpić typami SIMD, takimi jak float32x8 dla języków z taką obsługą.

Alternatywy

Możliwe jest podzielenie pewnego podzbioru struktury (zamiast każdego pojedynczego pola) na tablicę równoległą - i może to faktycznie poprawić lokalizację odniesienia , jeśli różne części pól są używane w różnych momentach programu (patrz projektowanie zorientowane na dane ).

Niektóre architektury SIMD zapewniają krokowe instrukcje ładowania/przechowywania w celu załadowania jednorodnych danych z formatu SoA. Jeszcze inną opcją używaną w niektórych Cell jest usuwanie przeplotu danych z formatu AoS podczas ładowania źródeł do rejestrów i przeplatanie podczas zapisywania wyników (ułatwione przez superskalarny problem permutów ) . Niektóre biblioteki matematyki wektorowej dopasowują wektory zmiennoprzecinkowe 4D do rejestru SIMD, aby wykorzystać powiązaną ścieżkę danych i instrukcje, jednocześnie zapewniając wygodę programistom, chociaż nie jest to skalowane do jednostek SIMD szerszych niż cztery pasy.

wektory 4D

AoS vs. SoA stanowi wybór przy rozważaniu danych wektorowych 3D lub 4D na maszynach z czteropasmowym sprzętem SIMD. SIMD ISA są zwykle zaprojektowane dla jednorodnych danych, jednak niektóre zapewniają iloczynu skalarnego i dodatkowe permutacje, dzięki czemu obsługa AoS jest łatwiejsza.

Chociaż większość sprzętu GPU odeszła od instrukcji 4D do skalarnych potoków SIMT , nowoczesne jądra obliczeniowe wykorzystujące SoA zamiast AoS mogą nadal zapewniać lepszą wydajność dzięki koalescencji pamięci.

Wsparcie oprogramowania

Większość języków obsługuje format AoS w bardziej naturalny sposób, łącząc rekordy i różne abstrakcyjne typy danych tablicowych .

SoA występuje głównie w językach, bibliotekach lub narzędziach metaprogramowania używanych do obsługi projektów zorientowanych na dane . Przykłady obejmują:

Zorientowane na SIMD funkcje eksperymentalnego języka programowania Jai to ostatnia próba zapewnienia obsługi SoA na poziomie języka.
„Ramki danych”, zaimplementowane w R , pakiecie Pandas Pythona i pakiecie DataFrames.jl Julii , to interfejsy umożliwiające dostęp do SoA, takich jak AoS.
Pakiet Julia StructArrays.jl umożliwia dostęp do SoA jako AoS, łącząc wydajność SoA z intuicyjnością AoS.
Generatory kodu dla języka C, w tym Datadraw i technika X Macro .

Automatyczne tworzenie AoSoA jest bardziej złożone. Przykład AoSoA w metaprogramowaniu można znaleźć w bibliotece LANL Cabana napisanej w C++ ; domyślnie przyjmuje szerokość wektora 16 pasów.