Оптимизировать индексированный массив суммирования

Question

У меня есть следующий код C++:

const int N = 1000000 
int id[N]; //Value can range from 0 to 9 
float value[N]; 

// load id and value from an external source... 

int size[10] = { 0 }; 
float sum[10] = { 0 }; 
for (int i = 0; i < N; ++i) 
{ 
    ++size[id[i]]; 
    sum[id[i]] += value[i]; 
} 

Как следует оптимизировать цикл?

Я рассмотрел использование SSE для добавления каждого 4 поплавков к сумме, а затем после N итераций сумма представляет собой сумму из 4 поплавков в регистре xmm, но это не работает, когда источник индексируется следующим образом и необходимо записать в 10 разных массивов.

Answer 1

Этот вид петли очень трудно оптимизировать с помощью SIMD-инструкций. В большинстве наборов инструкций SIMD нет простого способа сделать этот тип индексированного чтения («собрать») или написать («разброс»), даже если бы он был, этот конкретный цикл по-прежнему имеет проблему, которая может возникнуть два значения, которые сопоставляются с одним и тем же id в одном регистре SIMD, например когда

id[0] == 0 
id[1] == 1 
id[2] == 2 
id[3] == 0 

в этом случае очевидный подход (псевдокод здесь)

x = gather(size, id[i]); 
y = gather(sum, id[i]); 
x += 1; // componentwise 
y += value[i]; 
scatter(x, size, id[i]); 
scatter(y, sum, id[i]); 

не будет работать!

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

Один из способов получить это несколько быстрее, без использования SIMD является разбивая зависимостей между командами немного с помощью разворачивая:

int size[10] = { 0 }, size2[10] = { 0 }; 
int sum[10] = { 0 }, sum2[10] = { 0 }; 
for (int i = 0; i < N/2; i++) { 
    int id0 = id[i*2+0], id1 = id[i*2+1]; 
    ++size[id0]; 
    ++size2[id1]; 
    sum[id0] += value[i*2+0]; 
    sum2[id1] += value[i*2+1]; 
} 

// if N was odd, process last element 
if (N & 1) { 
    ++size[id[N]]; 
    sum[id[N]] += value[N]; 
} 

// add partial sums together 
for (int i = 0; i < 10; i++) { 
    size[i] += size2[i]; 
    sum[i] += sum2[i]; 
} 

ли это помогает или нет, зависит от целевого процессора, хотя.

Answer 2

Ну, вы дважды вызываете id [i] в ​​свой цикл. Вы можете сохранить его в переменной или в регистре int, если хотите.

register int index; 
for(int i = 0; i < N; ++i) 
{ 
index = id[i]; 
++size[index]; 
sum[index] += value[i]; 
} 

The MSDN документы утверждают, это о регистре:

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

Компилятор не принять пользователя запросы на переменные регистра; вместо этого он делает свой собственный регистр , когда глобально оптимизация распределения регистров (/ Oe ) включена. Тем не менее, все остальные семантики, связанные с регистром , выполняются.

Answer 3

Что вы можете сделать, это собрать его с -S флагом (или эквивалентом, если вы не используете GCC) и сравнить различные выходы сборки с использованием -O, -O2 и -O3 флагов. Один из распространенных способов, чтобы оптимизировать цикл должен сделать некоторую степень разматывания, для (очень простой, наивный), например:

int end = N/2; 
int index = 0; 
for (int i = 0; i < end; ++i) 
{ 
    index = 2 * i; 
    ++size[id[index]]; 
    sum[id[index]] += value[index]; 
    index++; 
    ++size[id[index]]; 
    sum[id[index]] += value[index]; 
} 

, который позволит сократить количество cmp инструкций пополам. Однако любой полупристойный оптимизирующий компилятор сделает это за вас.

Answer 4

Уверены ли вы, что это будет иметь большое значение? Вероятность того, что загрузка «id из внешнего источника» займет значительно больше времени, чем добавление значений.

Не оптимизируйте, пока не узнаете, где находится узкое горло.

Редактировать в ответ на комментарий: Вы меня неправильно поняли. Если для загрузки идентификаторов с жесткого диска требуется 10 секунд, то доли секунды, потраченные на обработку списка, несущественны в грандиозной схеме вещей. Допустим, что требуется 10 секунд для загрузки и 1 секунда для обработки:

Вы оптимизируете цикл обработки, так что он занимает 0 секунд (почти невозможно, но для иллюстрации точки), тогда он STILL занимает 10 секунд. 11 Секунды на самом деле не то, что ba поражает производительность, и вам было бы лучше сосредоточить свое время оптимизации на фактической нагрузке данных, поскольку это гораздо более вероятно, будет медленной частью.

На самом деле может быть вполне оптимальным выполнение нагрузок с двойной буферизацией. т.е. вы загружаете буфер 0, тогда вы начинаете загрузку буфера 1. В то время как буфер 1 загружает буфер процесса 0. Когда закончите загрузку следующего буфера при обработке буфера 1 и так далее. таким образом, вы можете полностью амортизировать затраты на обработку.

Дальнейшее редактирование: На самом деле ваша лучшая оптимизация, вероятно, произошла от загрузки вещей в набор ведер, которые устраняют «id [i]» часть расчета te. Затем вы можете просто разгрузить до 3 потоков, где каждый использует SSE. Таким образом, вы можете объединить их все одновременно и, если у вас есть, по крайней мере, трехъядерная машина, обрабатывать все данные в 10-й раз. Организация данных для оптимальной обработки всегда обеспечит лучшую оптимизацию, IMO.

Answer 5

В зависимости от вашей целевой машины и компилятора, посмотрите, есть ли у вас встроенный _mm_prefetch и сделайте снимок. Вернувшись в дни Pentium D, предварительная выборка данных с использованием инструкции asm для этой внутренней операции была реальной победой в скорости, если вы предварительно набрали несколько итераций цикла, прежде чем вам понадобились данные.

См. here (Страница 95 в формате PDF) для получения дополнительной информации от Intel.

Answer 6

Это вычисление тривиально параллелизуемо; просто добавьте

#pragma OMP parallel_for уменьшение (+: размер, +: сумма) (. -fopenmp в НКУ) график (статический)

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

Если вам необходимо выполнить суммирование несколько раз для заданного сопоставления идентификаторов (т. Е. Массив значений [] изменяется чаще, чем id []), вы можете вдвое сократить требования к пропускной способности памяти, предварительно отсортировав значения [] элементов в идентификатор заказа и устраняя за элемента выборки из идентификатора []:

для (I = 0, J = 0, к = 0; J < 10; сумма [J] + = TMP, J ++)

для (к + = размер [J], TMP = 0; я < к; я ++)

tmp += value[i];