Массив структур (AoS) и структура массивов (SoA) при случайном чтении для векторизации

Question

Массив структур (AoS) и структура массивов (SoA) при случайном чтении для векторизации

Мой вопрос касается следующей фразы из книги:

К сожалению, форма SoA не идеальна при любых обстоятельствах. За
случайные или несвязные обстоятельства, сборы используются для доступа к
данные и форма SoA могут привести к чтению лишних ненужных данных
в кэш, тем самым снижая производительность. В этом случае использование AoS
форма вместо этого приведет к уменьшению рабочего набора и улучшению
спектакль. Как правило, однако, если вычисление должно быть
Векторизованная форма SoA является предпочтительной.

мой Угадай Причины, по которым AoS может привести к лучшей производительности, — это когда разные или лучше все поля в одной структуре участвуют в одном прогоне векторизации.

Пример (просто концепция, без конкретного или рабочего кода вообще):

/*Note that the types of data I maintain the same intentionally,
to simplify discussion*/
struct Data {
float mean;
float distribution[10]
}

и определить массив тех, кто получил случайным образом из какого-то источника данных

Data aos[5];

Теперь, если во время цикла векторизации я делаю что-то вроде:

float* dataPtr =  &(aos[0].mean);

#pragma simd
for(int i=0; i< 60; i++)
{
const float mean = (*dataPtr);
/*do something with mean */

dataPtr++;

/*do something with distribution */
}

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

Правильно ли мое предположение или есть что-то еще?

5

c++cpu-cache parallel-processing vectorization

Решение

Другие решения

Да, вы, кажется, понимаете ситуацию.

Если вы читаете несколько значений из одной и той же структуры, то ЦПУ потребуется только выбрать столько строк кэша, сколько ему нужно для этих элементов структуры — возможно, только одно, если элементы структуры хорошо размечены. Так что кеш может выглядеть так (где v значения, которые вы хотите, и пустые слоты являются другими значениями)

line 1: | v |   | v | v |   |   | v |   |

Если каждое из этих значений должно быть прочитано из отдельного массива, то для каждого значения потребуется извлечь целую строку кэша. Так что кеш может выглядеть так

line 1: |   |   | v |   |   |   |   |   |
line 2: |   |   |   |   | v |   |   |   |
line 3: |   | v |   |   |   |   |   |   |
line 4: |   |   | v |   |   |   |   |   |

Если вы работаете с массивом по порядку, то это хорошо — вам скоро понадобятся дополнительные значения, которые были извлечены.

Однако, если вы работаете не по порядку (по словам книги, вы находитесь в «случайных или непоследовательных обстоятельствах»), то выборка большего, чем вам нужно, каждый раз будет тратить место в кеше, и вы в конечном итоге будете использовать больше пропускной способности памяти, чем если бы необходимые значения были вместе в структуре.

1

Источник

Accepted Answer

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

Горизонтальное распараллеливание обрабатывает каждую полосу в вашем SIMD-блоке как отдельный «поток», работающий с различными данными. Вертикальное распараллеливание требует, чтобы весь модуль SIMD работал над одним и тем же объектом данных, пытаясь извлечь выгоду из его внутренней многомерности.

Чтобы привести конкретный пример: предположим, у вас есть 2 массива X а также Y 3D векторов, которые вы хотите добавить.

Горизонтальный подход: каждая полоса блока SIMD будет выполнять:

for(idx = 0; idx<size; idx+=SIMD_size) {
... = X[idx+laneid].x + Y[idx+laneid].x;
... = X[idx+laneid].y + Y[idx+laneid].y;
... = X[idx+laneid].z + Y[idx+laneid].z;
}

Вертикальный подход: каждая полоса блока SIMD занимает различный компонент так же вектор:
```
for(idx = 0; idx<size; idx+=1) {
... = X[idx].coord(laneid) + Y[idx].coord(laneid);
}
```

Вертикальный подход легче реализовать. Фактически, компиляторы уже пытаются автоматически векторизовать. Проблема заключается в том, что, поскольку ширина SIMD-блока растет, реализация не может извлечь из этого пользу. Если вы переключаетесь с SIMD шириной от 4 до 16, вы все равно добавляете только 3 числа параллельно вашему трехмерному вектору.

Горизонтальный подход сложнее. Обычно вам приходится обрабатывать расходящиеся ветви, вызовы функций и т. Д. И — вы хотите реорганизовать свои данные в структуру массивов — так, чтобы соответствующие поля вашего другого объекта данных находились рядом в памяти.

Теперь вернемся к вашему вопросу: SoA имеет смысл только если вы делаете горизонтальное распараллеливание. Когда каждая дорожка имеет доступ к одному и тому же полю различного объекта, SoA позволяет заменить дорогостоящую инструкцию по сбору лучше выровненной одиночной выборкой из памяти.
Если вы попытаетесь сделать вертикальный, как в вашем примере в вопросе — никто бы даже не подумал сделать SoA в первую очередь — доступ к нескольким полям одного и того же объекта вызовет «сбор».

Однако при произвольном доступе SoA может оказаться не лучшим вариантом, даже если вы выполняете горизонтальное распараллеливание. Во-первых, вы не получаете выгоды от использования SoA, потому что вам все равно нужно делать дорогостоящий сбор. Однако, поскольку ваши поля одного и того же объекта распределены по памяти, каждая загрузка будет попадать на разные дорожки кэша. Это не только увеличивает использование пропускной способности памяти, но и может привести к перегрузке кеша.
Вот почему SoA не так эффективны с произвольным доступом.

Лучшее решение — использовать гибридный подход: вы упаковываете свои данные в массив структур из массивов SIMD с размером. Но это уже другая история…

8