Метод недопустимой операции:
Разделить кошку на ноль,
после чего она станет бесконечно большой,
так что её будет невозможно упустить.
[АбсурдопедиЯ]
Пытаясь найти проблему с производительностью относительно простого кода, я вспомнил несколько нелепых методов решения, описанных на Абсурдопедии, для задачи поиска черной кошки в темной комнате. Как ни странно, мне очень помогло последовательное использование трех методов, которые можно найти по ссылке: Прагматизм, Метод дихотомии и Метод тыка.
Итак, имеем задачу последовательной перестановки байтов в каждом слове массива (big-endian <-> little-endian) и суммирования всех слов в одно (reduction). Оставим пока в стороне задачу распараллеливания, ибо ее решение близко к тривиальному, и для нас пока не представляет интереса.
Прямая (в лоб) имплементация алгоритма обычно называется наивной. Это наверное от того, что мы, программисты, навивно полагаемся на компилятор, который сгенерирует если не оптимальный, то близкий к этому код, и дальше оптимизировать будет уже нечего. Впрочем, как мы увидим ниже в дизассемблере, компилятор производит довольно простую последовательность инструкций, по-идее, не должную вызывать особых проблем с производительностью на платформе x86.
void init()
{
int i;
for (i = 0; i < 1024; i++)
buf[i] = i;
}
unsigned int change_endianess(char *big)
{
char temp;
temp = big[0];
big[0] = big[3];
big[3] = temp;
temp = big[1];
big[1] = big[2];
big[2] = temp;
return *(unsigned int *)big;
}
void reduce()
{
int i, n;
unsigned int sum = 0;
init();
for (n = 0; n < ITER_NUM; n++){//repeat itarations
for (i = 0; i < 1024; i++){
sum += change_endianess((char *)(buf+i));}}
printf ("Sum is %d\n", sum);
}
main ()
{
reduce();
}
Как выражаются наши остроумные маркетологи, «оценка производительности без профилировки является гаданием». Поэтому запускаем General Exploration профиль в VTune Amplifier XE для того, чтобы оценить, насколько эффективно этот код выполняется на микроархитектуре Core i7 (codename Nehalem). Не забываем указать опции -Zi и /debug:inline-debug-info для Intel Compiler (Windows), чтобы сохранить отладочную информацию и информацию о строках функций, которые были «заинлайнены» (как правильно сказать по-русски, «inlined»?). Последняя опция очень полезна, так как позволяет VTune Amplifier XE атрибутировать значения счетчиков прямо по строкам вложенной функции. Это новая фича VTune; ее можно и отключать, чтобы результаты отображались только напротив вызова фунции.
Так как тест отрабатывает довольно быстро (несмотря на выбранное достаточно большое количество итераций), полезно в настройках проекта VTune включить опцию Allow Multiple Runs, что заставит инструмент запускать тест несколько раз, собирая счетчики группами. В противном случае, счетчики будут мультиплексироваться, и при небольшом времени выполнения теста точность может пострадать.
Из результатов понятно, что ничего не понятно. Видно, что производительность исполнения кода в функции reduce довольно далека от совершенства, так как CPI=1.67 более чем в 6 раз больше оптимального 0.25. Нет, это конечно не значит, что у нас потенциал увеличения производительности кода в 6 раз, но добиться блее низкого CPI на таком простом цикле вполне можно было бы. Однако, почему CPI высок, сказать трудно. Метрика Retire Stalls примерно равна 0.7 и говорит нам о том, что во время завершения выполнения инструкций наблюдаются простои конвеера в 70% тактов. Остальные показатели производительности, судя по результатам собранного профиля, в норме. Более того, зная, что в большинстве случаев причиной проблем производительности бывает подсистема памяти, можно специально запустить Memory Access анализ. Но он покажет тоже самое – проблем с памятью нет. Впрочем, код такой простой, а доступ к памяти такой последовательный, что запускать анализ памяти даже и не стоило. По тем же причинам нам не поможет и Branch Analysis.
Начинаем искать черную кошку в темной комнате, вернее причину провала производительности в микроархитектуре процессора.
Применяем улучшенный метод поиска кошки «Прагматизм». Изначально необходимо определиться, что мы получим, если найдем эту кошку, и стоит ли ее из-за этого искать. Какой именно у нас потенциал, помогают оценить метрики Execution Stalls и Retire Stalls.
Первая мертика Execution Stalls — соотношение между значениями счетчиков UOPS_EXECUTED.CORE_STALL_CYCLES и UOPS_EXECUTED.CORE_ACTIVE_CYCLES.
Счетчик событий UOPS_EXECUTED.CORE_STALL_CYCLES измеряет количество тактов простоя в вычислительной части конвейера процессора, когда диспетчер операций (Reservation Station) не назначает выполнение операций ни на один порт.
Счетчик событий UOPS_EXECUTED.CORE_ACTIVE_CYCLES соответственно считает циклы, когда хотя бы в одном из четырех вычислительных портов и двух портов чтения/записи есть микрооперация для исполнения.
Соотношение UOPS_EXECUTED.CORE_STALL_CYCLES / (UOPS_EXECUTED.CORE_ACTIVE_CYCLES + UOPS_EXECUTED.CORE_STALL_CYCLES) позволит нам судить о том, какая часть времени выполнения функции соответствовала простою вычислителя, и каков наш потенциал увеличения производительноти, если мы каким-либо способом добъемся снижения времени простоя процессора.
Кстати, сумма эти счетчиков должна давать значение счетчика всех тактов CPU_CLK_UNHALTED.THREAD. И в VTune для автоматического вычисления метрики Execution Stalls используется соотношение UOPS_EXECUTED.CORE_STALL_CYCLES / CPU_CLK_UNHALTED.THREAD.
В нашем случае, соотношение примерно равно 0.24 (четверть тактов простоя из общего числа), и это значит, что, если устранить простои, то потенциально можем увеличить пропускную способность вычислителя по крайней мере на четверть – и это только для одного из четырех слотов.
Вторая метрика Retire Stalls – это соотношение между значениями UOPS_RETIRED.STALL_CYCLES / CPU_CLK_UNHALTED.THREAD, показывающая какая часть времени от общего количества тактов соответствует состоянию, когда ни одна микрооперация не завершается (retired), хотя теоретически, могло бы завершаться до 4 операций за такт.
Это значит, что при 70% простоя, если мы хорошо будем искать кошку, устранив причину ожидания исполнения операций, можно надеяться на ускорение выполнения программы по крайней мере в 2.3 раза.
Пользуясь здравым смыслом, делаем вывод, что ради такого ускорения выполнения алгорима, можно и попытаться.
Чтобы найти, где у нас проблема, используем второй метод поиска кошки — «Метод дихотомии»: последовательно делим комнату на равные части, вернее разделяем стадии конвеера процессора на логические части, где можно пытаться искать причину проблемы. Этот метод хорошо описан в Intel® 64 and IA-32 Architectures Optimization Reference Manual, в разделе “Using Performance Monitoring Events” как «Performance Events Drill-Down and Software Tuning Feedback Loop”. Вот его несколько упрощенное представление:
Суть метода состоит в том, чтобы последовательно отделять части конвеера, находя с помощью соответствующих счетчиков место, где происходит его простой, то есть незанятость продвижением микроопераций (bottleneck). Первоначально необходимо определить, выполняются ли микроинструкции в конвеере. Если да, то заканчивается ли их выполнение успехом (Retire). В случае выполнения незаканчивающихся изменением состояния процессора операций (Non-Retired), имеет место ошибочное предсказание и выполнение не тех ветвлений программы (Bad Speculation). В нашем же случае мы имеем дело с простоем конвеера, и далее необходимо померить, возникают ли проблемы с выделением ресурсов процессора (внутренние регистры, буферы, и т.д.). Если нет, то это будет значить, что процессору не хватает инструкций для исполнения, и проблема во Frond-End, то есть там, где инструкции выбираются из кэша инструкций, декодирутся, и ставятся в очередь исполненя. Если да, то проблема где-то в самой темной части комнаты, называемой Back-End, где производятся вычисления, и где могут быть проблемы как с самими вычислителями, так и с диспетчеризацией микроинструкций, выделением буферов, ожиданием данных из памяти, и так далее.
Определить, есть ли Allocation Stalls очень просто. Нужно посмотреть показания счетчика с именем RESOURCE_STALLS.ANY. Переключив viewpoint VTune на Hardvare Event Count и глядя на показания этого счетчика (значение, соизмеримое с общим количествои тактов CPU), понимаем, что именно нехватка каких-то ресурсов, согласно счетчику, может идентифицировать проблему в нашем коде.
Согласно Абсурдопедии, Метод дихотомии должен привести к делению комнаты до тех пор, пока кошка не сконцентрируется в точку. Однако, для микроархитектуры процессора возможности метода не безграничны и на определенном этапе заканчиваются. И здесь, как нельзя лучше, применяется «Метод тыка» – один из самых эффективных научных методов, в случаях когда другие, более строгие и регулярные методы, уже не помогают.
Нам необходимо перемерить все возможные счетчики, которые харектеризуют нехватку ресурсов. Их немного, и нужно всего лишь заменить расширение счетчика ANY, на конкретные ресурсы. Для моего мобильного варианта Core i7: RESOURCE_STALLS.LOAD, RESOURCE_STALLS.STORE, RESOURCE_STALLS.ROB_FULL, RESOURCE_STALLS.RS_FULL, RESOURCE_STALLS.OTHER эти данные можно собрать отдельно, а можно и найти в результатах профиля General Exploration. Суммарные показатели намекают нам, что существует проблема остановки продвижения конвеера из-заполнения ROB-буфера, и нехватки буфера записи данных.
В Store Buffer складываются данные для записи в память. Задержки выполнения операций будут наблюдаться, если следует много инструкций записи, перемежающихся с чтением. Reorder Buffer (ROB) содержит в себе микрооперации, которые ожидают окончания исполнения, а также выполненые операции, которые изменяют состояние процессора в порядке их исполнения (in-order). Важно определить, при ожидании какой инструкции буфер был переполнен поступающими микрооперациями и блокировал дальнейшую работу конвеера.
Здесь нам поможет Source View вместе с дизассемблированием — Assembly View. Для экономии места расположим их отдельно, хотя в VTune они находятся рядом.
Как видно по значению счетчика CPU_CLK_UNHALTED.TREAD, большинство тактов попало на цикл выполнения суммирования слов, а не на функцию перестановки. Смещение данных на строку цикла for несколько запутывает, но это всегда происходит с циклами. Результаты, относящиеся к телу цикла могут сместиться на его заголовок, если тело цикла небольшое. Чтобы убедиться в этом, посмотрим на дизассемблированный вариант функции.
Интересным для нас является Basic Block 5: он представляет собой цикл выполнения операции перестановки байтов и суммирования слов – так сгенерировал инструкции компилятор. Начиная с адреса 0х4010d0 по 0x401105 находятся инструкции перестановки байтов в слове. По адресу 0х40110с – как раз искомая инструкция суммирования значения слова в регистре edx. Опять же, за счет смещения (skid) результаты отобразились на инструкции inc ниже, которая не может занимать столько тактов. Что интересно, эта же инструкция суммирования add собрала наибольшее количество показаний счетчиков Resource Stalls. Забегая вперед и применяя все тот же Метот тыка, отметим, что убрав из комнаты кошку, то есть эту операцию суммирования, мы точно узнаем, что комната пуста, а проблемы с Resource Stalls и производительностью исчезли.
Так в чем же проблема с этой инструкцией, вернее с несколькими микрооперациями, из которых она состоит (чтение адреса, чтение данных из памяти и операция суммирования в регистре)? Тут, как всегда есть одна хитрость: нужно либо хорошо знать особенности реализации выгрузки-загрузки данных в микроархитектуре, либо использовать несколько другой микропроцессор. Вместо нашего мобильного Core i7 (code name Nehalem) померяем на платформе c процессором Xeon либо на процессоре с кодовым именем Westmere (так сказать, возьмем комнату пооснасщеннее), в которых дополнительно можно получить счетчик LOAD_BLOCK.OVERLAP_STORE. Он будет просто зашкаливать на asm-инструкции add. Вообще этот счетчик сигнализирует о заблокированных по разным причинам микрооперациях загрузки данных (load). Самая распространенная причина такой сигнализации состоит в том, что микрооперация load заблокирована предыдущей микрооперацией записи (store):
— Некоторые байты читаемых данных были в предыдущей операции записи, а некоторые нет;
— Байты слова чтения те же, что и для предшествующей записи, и слово записи выровнено по своему размеру, при этом читаются 1-2 байта не выровненные по началу слова записи, либо 4-8 байт, и не выровненные с данными записи;
— Байты слова чтения те же, что и для предшествующей записи, но слово записи не выровнено по своему размеру, и чтение не выровнено по началу слова записи.
Теперь присмотримся внимательнее к последовательности asm-инструкций, реализующих цикл перестановки байт и сумиирования. Здесь происходит ни что иное, как чтение слова с соответствующим побайтовым смещением из памяти в регистры ebx и ecx (временные значения) и побайтовая запись данных из нижней части регистров bl и cl в память. Пока мы побайтно читаем и пишем в память, никаких проблем нет. Однако, стоит нам попытаться загрузить целое слово из памяти (микрооперация load в инструкции add) по тому же адресу слова, что в предыдущей операции записи, как эта операция загрузки будет заблокирована. Процессор не может передать все слово целиком в буфер чтения сразу после записи этого слова по частям – приходится ждать. Такая проблема называется Blocked Loads Due to No Store Forwarding. Запомните ее, так как она будет часто встречаться, если вы активно работаете с байтами внутри слов.
Необходимо отметить, что, исследуя проблему на данной мобильной платформе, пришлось применять Модифицированный Метод тыка, так как собранные счетчики явно не говорили о наличии No Store Forwarding. Мы притянули сюда shrink-версию микроархитекуры Nehalem – Westmere, либо Xeon; а профиль General Exploration не содержал счетчика событий LOAD_BLOCK.OVERLAP_STORE. Следующее поколение процессоров — 2nd generation Intel® Core™ processor с кодовым именем SandyBridge (собственно уже являющееся текущим поколением) — содержит специальный счетчик LD_BLOCKS_STORE_FORWARD, который есть в VTune-профиле General Exploration для SandyBridge, и который напрямую укажет нам на проблему.
Теперь осталось подумать, как исправить код и решить проблему производительности. Из описания причин ее возникновения понятно, что нужно сделать так, чтобы загрузка слова из памяти непосредственно не следовала после его побайтной записи по тому же адрусу. Значит, чтобы избежать задач поиска «этого котэ» в будущем, нужно разделить комнату и кошку: вынесем операцию суммирования слов массива в отдельный цикл.
void reduce()
{
int i, n;
unsigned int sum = 0;
init();
for (n = 0; n < ITER_NUM; n++)
{
for (i = 0; i < 1024; i++)
change_endianess((char *)(buf+i));
for (i = 0; i < 1024; i++)
sum += buf [i];
}
printf ("Sum is %d\n", sum);
}
Разницу времени выполнения программы можно видеть, сравнив результаты профилировки.
Остался один небольшой вопрос, почему функция ускорилась более чем в 3 раза, тогда как в начале мы определили, что циклов простоя всего 70 процентов? Дело в том, что такое количество циклов процессор простаивает при данном наборе инструкций, использованных компилятором. Разделив в исходном коде циклы перестановки байтов и суммирования, мы помогли компилятору автоматически векторизовать последний цикл, и он заменил обычные скалярные инструкции суммирования и чтения-записи на векторные SIMD-инструкции, которые на 32-битной платформе выполняются в 4 раза быстрее для данных типа int32. Помните потенциал, посчитанный по CPI?
