Оптимизированная сумма массива двойников в C
У меня есть задание, где я должен взять программу и сделать ее более эффективной с точки зрения времени. оригинальный код:
#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 ...
long int help;
// ... 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 ...
int j;
for (j = 0; j < ARRAY_SIZE; j++) {
sum += array[j];
help++;
}
// ... 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 ...
// ... and this one.
return 0;
}
Я почти исключительно изменил второй цикл for, изменив его на
double *j=array;
double *p=array+ARRAY_SIZE;
for(; j<p;j+=10){
sum += j[0]+j[1]+j[2]+j[3]+j[4]+j[5]+j[6]+j[7]+j[8]+j[9];
{
это само по себе позволило сократить время до критериев...это уже работает, но есть ли ошибки, которых я не вижу?
3 ответа
Я опубликовал улучшенную версию этого ответа на дубликате этого: справка по оптимизации цикла C для окончательного назначения. Первоначально это был просто репост, но затем я внес некоторые изменения, чтобы ответить на различия в этом вопросе. Я забыл, что отличается, но вы, вероятно, должны прочитать это вместо этого. Может быть, я должен просто удалить этот.
См. Также другие руководства по оптимизации в вики-теге x86.
Прежде всего, это действительно дерьмовый пример, потому что в нем нет ничего, что мешало бы умному компилятору оптимизировать весь процесс. Он даже не печатает сумму. Четное gcc -O1 (вместо -O3 Выкинул некоторые петли.
Обычно вы помещаете свой код в функцию и вызываете его из цикла main() в другом файле. И скомпилируйте их отдельно, без оптимизации кросс-файла всей программы, чтобы компилятор не мог выполнять оптимизацию на основе констант времени компиляции, которые вы вызываете. Повторяющийся цикл, настолько плотно обернутый вокруг фактического цикла над массивом, вызывает хаос с оптимизатором gcc (см. Ниже).
Также:
gcc -Wall -O3 -march=native fast-loop-cs201.c -o fl
fast-loop-cs201.c: In function ‘main’:
fast-loop-cs201.c:17:14: warning: ‘help’ is used uninitialized in this function [-Wuninitialized]
long int help;
Я должен согласиться с пренебрежительными замечаниями EOF о вашем проф. Раздавать код, который оптимизируется без нуля, и с неинициализированными переменными, - это полная чушь.
Некоторые люди в комментариях говорят, что "компилятор не имеет значения" и что вы должны оптимизировать исходный код C для микроархитектуры ЦП, а не позволять компилятору это делать. Это дерьмо: для хорошей производительности вы должны знать, что компиляторы могут делать, а что нет. Некоторые оптимизации являются "хрупкими", и небольшое, казалось бы, невинное изменение в источнике не позволит компилятору что-то сделать.
Я полагаю, ваш профессор упомянул несколько вещей о производительности. Здесь есть множество разных вещей, которые могут вступить в игру, многие из которых, я полагаю, не были упомянуты во втором классе CS.
Помимо многопоточности с openmp, есть векторизация с SIMD. Существуют также оптимизации для современных конвейерных процессоров: в частности, избегайте одной длинной цепочки зависимостей.
Дальнейшее необходимое чтение:
- Руководства Agner Fog по оптимизации C и Asm для x86. Часть из них относится ко всем процессорам.
- Что каждый программист должен знать о памяти
Ваше руководство по компилятору также важно, особенно для кода с плавающей запятой. Плавающая точка имеет ограниченную точность и не является ассоциативной. Окончательная сумма зависит от того, в каком порядке вы выполняете сложения. Однако обычно разница в ошибке округления невелика. Таким образом, компилятор может получить большое ускорение, переупорядочив вещи, если вы используете -ffast-math чтобы позволить это. Это, возможно, было то, что позволял ваш раскрутить на 10.
Вместо того, чтобы просто разворачивать, сохранение нескольких аккумуляторов, которые вы только добавляете в конце, может поддерживать насыщенные блоки выполнения с плавающей запятой, потому что инструкции 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 с. (лязг не поддерживает-march=sandybridge).
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 пересекает строку кэша, вызывая большое замедление. Я полагаю, что на Sandybridge немного быстрее выполнить две отдельные загрузки 16B, когда указатель выровнен по 16B, но не выровнен по 32B. Компилятор делает хороший выбор здесь.
Изменения уровня источника
Как мы можем видеть из 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 Как очевидно требует ваше глупое назначение, значения сохраняются в ОЗУ в конце каждого оператора. (Технически, в каждой "точке последовательности", как ее называют стандарты C.) Написание более длинных выражений без обновления каких-либо переменных, даже временных, сделает -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. Обратите внимание, что я должен был привести приведенное значение calloc потому что godbolt использует компиляторы C++, а не компиляторы C. Внутренний цикл от .L3 в jne .L3, См. https://stackru.com/tags/x86/info для ссылок asm x86. См. Также режимы Micro Fusion и Addressing, потому что это изменение Sandybridge еще не вошло в руководства Agner Fog.).
спектакль:
$ 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 была проблемой в конце концов. Снижение ARRAY_SIZE до 1008 (кратное 16) и увеличение N_TIMES в 10 раз сократило время выполнения до 0,5 с. Это 1,68 insns за цикл. (Внутренний цикл состоит из 7 инструкций для 4 операций добавления FP, таким образом, мы наконец-то насыщаем векторный модуль добавления FP и порты загрузки.) IDK, почему предварительный сборщик HW не может продвинуться после одного останова, а затем остаться впереди. Возможно, предварительная загрузка программного обеспечения может помочь? Может быть, каким-то образом избежать запуска HW prefetcher за массивом, и вместо этого снова начать предварительную выборку начала массива. (Черепица петли - намного лучшее решение, см. ниже.)
Процессоры Intel имеют только 32 Кбайт каждого кэша данных L1 и L1. Я думаю, что ваш массив едва поместится в L1 на процессоре AMD.
Попытка 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) блок в части кода, которую вы можете изменить. Он все равно будет выполнять то же количество операций добавления, но в более оптимальном для кэша порядке.
Я бы попробовал это для внутреннего цикла:
double* tmp = array;
for (j = 0; j < ARRAY_SIZE; j++) {
sum += *tmp; // Use a pointer
tmp++; // because it is faster to increment the pointer
// than it is to recalculate array+j every time
help++;
}
или лучше
double* tmp = array;
double* end = array + ARRAY_SIZE; // Get rid of variable j by calculating
// the end criteria and
while (tmp != end) { // just compare if the end is reached
sum += *tmp;
tmp++;
help++;
}
Я думаю, что вы должны прочитать о библиотеке openmp, если бы вы могли использовать многопоточность. Но это настолько простой пример, который, я думаю, нельзя оптимизировать.
Конечно, вам не нужно заявлять i а также j прежде чем для цикла. Что бы сделать:
for (int i = 0; i < N_TIMES; i++)