Ответ 1
Я опубликовал улучшенную версию этого ответа в дубликате этого: помощь оптимизации цикла C для окончательного назначения. Первоначально это был репост, но затем я внес некоторые изменения, чтобы ответить на различия в этом вопросе. Я забываю, что другое, но вы, вероятно, должны это прочитать. Возможно, я просто удалю этот.
См. также другие руководства по оптимизации в x86 tag wiki.
Прежде всего, это действительно хард-образец, потому что у него нет ничего, чтобы остановить умный компилятор от оптимизации всего. Он даже не печатает сумму. Даже 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 2-го года.
Помимо многопоточности с openmp, векторизация выполняется с помощью SIMD. Существуют также оптимизация для современных конвейерных процессоров: в частности, избегайте одной длинной цепи зависимостей.
Дальнейшее существенное чтение:
- Руководство Agner Fog для оптимизации C и asm для x86. Некоторые из них применимы ко всем ЦП.
- Что каждый программист должен знать о памяти
Ваше руководство по компилятору также имеет важное значение, особенно. для кода с плавающей точкой. Плавающая точка имеет ограниченную точность и не является ассоциативной. Окончательная сумма зависит от того, какой порядок вы выполняете. Однако, как правило, разница в погрешности округления мала. Таким образом, компилятор может получить большое ускорение, переупорядочивая вещи, если вы используете -ffast-math, чтобы разрешить это. Возможно, это было то, что разрешено вашим разворачиванием.
Вместо того, чтобы просто разворачивать, хранение нескольких аккумуляторов, которые вы только добавляете в конце, может поддерживать насыщенность блоков выполнения с плавающей запятой, поскольку команды FP имеют латентность!= пропускная способность. Если вам нужно, чтобы результат последнего op был завершен до следующего запуска, вы ограничены задержкой. Для FP добавить, что один на 3 цикла. В Intel Sandybridge, IvB, Haswell и Broadwell пропускная способность FP add составляет один за цикл. Поэтому вам нужно сохранить как минимум 3 независимых оператора, которые могут быть в полете сразу, чтобы насытить машину. Для Skylake, 2 за цикл с задержкой в 4 часа. (На стороне плюса для Skylake FMA сокращается до 4 циклов).
В этом случае также есть базовые вещи, такие как вытаскивание вещей из цикла, например. help += ARRAY_SIZE.
параметры компилятора
Я начал с оригинальной внутренней петли, вытащив всего help += ARRAY_SIZE и добавив printf в конец, так что gcc не оптимизирует все. Попробуйте некоторые параметры компилятора и посмотрите, что мы можем достичь с помощью gcc 4.9.2 (на моем i5 2500k Sandybridge. 3.8GHz max turbo (небольшой OC), 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.275s -
clang-3.5 -Ofast -march=native -ffast-math: 1.070s. (clang не поддерживает-march=sandybridge).
gcc -O3 векторизует веселым способом: внутренний цикл выполняет 2 (или 4) итерации внешнего цикла параллельно, передавая один элемент массива всем элементам регистра xmm (или ymm) и выполняя addpd на этом. Таким образом, он видит, что одни и те же значения добавляются повторно, но даже -ffast-math не позволяет gcc просто превращать его в умножение. Или переключите петли.
clang-3.5 векторизует намного лучше: он вектурирует внутренний цикл, а не внешний, поэтому ему не нужно транслировать. Он даже использует 4 векторных регистра как 4 отдельных аккумулятора. Тем не менее, он не предполагает, что calloc возвращает выровненную память, и по какой-то причине он считает, что лучшим вариантом является пара 128-битных нагрузок.
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.) Я думаю, что способ, которым жесткая петля 4x vaddpd mem, %ymmX,%ymmX выравнивается ставит cmp $0x271c,%rcx пересечение границы 32B, поэтому он не может использовать макро-предохранитель с jne. uop пропускная способность не должна быть проблемой, хотя, поскольку этот код только получает 0,65inns за цикл (и 0,93 uops/cycle), согласно perf.
Ahh, я проверил с отладчиком, а calloc возвращает указатель с 16-кратным выравниванием. Таким образом, половина доступа к памяти 32B пересекает линию кэша, что вызывает значительное замедление. Я думаю, что немного быстрее сделать две отдельные нагрузки 16B, когда ваш указатель выровнен по 16B, но не 32B-выровнен, на Sandybridge. Компилятор делает хороший выбор здесь.
Изменения уровня источника
Как видно из clang beating 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 добавлений и требует достаточно нескольких инструкций для выхода из аппаратное обеспечение выполнения заказа, чтобы увидеть начало следующей цепочки, и найдите parallelism, чтобы сохранить эти средние задержки, а также высокопроизводительные модули исполнения FP.
С -O0, как вам кажется, ваше глупое присваивание, значения сохраняются в ОЗУ в конце каждого утверждения. (Технически, в каждой "точке последовательности", как это называют стандарты C.) Написание более длинных выражений без обновления каких-либо переменных, даже временных, сделает -O0 быстрее, но это не является полезной оптимизацией. Не тратьте время на изменения, которые помогают только с -O0, особенно. не за счет удобочитаемости.
Использование 4-аккумулятора и не сложение их вместе до тех пор, пока конец внешнего цикла не победит авто-векторный указатель. Он по-прежнему работает только с 1,66 с (против 4,89 для gcc-не-векторизованных -O2 с одним аккумулятором). Даже gcc -O2 без -ffast-math также получает 1,66 с для этого изменения источника. Обратите внимание, что ARRAY_SIZE, как известно, кратно 4, поэтому я не включил код очистки для обработки последних элементов "вверх-до" (или чтобы не пропустить конец конца массива, что произойдет, как написано сейчас), Это действительно легко получить что-то неправильно и прочитать за конец массива при этом.
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. Внутренний цикл от .L3 до jne .L3. См. fooobar.com/tags/x86/... для ссылок asm x86. См. Также Режимы микросовключения и адресации, потому что это изменение 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 L2 может поддерживаться одна передача 32B за цикл, которая должна идти в ногу с тем, что один вектор 32 FP добавляет за цикл.
Загружает 32B нагрузки из L1, занимая 2 цикла (это было только после того, как Хасуэлл, который Intel сделал 32B, загружал однотактную операцию). Однако есть 2 порта нагрузки, поэтому устойчивая пропускная способность составляет 32 Б за цикл (чего мы не достигаем).
Возможно, нагрузки должны быть конвейерными впереди, когда они используются, чтобы свести к минимуму заполнение ROB (буфера повторного заказа) при загрузке груза? Но счетчики perf указывают на довольно высокую частоту попадания кеша L1, поэтому аппаратная предварительная выборка от L2 до L1, похоже, выполняет свою работу.
0,65 инструкций за цикл составляют примерно половину пути для насыщения векторного сумматора FP. Это расстраивает. Даже IACA говорит, что цикл должен выполняться в 4 циклах на итерацию. (то есть насыщают порты нагрузки и порт1 (где живет сумматор FP)):/
update: Я предполагаю, что L2 латентность была проблемой в конце концов. Уменьшение ARRAY_SIZE до 1008 (кратное 16) и увеличение N_TIMES в 10 раз привело к сокращению времени выполнения до 0,5 с. Это 1.68 insns за цикл. (Внутренний цикл - 7 общих инструкций для добавления 4 FP, таким образом, мы, наконец, насыщаем блок добавления FP и порты загрузки.) IDK, почему превентор HW не может продвинуться после одного ларька, а затем оставаться впереди. Возможно, может помочь предварительная выборка программного обеспечения? Возможно, каким-то образом избежать использования префактора HW за массивом и вместо этого снова начать предварительную выборку начала массива. (петлевая черепица - намного лучшее решение, см. ниже.)
Процессоры Intel имеют только 32 тыс. кэшей L1-данных и L1-команд. Я думаю, что ваш массив будет едва вписываться в L1 на процессоре AMD.
Gcc попытка векторизации путем трансляции одного и того же значения в параллельный add не кажется настолько сумасшедшим. Если бы это удалось сделать правильно (используя несколько аккумуляторов, чтобы скрыть латентность), это позволило бы насытить векторный сумматор FP с половиной полосы пропускания памяти. Как-будто, это было в значительной степени стиранием, возможно, из-за накладных расходов на вещание.
Кроме того, это довольно глупо. N_TIMES - это просто повторение make-work. На самом деле мы не хотим оптимизировать многократное выполнение одинаковой работы. Если мы не хотим побеждать в таких глупых заданиях. Путь к исходному уровню для этого состоит в том, чтобы увеличить 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 иногда сделает это за вас.
Более общий метод называется блокировкой кеша или черепицей цикла. Идея состоит в том, чтобы работать с вашими входными данными в небольших блоках, которые вписываются в кеш. В зависимости от вашего алгоритма, можно сделать несколько этапов вещи на куске, а затем повторить для следующего фрагмента, вместо того, чтобы каждый цикл цикла на весь вход. Как всегда, как только вы узнаете правильное имя для трюка (и что оно вообще существует), вы можете загрузить большую часть информации.
Вы можете использовать правила-юриста для помещения цикла interchanged внутри блока if (i == 0) в той части кода, которую вы можете изменить. Он по-прежнему будет делать то же количество дополнений, но в более оптимальном для кеша порядке.