Справка по оптимизации цикла C для окончательного назначения
Поэтому для моего последнего задания в классе "Компьютерные системы" нам нужно оптимизировать эти циклы, чтобы они выполнялись быстрее, чем оригинал. Базовая оценка составляет менее 7 секунд, а полная оценка - менее 5 секунд на нашем сервере Linux. Этот код, который у меня есть, получает около 5,6 секунд. Я думаю, что мне может понадобиться использовать указатели с этим, чтобы заставить его работать быстрее, но я не совсем уверен. Может ли кто-нибудь предложить какие-либо советы или варианты, которые у меня есть? Спасибо вам большое!
QUICKEDIT: файл должен содержать не более 50 строк, и я игнорирую те строки с комментариями, которые включил инструктор.
#include <stdio.h>
#include <stdlib.h>
// You are only allowed to make changes to this code as specified by the comments in it.
// The code you submit must have these two values.
#define N_TIMES 600000
#define ARRAY_SIZE 10000
int main(void)
{
double *array = calloc(ARRAY_SIZE, sizeof(double));
double sum = 0;
int i;
// You can add variables between this comment ...
register double sum1 = 0, sum2 = 0, sum3 = 0, sum4 = 0, sum5 = 0, sum6 = 0, sum7 = 0, sum8 = 0, sum9 = 0;
register int j;
// ... and this one.
printf("CS201 - Asgmt 4 - \n");
for (i = 0; i < N_TIMES; i++)
{
// You can change anything between this comment ...
for (j = 0; j < ARRAY_SIZE; j += 10)
{
sum += array[j];
sum1 += array[j + 1];
sum2 += array[j + 2];
sum3 += array[j + 3];
sum4 += array[j + 4];
sum5 += array[j + 5];
sum6 += array[j + 6];
sum7 += array[j + 7];
sum8 += array[j + 8];
sum9 += array[j + 9];
}
// ... and this one. But your inner loop must do the same
// number of additions as this one does.
}
// You can add some final code between this comment ...
sum += sum1 + sum2 + sum3 + sum4 + sum5 + sum6 + sum7 + sum8 + sum9;
// ... and this one.
return 0;
}
3 ответа
Вы можете быть на правильном пути, хотя вам нужно измерить его, чтобы быть уверенным (мой обычный совет, чтобы измерить, а не угадывать, кажется здесь немного излишним, так как весь смысл задания состоит в том, чтобы измерить).
Оптимизация компиляторов, вероятно, не увидит большой разницы, поскольку они довольно умны в этом, но, поскольку мы не знаем, на каком уровне оптимизации он будет компилироваться, вы можете получить существенное улучшение.
Чтобы использовать указатели во внутреннем цикле, достаточно сначала добавить переменную-указатель:
register double *pj;
затем изменив цикл на:
for (pj = &(array[0]); pj < &(array[ARRAY_SIZE]); j++) {
sum += *j++;
sum1 += *j++;
sum2 += *j++;
sum3 += *j++;
sum4 += *j++;
sum5 += *j++;
sum6 += *j++;
sum7 += *j++;
sum8 += *j++;
sum9 += *j;
}
Это сохраняет количество добавлений в цикле одинаковым (при условии, что вы считаете += а также ++ как операторы сложения, конечно), но в основном использует указатели, а не индексы массива.
Без оптимизации 1 в моей системе это снижает его с 9,868 секунд (время процессора) до 4,84 секунд. Ваш пробег может отличаться.
1 С уровнем оптимизации -O3 Обе, как сообщается, занимают 0,001 секунды, поэтому, как уже упоминалось, оптимизаторы довольно умны. Однако, учитывая, что вы видите 5+ секунд, я бы предположил, что он не был скомпилирован с оптимизацией.
Кроме того, это хорошая причина, почему обычно рекомендуется писать код в удобочитаемой форме и позволить компилятору позаботиться о том, чтобы он работал быстрее. Хотя мои скудные попытки оптимизации примерно удвоили скорость, используя -O3 заставил его работать примерно в десять тысяч раз быстрее:-)
Повторная публикация измененной версии моего ответа из оптимизированной суммы массива парных чисел в C, поскольку этот вопрос был снижен до -5. ОП другого вопроса больше выразил это как "что еще возможно", так что я взял его на слово и бросил информацию о векторизации и настройке для текущего аппаратного обеспечения процессора.:)
ОП этого вопроса в конце концов сказал, что ему не разрешено использовать параметры компилятора выше -O0 Я полагаю, что и здесь тоже так.
Резюме:
Зачем использовать
-O0искажает вещи (несправедливо наказывает вещи, которые хороши в обычном коде для обычного компилятора).Вещи, которые не так с назначением.
Типы оптимизаций. Задержка FP в зависимости от пропускной способности и цепочек зависимостей. Ссылка на сайт Агнер Фог. (Необходимое чтение для оптимизации).
Эксперименты заставляют компилятор оптимизировать его (после исправления, чтобы не оптимизировать его). Лучший результат с авто-векторизацией (без изменений источника): gcc: вдвое быстрее, чем оптимальный векторизованный цикл. clang: та же скорость, что и в векторизованном цикле.
Еще несколько комментариев о том, почему большие выражения являются идеальной победой с
-O0только.Изменения исходного кода, чтобы получить хорошую производительность без
-ffast-math, делая код ближе к тому, что мы хотим, чтобы компилятор делал. Также некоторые правила-законоведческие идеи, которые были бы бесполезны в реальном мире.Векторизация цикла с помощью GCC-архитектурно-нейтральных векторов позволяет увидеть, насколько близко компиляторы автоматически векторизовались к соответствию производительности идеального кода asm (поскольку я проверял выходные данные компилятора).
Я думаю, что цель задания - научить оптимизации производительности на ассемблере с использованием языка Си без оптимизации компилятора. Это глупо. Он смешивает вещи, которые компилятор сделает для вас в реальной жизни, с вещами, которые требуют изменений на уровне исходного кода.
-O0 не просто "не оптимизировать", он заставляет компилятор хранить переменные в памяти после каждого оператора, вместо того, чтобы хранить их в регистрах. Это делает это, чтобы вы получили "ожидаемые" результаты, если вы установили точку останова с помощью gdb и изменили значение (в памяти) переменной C. Или даже если ты jump на другую строку в той же функции. Поэтому каждый оператор C должен быть скомпилирован в независимый блок asm, который начинается и заканчивается всеми переменными в памяти. Для современного переносимого компилятора, такого как gcc, который уже трансформируется через несколько внутренних представлений потока программы на пути от источника к asm, эта часть -O0 требует явной де-оптимизации своего графика потока данных обратно в отдельные операторы Си. Эти сохранения / перезагрузки удлиняют каждую цепочку зависимостей, переносимых циклами, так что это ужасно для крошечных циклов (например, 1 цикл на итерацию против узкого места 6c при обновлении счетчика цикла).
С gcc -O0, register ключевое слово позволяет gcc хранить переменную в регистре, а не в памяти, и, таким образом, может иметь большое значение в тесных циклах ( пример в проводнике компилятора Godbolt). Но это только с -O0, В реальном коде register не имеет смысла: компилятор пытается оптимально использовать доступные регистры для переменных и временных переменных. register уже устарело в ISO C++11 (но не в C11), и есть предложение удалить его из языка вместе с другими устаревшими вещами, такими как триграфы.
С учетом дополнительных переменных, -O0 Вредит индексированию массива немного больше, чем приращение указателя.
Индексирование массива обычно облегчает чтение кода. Компиляторы иногда не могут оптимизировать такие вещи, как array[i*width + j*width*height] так что это хорошая идея, чтобы изменить источник, чтобы сделать оптимизацию снижения силы превращения умножения в += добавляет.
На уровне asm индексирование массива и увеличение указателя близки к одинаковой производительности. (например, в x86 есть режимы адресации [rsi + rdx*4] которые так же быстро, как [rdi], кроме Sandybridge и более поздних.) Задача компилятора - оптимизировать ваш код с помощью увеличения указателя, даже когда источник использует индексирование массива, когда это происходит быстрее.
Для хорошей производительности вы должны знать, что компиляторы могут и не могут делать. Некоторые оптимизации являются "хрупкими", и небольшое, казалось бы, невинное изменение исходного кода не позволит компилятору выполнить оптимизацию, которая была необходима для быстрого выполнения некоторого кода. (например, вытащить постоянное вычисление из цикла или доказать что-то о том, как различные условия ветвления связаны друг с другом, и упростить.)
Помимо всего этого, это дерьмовый пример, потому что в нем нет ничего, что мешало бы умному компилятору оптимизировать весь процесс. Он даже не печатает сумму. Четное gcc -O1 (вместо -O3 Выкинул некоторые петли.
(Вы можете исправить это, напечатав sum в конце. GCC и Clang, кажется, не понимают, что calloc возвращает обнуленную память и оптимизирует ее 0.0, Смотрите мой код ниже.)
Обычно вы помещаете свой код в функцию и вызываете его из цикла main() в другом файле. И скомпилируйте их отдельно, без оптимизации кросс-файла всей программы, чтобы компилятор не мог выполнять оптимизацию на основе констант времени компиляции, которые вы вызываете. Повторяющийся цикл, настолько плотно обернутый вокруг фактического цикла над массивом, вызывает хаос с оптимизатором gcc (см. Ниже).
Кроме того, другая версия этого вопроса имела неинициализированную переменную. Это выглядит как long int help был введен ОП этого вопроса, а не проф. Поэтому мне придется понизить мою "полную ерунду" до простой "глупости", потому что код даже не выводит результат в конце. Это самый распространенный способ заставить компилятор не оптимизировать все в микробенчмарке, подобном этому.
Я полагаю, ваш профессор упомянул несколько вещей о производительности. Здесь есть множество разных вещей, которые могут вступить в игру, многие из которых, я полагаю, не были упомянуты во втором классе CS.
Помимо многопоточности с openmp, есть векторизация с SIMD. Существуют также оптимизации для современных конвейерных процессоров: в частности, избегайте одной длинной цепочки зависимостей.
Дальнейшее необходимое чтение:
- Руководства Agner Fog по оптимизации C и Asm для x86. Часть из них относится ко всем процессорам.
- Что каждый программист должен знать о памяти
Ваше руководство по компилятору также важно, особенно для кода с плавающей запятой. Плавающая точка имеет ограниченную точность и не является ассоциативной. Окончательная сумма зависит от того, в каком порядке вы выполняете сложения. Обычно разница в ошибке округления невелика, поэтому компилятор может получить большое ускорение, переупорядочив вещи, если вы используете -ffast-math чтобы позволить это.
Вместо того, чтобы просто развернуть, сохраните несколько аккумуляторов, которые вы добавляете только в конце, как вы делаете с sum0.. sum9 раскатать-на-10. Инструкции FP имеют среднюю задержку, но высокую пропускную способность, поэтому вам нужно выполнять несколько операций FP в полете, чтобы поддерживать насыщенные блоки выполнения с плавающей запятой.
Если вам нужно, чтобы результат последней операции был завершен до начала следующей операции, вы ограничены задержкой. Для FP добавить это один на 3 цикла. В Intel Sandybridge, IvB, Haswell и Broadwell пропускная способность FP добавляется по одному на цикл. Таким образом, вам нужно сохранить как минимум 3 независимых операции, которые могут быть в полете одновременно, чтобы насытить машину. Для Skylake это 2 за цикл с задержкой в 4 такта. (С положительной стороны для Skylake, FMA уменьшена до 4 циклов задержки.)
В этом случае есть и такие базовые вещи, как вытаскивание из цикла, например help += ARRAY_SIZE,
параметры компилятора
Начнем с того, что компилятор может сделать для нас.
Я начал с оригинального внутреннего цикла, просто help += ARRAY_SIZE вытащил, и добавив printf в конце так gcc не все оптимизирует. Давайте попробуем некоторые варианты компилятора и посмотрим, чего мы можем достичь с помощью gcc 4.9.2 (на моем i5 2500k Sandybridge. Максимальная турбо- частота 3,8 ГГц (небольшая ОС), 3,3 ГГц (не имеет значения для этого короткого теста)):
gcc -O0 fast-loop-cs201.c -o fl: Выступление 16.43s - это полная шутка. Переменные сохраняются в памяти после каждой операции и загружаются до следующей. Это узкое место, и добавляет много времени ожидания. Не говоря уже о проигрышах на реальных оптимизациях. Сроки / настройка кода с-O0не полезно-O1: 4.87s-O2: 4.89s-O3: 2.453s (использует SSE для выполнения 2 одновременно. Я, конечно, использую 64-битную систему, поэтому аппаратная поддержка-msse2является базовым.)-O3 -ffast-math -funroll-loops: 2.439s-O3 -march=sandybridge -ffast-math -funroll-loops: 1.275s (использует AVX для выполнения 4 одновременно.)-Ofast ...: нет выгоды-O3 -ftree-parallelize-loops=4 -march=sandybridge -ffast-math -funroll-loops: 0m2.375s реально, 0m8.500s пользователя. Похоже, блокировка над головой убила его. Он порождает всего 4 потока, но внутренний цикл слишком короткий, чтобы быть выигрышным: он собирает суммы каждый раз вместо того, чтобы давать каждому потоку 1/4 итераций внешнего цикла.-Ofast -fprofile-generate -march=sandybridge -ffast-math, тогда запусти-Ofast -fprofile-use -march=sandybridge -ffast-math: 1.275 с. Оптимизация по профилю - это хорошая идея, когда вы можете использовать все соответствующие пути кода, чтобы компилятор мог лучше принимать решения по развертыванию / вставке.clang-3.5 -Ofast -march=native -ffast-math: 1.070 с. (Clang 3.5 слишком стар, чтобы поддерживать-march=sandybridge, Вы должны предпочесть использовать версию компилятора, которая является достаточно новой, чтобы знать о целевой архитектуре, для которой вы настраиваете, особенно. при использовании-marchсделать код, который не должен работать на старых архитектурах.)
gcc -O3 веселый векторизация: внутренний цикл выполняет 2 (или 4) итерации внешнего цикла параллельно, передавая один элемент массива всем элементам регистра xmm (или ymm) и выполняя addpd на что. Таким образом, он видит, что одни и те же значения добавляются неоднократно, но даже -ffast-math не позволяет gcc просто превратить это в умножение. Или поменяйте петли.
clang-3.5 векторизуется намного лучше: он векторизует внутренний цикл, а не внешний, поэтому он не нуждается в трансляции. Он даже использует 4 векторных регистра как 4 отдельных аккумулятора. Тем не менее, это не предполагает, что calloc возвращает выровненную память, и по некоторым причинам он считает, что лучшая ставка - пара нагрузок 128b.
vmovupd -0x60(%rbx,%rcx,8),%xmm4`
vinsertf128 $0x1,-0x50(%rbx,%rcx,8),%ymm4,%ymm4
Это на самом деле медленнее, когда я говорю, что массив выровнен. (с глупым взломом, как array = (double*)((ptrdiff_t)array & ~31); который на самом деле генерирует инструкцию для маскировки младших 5 бит, потому что clang-3.5 не поддерживает gcc __builtin_assume_aligned.) Я думаю, что путь плотной петли в 4 раза vaddpd mem, %ymmX,%ymmX выровнен ставит cmp $0x271c,%rcx пересекает границу 32В, поэтому она не может слиться с jne, Пропускная способность мопов не должна быть проблемой, так как этот код получает только 0,65insns за цикл (и 0,93 моп / цикл), согласно perf,
Ааа, я проверил с помощью отладчика, и calloc возвращает только 16B-выровненный указатель. Таким образом, половина обращений к памяти 32B пересекает строку кэша, вызывая большое замедление. Немного быстрее выполнить две отдельные загрузки 16B, когда указатель выровнен по 16B, но не выровнен по 32B, в Sandybridge. (GCC позволяет -mavx256-split-unaligned-load а также ...-store за -march=sandybridge, а также для мелодии по умолчанию = универсальный с -mavx, что не очень хорошо, особенно для Haswell или с памятью, которая обычно выравнивается компилятором, не знает об этом.)
Изменения уровня источника
Как мы можем видеть из gcc, бьющих gcc, несколько аккумуляторов превосходны. Наиболее очевидный способ сделать это будет:
for (j = 0; j < ARRAY_SIZE; j+=4) { // unroll 4 times
sum0 += array[j];
sum1 += array[j+1];
sum2 += array[j+2];
sum3 += array[j+3];
}
и затем не собирайте 4 аккумулятора в один до окончания внешнего цикла.
Ваш (из другого вопроса) источник изменения
sum += j[0]+j[1]+j[2]+j[3]+j[4]+j[5]+j[6]+j[7]+j[8]+j[9];
на самом деле имеет аналогичный эффект, благодаря выполнению вне порядка. Каждая группа из 10 представляет собой отдельную цепочку зависимостей. правила порядка операций говорят j значения добавляются вместе, а затем добавляются в sum, Таким образом, цепочка зависимостей, переносимая циклами, по-прежнему представляет собой только задержку одного добавления FP, и для каждой группы из 10. существует много независимой работы. Каждая группа представляет собой отдельную цепочку зависимостей из 9 добавлений, и для ее выполнения требуется всего несколько инструкций. -закажите аппаратное обеспечение исполнения, чтобы увидеть начало следующей цепочки и найти параллелизм, чтобы поддерживать эти блоки исполнения FP со средней задержкой и высокой пропускной способностью.
С -O0 Как очевидно требует ваше глупое назначение, значения сохраняются в ОЗУ в конце каждого оператора. Написание более длинных выражений без обновления каких-либо переменных, даже временных, сделает -O0 работать быстрее, но это не полезная оптимизация. Не тратьте свое время на изменения, которые только помогают -O0 особенно не за счет читабельности.
Использование 4-х переменных-аккумуляторов и не суммирование их вместе до конца внешнего цикла побеждает авто-векторизатор clang. Он по-прежнему работает всего за 1,66 с (против 4,89 для не векторизованного gcc -O2 с одним аккумулятором). Четное gcc -O2 без -ffast-math также получает 1,66 с для этого изменения источника. Обратите внимание, что ARRAY_SIZE, как известно, кратно 4, поэтому я не включил никакого кода очистки для обработки последних до 3 элементов (или во избежание чтения за концом массива, что произойдет так, как написано сейчас), При этом очень легко ошибиться и прочитать за конец массива.
С другой стороны, gcc векторизует это, но также пессимизирует (не оптимизирует) внутренний цикл в единую цепочку зависимостей. Я думаю, что он снова делает несколько итераций внешнего цикла.
Используя независимые от платформы векторные расширения gcc, я написал версию, которая компилируется в очевидно оптимальный код:
// compile with gcc -g -Wall -std=gnu11 -Ofast -fno-tree-vectorize -march=native fast-loop-cs201.vec.c -o fl3-vec
#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>
#include <assert.h>
#include <string.h>
// You are only allowed to make changes to this code as specified by the comments in it.
// The code you submit must have these two values.
#define N_TIMES 600000
#define ARRAY_SIZE 10000
int main(void)
{
double *array = calloc(ARRAY_SIZE, sizeof(double));
double sum = 0;
int i;
// You can add variables between this comment ...
long int help = 0;
typedef double v4df __attribute__ ((vector_size (8*4)));
v4df sum0={0}, sum1={0}, sum2={0}, sum3={0};
const size_t array_bytes = ARRAY_SIZE*sizeof(double);
double *aligned_array = NULL;
// this more-than-declaration could go in an if(i == 0) block for strict compliance with the rules
if ( posix_memalign((void**)&aligned_array, 32, array_bytes) ) {
exit (1);
}
memcpy(aligned_array, array, array_bytes); // In this one case: faster to align once and have no extra overhead for N_TIMES through the loop
// ... and this one.
// Please change 'your name' to your actual name.
printf("CS201 - Asgmt 4 - I. Forgot\n");
for (i = 0; i < N_TIMES; i++) {
// You can change anything between this comment ...
/*
#if defined(__GNUC__) && (__GNUC__ * 100 + __GNUC_MINOR__) >= 407 // GCC 4.7 or later.
array = __builtin_assume_aligned(array, 32);
#else
// force-align for other compilers. This loop-invariant will be done outside the loop.
array = (double*) ((ptrdiff_t)array & ~31);
#endif
*/
assert ( ARRAY_SIZE / (4*4) == (ARRAY_SIZE+15) / (4*4) ); // We don't have a cleanup loop to handle where the array size isn't a multiple of 16
// incrementing pointers can be more efficient than indexing arrays
// esp. on recent Intel where micro-fusion only works with one-register addressing modes
// of course, the compiler can always generate pointer-incrementing asm from array-indexing source
const double *start = aligned_array;
while ( (ptrdiff_t)start & 31 ) {
// annoying loops like this are the reason people use aligned buffers
sum += *start++; // scalar until we reach 32B alignment
// in practice, this loop doesn't run, because we copy into an aligned buffer
// This will also require a cleanup loop, and break our multiple-of-16 doubles assumption.
}
const v4df *end = (v4df *)(aligned_array+ARRAY_SIZE);
for (const v4df *p = (v4df *)start ; p+3 < end; p+=4) {
sum0 += p[0]; // p+=4 increments the pointer by 4 * 4 * 8 bytes
sum1 += p[1]; // make sure you keep track of what you're incrementing
sum2 += p[2];
sum3 += p[3];
}
// the compiler might be smart enough to pull this out of the inner loop
// in fact, gcc turns this into a 64bit movabs outside of both loops :P
help+= ARRAY_SIZE;
// ... and this one. But your inner loop must do the same
// number of additions as this one does.
/* You could argue legalese and say that
if (i == 0) {
for (j ...)
sum += array[j];
sum *= N_TIMES;
}
* still does as many adds in its *INNER LOOP*, but it just doesn't run it as often
*/
}
// You can add some final code between this comment ...
sum0 = (sum0 + sum1) + (sum2 + sum3);
sum += sum0[0] + sum0[1] + sum0[2] + sum0[3];
printf("sum = %g; help=%ld\n", sum, help); // defeat the compiler.
free (aligned_array);
free (array); // not strictly necessary, because this is the end of main(). Leaving it out for this special case is a bad example for a CS class, though.
// ... and this one.
return 0;
}
Внутренний цикл компилируется в:
4007c0: c5 e5 58 19 vaddpd (%rcx),%ymm3,%ymm3
4007c4: 48 83 e9 80 sub $0xffffffffffffff80,%rcx # subtract -128, because -128 fits in imm8 instead of requiring an imm32 to encode add $128, %rcx
4007c8: c5 f5 58 49 a0 vaddpd -0x60(%rcx),%ymm1,%ymm1 # one-register addressing mode can micro-fuse
4007cd: c5 ed 58 51 c0 vaddpd -0x40(%rcx),%ymm2,%ymm2
4007d2: c5 fd 58 41 e0 vaddpd -0x20(%rcx),%ymm0,%ymm0
4007d7: 4c 39 c1 cmp %r8,%rcx # compare with end with p
4007da: 75 e4 jne 4007c0 <main+0xb0>
(Для получения дополнительной информации см. Онлайн-вывод компилятора в проводнике компилятора Godbolt. -xc Опция компилятора компилируется как C, а не C++. Внутренний цикл от .L3 в jne .L3, Смотрите вики-теги x86 для ссылок asm x86. Смотрите также этот вопрос о микросинтезе, не происходящем в семействе SnB, который не описан в руководствах Агнера Фога).
спектакль:
$ perf stat -e task-clock,cycles,instructions,r1b1,r10e,stalled-cycles-frontend,stalled-cycles-backend,L1-dcache-load-misses,cache-misses ./fl3-vec
CS201 - Asgmt 4 - I. Forgot
sum = 0; help=6000000000
Performance counter stats for './fl3-vec':
1086.571078 task-clock (msec) # 1.000 CPUs utilized
4,072,679,849 cycles # 3.748 GHz
2,629,419,883 instructions # 0.65 insns per cycle
# 1.27 stalled cycles per insn
4,028,715,968 r1b1 # 3707.733 M/sec # unfused uops
2,257,875,023 r10e # 2077.982 M/sec # fused uops. lower than insns because of macro-fusion
3,328,275,626 stalled-cycles-frontend # 81.72% frontend cycles idle
1,648,011,059 stalled-cycles-backend # 40.47% backend cycles idle
751,736,741 L1-dcache-load-misses # 691.843 M/sec
18,772 cache-misses # 0.017 M/sec
1.086925466 seconds time elapsed
Я до сих пор не знаю, почему он получает такие низкие инструкции за цикл. Внутренний цикл использует 4 отдельных аккумулятора, и я проверил с помощью GDB, что указатели выровнены. Таким образом, конфликты между кеш-банком не должны быть проблемой. Кэш-память второго уровня Sandybridge может выдерживать одну передачу 32B за цикл, что должно соответствовать одному добавлению вектора 32B FP за цикл.
Загрузка 32B из L1 занимает 2 цикла (до тех пор, пока в Haswell Intel не произвела загрузку 32B за один цикл). Однако есть 2 порта загрузки, поэтому поддерживаемая пропускная способность составляет 32B на цикл (чего мы не достигаем).
Может быть, нагрузки должны быть переданы по конвейеру, когда они используются, чтобы минимизировать заполнение ROB (буфера переупорядочения), когда нагрузка останавливается? Но счетчики производительности указывают на довольно высокую частоту обращений к кэшу L1, поэтому аппаратная предварительная выборка от L2 к L1, кажется, делает свое дело.
0,65 инструкций за цикл - это только примерно половина пути к насыщению векторного FP-сумматора. Это расстраивает. Даже IACA говорит, что цикл должен выполняться в 4 цикла на итерацию. (т.е. насыщать порты загрузки и порт1 (где живет сумматор FP)):/
обновление: я думаю, что пропускная способность L2 была проблемой в конце концов. Недостаточно буферов для заполнения линии, чтобы удерживать достаточно промахов в полете, чтобы поддерживать максимальную пропускную способность в каждом цикле. Поддерживаемая пропускная способность L2 меньше максимальной на процессорах Intel SnB / Haswell / Skylake.
См. Также Пропускная способность однопоточной памяти на SandyBridge (ветка на форуме Intel, где много говорится о том, что ограничивает пропускную способность и как latency * max_concurrency является одним из возможных узких мест. См. Также часть "Платформы с задержкой " в ответе на расширенный REP MOVSB для memcpy; ограниченный параллелизм памяти является узким местом как для нагрузок, так и для хранилищ, но для предварительных загрузок в L2 это означает, что вы не можете быть ограничены чисто буферами Line Fill для исключительных промахов L1D.
Снижение ARRAY_SIZE до 1008 (кратное 16) и увеличение N_TIMES в 10 раз сократило время выполнения до 0,5 с. Это 1,68 insns за цикл. (Внутренний цикл - это всего 7 инструкций для 4-х операций добавления FP, таким образом, мы наконец-то насыщаем векторный модуль добавления FP и порты нагрузки.) Черепичное построение цикла является гораздо лучшим решением, см. Ниже.
Процессоры Intel имеют только 32 Кбайт каждого кэша данных L1 и L1. Я думаю, что ваш массив едва поместился бы в 64-килобайтном L1D на процессоре AMD K10 (Стамбул), но не в семействе Bulldozer (16-килобайтный L1D) или Ryzen (32-килобайтный L1D).
Попытка Gcc векторизовать, передавая то же значение в параллельное дополнение, не кажется такой безумной. Если бы ему удалось получить это право (используя несколько аккумуляторов, чтобы скрыть задержку), это позволило бы ему насытить векторный FP-сумматор только половиной пропускной способности памяти. На самом деле, это было в значительной степени стирка, вероятно, из-за накладных расходов на вещание.
Кроме того, это довольно глупо. N_TIMES это просто повторение работы. На самом деле мы не хотим оптимизировать выполнение одной и той же работы несколько раз. Если только мы не хотим побеждать в глупых заданиях, подобных этому. Способ сделать это на уровне источника - увеличить i в части кода мы можем изменить:
for (...) {
sum += a[j] + a[j] + a[j] + a[j];
}
i += 3; // The inner loop does 4 total iterations of the outer loop
Более реалистично, чтобы справиться с этим, вы могли бы поменять местами циклы (зациклите массив один раз, добавив каждое значение N_TIMES раз). Я думаю, что я читал, что компилятор Intel иногда делает это для вас.
Более общая техника называется блокировкой кеша или циклическим разбиением. Идея состоит в том, чтобы обрабатывать ваши входные данные небольшими блоками, которые помещаются в кэш. В зависимости от вашего алгоритма, может быть возможно выполнить различные этапы работы с чанком, а затем повторить для следующего чанка, вместо того, чтобы каждый этап проходил по всему входу. Как всегда, когда вы знаете правильное название для хитрости (и она существует вообще), вы можете погуглить тонну информации.
Вы могли бы по правилам адвокат ваш путь в том, чтобы положить взаимозаменяемый цикл внутри if (i == 0) блок в части кода, которую вы можете изменить. Он все равно будет выполнять то же количество операций добавления, но в более оптимальном для кэша порядке.
Прежде всего, попробуйте изменить настройки компилятора, чтобы создать более быстрый код. Существует общая оптимизация, и компилятор может выполнять автоматическую векторизацию.
Что вы всегда будете делать, это попробовать несколько подходов и проверить, что является самым быстрым. В качестве цели, попробуйте получить один цикл за добавление или лучше.
Количество итераций в цикле: вы складываете 10 сумм одновременно. Возможно, ваш процессор не имеет достаточно регистров для этого, или он имеет больше. Я бы измерял время для 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14... сумм за цикл.
Количество сумм: Наличие более одной суммы означает, что задержка не кусает вас, а просто увеличивает пропускную способность. Но более четырех или шести могут не быть полезными. Попробуйте четыре суммы, с 4, 8, 12, 16 итерациями на цикл. Или шесть сумм с 6, 12, 18 итерациями.
Кэширование: вы пробегаете массив из 80000 байтов. Вероятно, больше, чем кэш L1. Разделите массив на 2 или 4 части. Выполните внешний цикл, повторяющийся по двум или четырем подмассивам, следующий цикл от 0 до N_TIMES - 1 и внутренний цикл, суммирующий значения.
И тогда вы можете попробовать использовать векторные операции, или многопоточность вашего кода, или использовать графический процессор для выполнения работы.
И если вы вынуждены не использовать оптимизацию, тогда ключевое слово "register" может действительно работать.