AoS и SoA

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

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

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

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

struct pointlist3D {
    float x[N];
    float y[N];
    float z[N];
};
struct pointlist3D points;
float get_point_x(int i) { return points.x[i]; }

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

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

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

struct point3D {
    float x;
    float y;
    float z;
};
struct point3D points[N];
float get_point_x(int i) { return points[i].x; }

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

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

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

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]; }

В зависимости от фактической ширины регистра 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]