AoS и SoA

В вычислительной технике массив структур (AoS) , структура массивов (SoA) или массив структур массивов (AoSoA) представляют собой противоположные способы упорядочить последовательность записей в памяти с учетом чередования и представляют интерес для SIMD и SIMT- программирование.

Структура массивов

Структура массивов ( SoA ) — это макет, разделяющий элементы записи ( или «структуры» на языке программирования C ) на один параллельный массив для каждого поля . ^[1] Мотивацией является более легкое манипулирование упакованными инструкциями SIMD в большинстве архитектур набора команд , поскольку один регистр SIMD может загружать однородные данные , возможно, передаваемые по широкому внутреннему каналу данных (например, 128-битному ). Если требуется только определенная часть записи, необходимо выполнить итерацию только по этим частям, что позволяет разместить больше данных в одной строке кэша. Обратной стороной является необходимость большего количества способов кэширования при перемещении данных и неэффективная индексированная адресация .

Например, чтобы сохранить N точек в трехмерном пространстве, используя структуру массивов:

struct   pointlist3D   {      float   x  [  N  ];      плавать   y  [  N  ];      плавать   z  [  Н  ];  };  структура   pointlist3D   точки  ;  float   get_point_x  (  int   i  )   {   возврата   точки  .  х  [  я  ];   }

Массив структур

Массив структур ( AoS ) — это противоположный (и более традиционный) макет, в котором данные для разных полей чередуются. Зачастую это более интуитивно понятно и напрямую поддерживается большинством языков программирования .

Например, чтобы сохранить N точек в 3D-пространстве с помощью массива структур:

структура   point3D   {      float   x  ;      плавать   у  ;      плавать   z  ;  };  struct   point3D   точек  [  N  ];  float   get_point_x  (  int   i  )   {   возврата   точки  [  i  ].  х  ;   }

Массив структур массивов

Массив структур массивов ( AoSoA ) или мозаичный массив структур — это гибридный подход между предыдущими макетами, в котором данные для разных полей чередуются с использованием тайлов или блоков с размером, равным размеру вектора SIMD. Зачастую это менее интуитивно понятно, но позволяет достичь пропускной способности памяти, сравнимой с подходом SoA, при этом более дружелюбным к локальности кэша и архитектуре портов загрузки современных процессоров. ^[2] В частности, запросы к памяти в современных процессорах должны выполняться с фиксированной шириной (например, размером строки кэша). ^[3]). Мозаичное хранилище AoSoA приводит шаблон доступа к памяти в соответствие с фиксированной шириной запросов, что приводит к меньшему количеству операций доступа для выполнения запроса к памяти и, таким образом, повышает эффективность. ^[4]

Например, для хранения N точек в 3D-пространстве с использованием массива структур массивов с шириной регистра SIMD 8 чисел с плавающей запятой (или 8×32 = 256 бит):

struct   point3Dx8   {      float   x  [  8  ];      плавать   y  [  8  ];      плавать   z  [  8  ];  };  struct   point3Dx8   точек  [(  N  +  7  )  /  8  ];  float   get_point_x  (  int   i  )   {   возврата   точки  [  i  /  8  ].  х  [  я  %  8  ];   }

В зависимости от фактической ширины регистра SIMD может потребоваться другая ширина. Внутренние массивы можно заменить типами SIMD, такими как float32x8 для языков с такой поддержкой.

Альтернативы

Можно разделить некоторое подмножество структуры (а не каждое отдельное поле) на параллельный массив – и это действительно может улучшить локальность ссылок , если разные части полей используются в разное время в программе (см. Data Oriented Design ).

Некоторые архитектуры SIMD предоставляют пошаговые инструкции загрузки/сохранения для загрузки однородных данных из формата SoA. Еще один вариант, используемый в некоторых библиотеках Cell , — это устранение чередования данных из формата AoS при загрузке источников в регистры и чередование при записи результатов (благодаря проблеме permutes суперскалярной ). Некоторые библиотеки векторной математики выравнивают 4D-векторы с плавающей запятой с регистром SIMD, чтобы использовать связанный путь данных и инструкции, обеспечивая при этом удобство программиста, хотя это не масштабируется для модулей SIMD шириной более четырех полос.

4D векторы

