AoS и SoA

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

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

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

структура pointlist3D {   плавающий x [ N ];  плавающий y [ N ];  плавающий z [ N ]; };struct pointlist3D точки ;  float get_point_x ( int i ) { return points . x [ i ]; }      

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

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

структура point3D {   плавающий x ;  плавающий y ;  плавающий z ; };struct point3D точки [ N ];  float get_point_x ( int i ) { return points [ i ]. x ; }      

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

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

структура point3Dx8 {   плавающий x [ 8 ];  плавающий у [ 8 ];  плавающий z [ 8 ]; };структура point3Dx8 точек [( N + 7 ) / 8 ];  float get_point_x ( int i ) { return points [ i / 8 ]. x [ i % 8 ]; }      

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

Этот раздел, возможно, содержит оригинальные исследования . Пожалуйста, улучшите его, проверив сделанные заявления и добавив встроенные цитаты . Заявления, состоящие только из оригинальных исследований, должны быть удалены. ( Август 2019 ) ( Узнайте, как и когда удалять это сообщение )

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

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

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

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

Для проверки этой статьи нужны дополнительные цитаты . Помогите улучшить эту статью , добавив ссылки на надежные источники . Материалы без источников могут быть оспорены и удалены. Найти источники:  «AoS и SoA» – новости  · газеты  · книги  · ученый  · JSTOR ( июль 2023 г. ) ( Узнайте, как и когда удалять это сообщение )

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

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

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

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