Почему моя программа не может достичь предела пропускной способности инструкций сложения целых чисел?
Я прочитал главу 5 CSAPP 3e. Я хочу проверить, могут ли методы оптимизации, описанные в книге, работать на моем компьютере. Я пишу следующую программу:
#define SIZE (1024)
int main(int argc, char* argv[]) {
int sum = 0;
int* array = malloc(sizeof(int) * SIZE);
unsigned long long before = __rdtsc();
for (int i = 0; i < SIZE; ++i) {
sum += array[i];
}
unsigned long long after = __rdtsc();
double cpe = (double)(after - before) / SIZE;
printf("CPE is %f\n", cpe);
printf("sum is %d\n", sum);
return 0;
}
и он сообщает, что CPE составляет около 1,00.
Я преобразовываю программу, используя метод развертывания цикла 4x4, и это приводит к следующей программе:
#define SIZE (1024)
int main(int argc, char* argv[]) {
int sum = 0;
int* array = malloc(sizeof(int) * SIZE);
int sum0 = 0;
int sum1 = 0;
int sum2 = 0;
int sum3 = 0;
/* 4x4 unrolling */
unsigned long long before = __rdtsc();
for (int i = 0; i < SIZE; i += 4) {
sum0 += array[i];
sum1 += array[i + 1];
sum2 += array[i + 2];
sum3 += array[i + 3];
}
unsigned long long after = __rdtsc();
sum = sum0 + sum1 + sum2 + sum3;
double cpe = (double)(after - before) / SIZE;
printf("CPE is %f\n", cpe);
printf("sum is %d\n", sum);
return 0;
}
Обратите внимание, что я опускаю код для обработки ситуации, когда SIZE не кратно 4. Эта программа сообщает, что CPE составляет около 0,80.
Моя программа работает на AMD 5950X, и, согласно руководству по оптимизации программного обеспечения AMD (https://developer.amd.com/resources/developer-guides-manuals/), инструкция целочисленного сложения имеет задержку 1 цикл и производительность 4 инструкции за такт. Он также имеет блок загрузки-сохранения, который может выполнять три независимые операции загрузки одновременно. Мое ожидание CPE составляет 0,33, и я не знаю, почему результат намного выше.
Мой компилятор gcc 12.2.0. Все программы компилируются с флагами -Og.
Я проверил ассемблерный код оптимизированной программы, но ничего полезного не нашел:
.L4:
movslq %r9d, %rcx
addl (%r8,%rcx,4), %r11d
addl 4(%r8,%rcx,4), %r10d
addl 8(%r8,%rcx,4), %ebx
addl 12(%r8,%rcx,4), %esi
addl $4, %r9d
.L3:
cmpl $127, %r9d
jle .L4
Я предполагаю, что по крайней мере 3 из 4 addl инструкций должны выполняться параллельно. Однако результат программы не соответствует моим ожиданиям.
Также заполните свой ввод, чтобы, возможно, избежать ошибки страницы и проверить результаты (и избежать неожиданной оптимизации). Обратите внимание, что инструкции SIMD могут делать это намного эффективнее. (Кстати, это печально, Zen не поддерживается uiCA)
@JérômeRichard: Или просто используйте пространство стека, инициализированное или нет. (Возможно, со встроенным asm("" : "=m"(array)), чтобы сообщить компилятору, что он был написан, без фактического запуска каких-либо инструкций для его записи.
Не используйте -Og, это оптимизация для отладки или что-то в этом роде. Используйте -O3.
@Lundin: OP не пытается сравнить C, они пытаются создать скалярный цикл микротестирования asm, который соответствует их исходному коду C, по какой-то причине фактически не записывая asm вручную. -Og вроде работает для этого, и было бы хорошо, если бы они использовали size_t, ptrdiff_t или uintptr_t для своего счетчика цикла, чтобы избежать movslq внутри цикла. Они не хотят, чтобы автоматическая векторизация с paddd выполняла четыре 32-битных сложения в одной инструкции, они пытаются измерить ограничения пропускной способности конвейера ЦП для скаляра add r32, r/m32.
@Lundin: Конечно, просмотр asm должен быть шагом 1 для такого рода микробенчмаркинга, а не там, где вы обращаетесь за объяснением после того, как время не соответствует вашим ожиданиям, поэтому то, что я описал в своем предыдущем комментарии как действительный подход к использование -Og или -O1 или -O2 -fno-tree-vectorize может не соответствовать мышлению OP, и они просто собирались предположить, что компилятор сделал то, что они ожидали, если бы числа сработали...
Ответы 1
cmpl $127, %r9d — это небольшое количество итераций по сравнению с rdtsc накладными расходами и неправильным предсказанием ветвления при выходе из цикла, а также временем, за которое ЦП разгоняется до максимальной частоты.
Кроме того, вы хотите измерять тактовые циклы ядра, а не эталонные циклы TSC. Поместите цикл в статический исполняемый файл (для минимальных затрат на запуск) и запустите его с помощью perf stat, чтобы получить основные часы для всего процесса. (Например, Может ли MOV для x86 быть «бесплатным»? Почему я вообще не могу воспроизвести это? или некоторые perf эксперименты, которые я опубликовал в других ответах.)
См. Идиоматический способ оценки эффективности?
Общее количество итераций от 10 до 1000 миллионов подходит, так как это все еще меньше секунды, и мы хотим измерить только стационарное поведение, а не эффект холодного кеша или холодного ветвления-предиктора. Или ошибки страницы. Накладные расходы на прерывания, как правило, составляют менее 1% в бездействующей системе. Используйте perf stat --all-user только для подсчета циклов и инструкций пользовательского пространства.
Если вы хотите сделать это над массивом (вместо того, чтобы просто удалить приращение указателя из asm), сделайте много проходов по небольшому (16 КБ) массиву, чтобы все они попали в кеш L1d. Используйте вложенный цикл или используйте and для переноса индекса.
Делая это, да, вы должны быть в состоянии измерить пропускную способность 3/такт add mem, reg на Zen3 и более поздних версиях, даже если вы оставите movslq накладные расходы и подобную чушь из вывода компилятора -Og.
Когда вы действительно проводите микротестирование, чтобы узнать информацию о пропускной способности одной формы одной инструкции, обычно проще написать ассемблер вручную, чем уговорить компилятор сгенерировать нужный вам цикл. (Если вы знаете достаточно asm, чтобы избежать ловушек, например, .balign 64 перед циклом просто для верности, чтобы избежать узких мест во внешнем интерфейсе.)
См. также https://uops.info/ , как они измеряют; для любого заданного теста вы можете щелкнуть ссылку, чтобы увидеть тело цикла asm для экспериментов, которые они проводили, и необработанные выходные данные счетчика производительности для каждого варианта теста. (Хотя я должен признать, что забыл, что означают MPERF и APERF для процессоров AMD; результаты для процессоров Intel более очевидны.) например. https://uops.info/html-tp/ZEN3/ADD_R32_M32-Measurements.html — это результаты Zen3, включающие тест из 4 или 8 независимых add reg, [r14+const] инструкций в качестве тела внутреннего цикла.
Они также протестировали режим индексированной адресации. С unroll_count=200 и без внутреннего цикла они получили идентичные результаты для MPERF / APERF / UOPS для 4 независимых добавлений с индексированным и неиндексированным режимами адресации. (Их циклы не имеют приращения указателя.)
Большое спасибо. Я только начал изучать информатику, поэтому ваш ответ содержит много информации для меня. Я не тороплюсь, чтобы изучить весь этот новый материал.
@drcxd: Да, микробенчмаркинг — это непросто, и может потребоваться некоторое время, чтобы понять все возможные подводные камни. Использование большого интервала измерения будет учитывать все небольшие накладные расходы, такие как измерения и другие накладные расходы при запуске из-за того, что процессоры «ленивы» экономить энергию, например, не работают на максимальной тактовой частоте все время. И особенно тот факт, что TSC работает с фиксированной частотой, независимо от тактовой частоты ядра ЦП, потому что высокоточный источник времени с низкими накладными расходами был более полезен для ОС, чем фактический счетчик циклов. (Что вы все еще можете получить с помощью RDPMC, если ядро программирует счетчики.)
@drcxd: несколько десятилетий назад компьютеры были намного проще. Никаких энергосберегающих изменений часов, эффекты кеша были намного менее выражены, а пропускная способность была ниже по сравнению с накладными расходами на прерывания/исключения (поэтому отказы страниц обходились относительно дешевле, хотя ядру все равно пришлось бы обнулить страницу для вас). Однако на компьютерах без виртуальной памяти у вас не будет даже программных ошибок страниц. Забегая вперед, скажем, что реальное аппаратное обеспечение очень сложное, поэтому вводные курсы упрощают многие вещи и/или работают с упорядоченным конвейером MIPS 1980 года.
Эта упрощенная модель сбивает меня с толку, когда что-то работает не так, как описано в учебнике.
Я бы не только подсчитывал циклы на операцию, но также попадал или не попадал в конвейер команд и кэш-память. Обычно современные компиляторы C отлично справляются с оптимизацией. Я ожидаю, что ручная оптимизация может быть хуже кода, оптимизированного компилятором.