AoS или SoA представляют собой выбор при рассмотрении векторных данных 3D или 4D на машинах с четырехполосным оборудованием SIMD. SIMD ISA обычно разрабатываются для однородных данных, однако некоторые из них предоставляют скалярного произведения . инструкцию ^[5] и дополнительные перестановки, упрощающие обработку случая AoS.

Хотя большая часть аппаратного обеспечения графических процессоров перешла от 4D-инструкций к скалярным SIMT , конвейерам ^[6] современные вычислительные ядра, использующие SoA вместо AoS, по-прежнему могут обеспечивать более высокую производительность за счет объединения памяти. ^[7]

Поддержка программного обеспечения

Большинство языков поддерживают формат AoS более естественным образом, комбинируя записи и различные абстрактные типы данных массива .

SoA чаще всего встречается в языках, библиотеках или инструментах метапрограммирования , используемых для поддержки проектирования, ориентированного на данные . Примеры включают в себя:

«Кадры данных», реализованные в R , пакете Pandas Python и Julia , представляют собой интерфейсы для доступа к SoA, например AoS. пакете DataFrames.jl
Пакет Julia StructArrays.jl позволяет получить доступ к SoA как к AoS, чтобы объединить производительность SoA с интуитивностью AoS.
Генераторы кода для языка C, включая Datadraw и технику X Macro .

Автоматизированное создание AoSoA более сложное. Пример AoSoA в метапрограммировании можно найти в библиотеке Cabana компании LANL , написанной на C++; по умолчанию предполагается, что ширина вектора равна 16 полосам. ^[8]

Ссылки

^ «Как манипулировать структурой данных для оптимизации использования памяти» . Интел. 9 февраля 2012 г. Проверено 17 марта 2019 г.
^ «Преобразования структуры памяти» . Интел. 26 марта 2019 г. Проверено 2 июня 2019 г.
^ «Руководство по профилированию ядра» (PDF) . NVIDIA. 01.12.2022 . Проверено 14 января 2022 г. )
^ Фей, Юн (Раймонд); Хуан, Юхан; Гао, Мин (2021), «Принципы моделирования метода материальных точек в реальном времени на современных графических процессорах», стр. 1–16, arXiv : 2111.00699 [ cs.GR ]
^ «Внутренняя часть скалярного произведения Intel SSE4 с плавающей запятой» . Интел. Архивировано из оригинала 24 июня 2016 г. Проверено 17 марта 2019 г.
^ «Современная архитектура графического процессора (см. Скалярные унифицированные конвейеры)» (PDF) . NVIDIA. Архивировано из оригинала (PDF) 17 мая 2018 г. Проверено 17 марта 2019 г.
^ Ким, Хесон (8 февраля 2010 г.). «Стратегии оптимизации CUDA» (PDF) . CS4803 Дизайн игровых консолей . Проверено 17 марта 2019 г.
^ «ECP-copa/Cabana: AoSoA» . Гитхаб .

[1] «Как манипулировать структурой данных для оптимизации использования памяти» . Интел. 9 февраля 2012 г. Проверено 17 марта 2019 г.

[2] «Преобразования структуры памяти» . Интел. 26 марта 2019 г. Проверено 2 июня 2019 г.

[3] «Руководство по профилированию ядра» (PDF) . NVIDIA. 01.12.2022 . Проверено 14 января 2022 г. )

[4] Фей, Юн (Раймонд); Хуан, Юхан; Гао, Мин (2021), «Принципы моделирования метода материальных точек в реальном времени на современных графических процессорах», стр. 1–16, arXiv : 2111.00699 [ cs.GR ]

[5] «Внутренняя часть скалярного произведения Intel SSE4 с плавающей запятой» . Интел. Архивировано из оригинала 24 июня 2016 г. Проверено 17 марта 2019 г.

[6] «Современная архитектура графического процессора (см. Скалярные унифицированные конвейеры)» (PDF) . NVIDIA. Архивировано из оригинала (PDF) 17 мая 2018 г. Проверено 17 марта 2019 г.

[7] Ким, Хесон (8 февраля 2010 г.). «Стратегии оптимизации CUDA» (PDF) . CS4803 Дизайн игровых консолей . Проверено 17 марта 2019 г.

[8] «ECP-copa/Cabana: AoSoA» . Гитхаб .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]