В предыдущих посте Основные проблемы влияющие на производительность ... я написал о том, что анализ производительности — задача сложная и ее нельзя в большинстве случаев решить без анализа исходного кода, без изучения того, как реализован тот или иной алгоритм и без знания вычислительной архитектуры, на которой приложение будет выполняться. В этом посте я хочу показать пример оптимизации программы, базирующийся на идее разбиения цикла.
Основная идея цикловых оптимизаций
Циклы исключительно важны в вычислительных программах и как правило выполнения различных циклов и являются горячими функциями приложения, т.е. функциями отнимающими много времени при исполнении. Первые вычислительные архитектуры в основном предназначались для высокопроизводительных вычислений с широким использованием различных циклов и поэтому идея их оптимизации владеет умами уже очень давно и различных цикловых оптимизаций предложено довольно много. Основная идея цикловых оптимизаций состоит в изменении порядка выполняемой работы. Если на уровне вычислительного ядра перестановка инструкций служит для улучшения работы вычислительного конвейера, то при выполнении цикловых оптимизаций перестановка утверждений осуществляется с более глобальными целями, такими как улучшение работы подсистемы памяти, осуществление векторизации и автопараллелизации, улучшении инструкционного параллелизма, переиспользование данных, улучшении работы предсказателя ветвлений и т.д. Поскольку различных факторов много, то у компилятора должен существовать некий эврестический механизм, который оценивает возможные плюсы и минусы и принимает решение о том делать или нет ту или иную высокоуровневую оптимизацию.
Простой пример эффективности цикловых оптимизаций
Рассмотрим простой пример с популярной оптимизацией разбиение цикла (loop distribution), которая обычно тесно увязана с обратной оптимизацией объединения циклов (loop fusion), и посмотрим, как оптимизация влияет на производительность некоего синтетического теста. Синтетический тест абсолютно бесмысленный, но поможет вскрыть определенные закономерности работы вычислительного ядра. Массивы реализованы как векторы указателей. Под макросом PERF начальный большой цикл разбит на три цикла, каждый из которых содержит часть взаимосвязанных вычислений из начального цикла.
#include <stdio.h>
#include <stdlib.h>
#define N 1000
int main() {
int i,j,rep;
int volatile nnn;
float **a1,**a2,**a3;
float **b1,**b2, **b3;
double **c1, **c2, **c3;
double sum1,sum2,sum3;
nnn = 2000; // upper bound for repeat loop
.... // memory allocation and initialization
for(rep=0;rep<nnn;rep++) {
#ifndef PERF
for(j=1;j<N-1;j++)
for(i=0;i<N;i++) {
sum1 = sum1 + (a1[j][i]+a2[j][i]+a3[j][i]);
sum2 = sum2 + (b1[j][i]+b2[j][i]+b3[j][i]);
sum3 = sum3 + (c1[j][i]+c2[j][i]+c3[j][i]);
sum1 = sum1 - (a1[j-1][i]+a2[j-1][i]+a3[j-1][i]);
sum2 = sum2 - (b1[j-1][i]+b2[j-1][i]+b3[j-1][i]);
sum3 = sum3 - (c1[j-1][i]+c2[j-1][i]+c3[j-1][i]);
sum1 = sum1 - (a1[j+1][i]+a2[j+1][i]+a3[j+1][i]);
sum2 = sum2 - (b1[j+1][i]+b2[j+1][i]+b3[j+1][i]);
sum3 = sum3 - (c1[j+1][i]+c2[j+1][i]+c3[j+1][i]);
}
#else
for(j=1;j<N-1;j++)
for(i=0;i<N;i++) {
sum1 = sum1 + (a1[j][i]+a2[j][i]+a3[j][i]);
sum1 = sum1 - (a1[j-1][i]+a2[j-1][i]+a3[j-1][i]);
sum1 = sum1 - (a1[j+1][i]+a2[j+1][i]+a3[j+1][i]);
}
for(j=1;j<N-1;j++)
for(i=0;i<N;i++) {
sum2 = sum2 + (b1[j][i]+b2[j][i]+b3[j][i]);
sum2 = sum2 - (b1[j-1][i]+b2[j-1][i]+b3[j-1][i]);
sum2 = sum2 - (b1[j+1][i]+b2[j+1][i]+b3[j+1][i]);
}
for(j=1;j<N-1;j++)
for(i=0;i<N;i++) {
sum3 = sum3 + (c1[j][i]+c2[j][i]+c3[j][i]);
sum3 = sum3 - (c1[j-1][i]+c2[j-1][i]+c3[j-1][i]);
sum3 = sum3 - (c1[j+1][i]+c2[j+1][i]+c3[j+1][i]);
}
#endif
}
printf("%lf %lf %lf n",sum1,sum2,sum3);
... //deallocation
}
Я буду использовать интеловский компилятор с опцией –O1. Про эту опцию компилятор говорит (icl –help):
/O1 optimize for maximum speed, but disable some optimizations which increase code size for a small speed benefit
По факту, с этой опцией компилятор не делает цикловых оптимизаций, в том числе автовекторизации. Поэтому он не будет вмешиваться в предлагаемый эксперимент.
В результате компиляции с опцией –DPERF и без нее будет создано два исполняемых файла.
icl -O1 distr.c -Fedistr.exe
icl -O1 -DPERF distr.c -Fedistr2.exe
На моей лабораторной машине c Windows Server 2008 R2 Enterprise и процессором Intel Xeon X5570 время выполнения получившихся тестов следующее:
distr.exe: 38.8 sec
distr2.exe: 31.2 sec
Производительность второго цикла существенно лучше. Давайте посмотрим на General Exploration программы, сделанный Intel VTune Amplifier XE2013 и сравним результаты для обоих программ.
Интересно, в чем же тут дело?
Есть специальное руководство «Performance Analysis Guide for Intel@ Core TM i7 Processor and Intel@ Xeon TM 5500 processors” в котором можно изучить методы анализа работы вычислительного ядра. VTune Amplifier также содержит краткое описание различных событий. Поэтому если есть вопросы по значению некоторых приводимых здесь названий, то можно обратиться к этой информации. Также буду рад, если кто-то меня поправит или даст дополнительные идеи о том, за счет чего оптимизация цикла показывает такой эффект.
При сравнении отчетов можно отметить факт, что INST_RETIRED.ANY у обоих вариантов программы примерно одинаковое. Т.е. здесь не произошло никаких чудес (типа векторизации) и количество выполненной работы в обоих случаях примерно равно. Но при этом в оптимизированном варианте CPI Rate значительно лучше и нужно понять за счет чего это произошло.
Интересно появление LLC Load Misses Serviced By Remote DRAM в одном из вариантов программы. По идее, эта проблема характерна для многопоточных приложений и связана с использованием вычислительным ядром памяти принадлежащей другому ядру, что характерно для вычислительных архитектур с неравномерным доступом к памяти (NUMA). В данном случае эта ситуация появляется из-за миграции вычислительного процесса по разным вычислительным ядрам. Звезды сложились так, что вторая программа мигрировала по вычислительным ядрам менее удачно. Можно привязать программу к определенному вычислительному ядру, чтобы эти вызываемые операционной системой переключения между ядрами не влияли на результаты. Следующие эксперименты сделаны с привязкой к конкретному ядру.
Я не буду пользоваться стандартным Memory Access анализом, различные события для которого определены для архитектуры Nehalem в VTune Amplifier, а возьму и составлю свой набор событий и сравню их для двух модификаций моей программы. У меня получился примерно следующий анализ:
Удивляет то, что изменилось количество загрузок из памяти (MEM_INST_RETIRED.LOADS). Однако, если сравнить ассемблер обоих вариантов программы, то количество инструкций работы с памятью в первоначальном варианте действительно больше. Это объясняется тем, что при одновременной работе с большим количеством массивов не хватает регистров для хранения промежуточных результатов и происходит постоянный обмен между стеком программы и регистрами. Наверное, эта проблема не должна быть критической, поскольку стек из-за постоянного использования будет в кэше.
Если вспомнить организацию подсистемы памяти, то у вычислительного ядра существует L1 кэш данных размером 32KB. В первоначальном варианте программы на каждой итерации мы работаем с большим количеством различных потоков данных. Т.е. на каждой итерации нам нужно читать данные из 27 мест a1[j-1][i],a1[j][i],a1[j+1][i],a2[j-1][i],…,c1[j+1][i]. Но часть этих данных должна быть загружена в подсистему кэшей на предыдущей итерации по j. Новых данные подгружаются для a1[j+1][:],a2[j+1][:],a3[j+1][:],b1[j+1][:],...,c3[j+1][:]. Размер float — 4 байта, размер double – 8 байтов. Количество элементов в строке матрицы -1000. Получаем, что в подсистему кэшей на каждой итерации должно быть помещено 4000*3+4000*3+8000*3=~47KB данных. Очевидно, что в первоначальном варианте программы на каждой итерации полностью обновляется L1D кэш. В модифицированном варианте на каждой итерации обновляется ~12KB для вещественных матриц и ~24KB для вещественных двойной точности, т.е. данные зачитанные на предыдущих итерациях должны частично сохраниться в памяти. Это можно увидеть сравнив соотношение событий L1D_CACHE_LD.I_STATE (промахов по кэшу) к L1D_CACHE_LD.MESI (общему числу обращений к кэшу). В «медленном» варианте это соотношение равно ~13.6%. В «быстром» варианте — ~7%. В результате у модифицированного варианта меньше задержек с большими временами ожидания.
На производительность данного вычисления также должны оказывать влияние устройства аппаратной предвыборки. Существуют устройства предвыборки, которые работают с L1 и L2 кэшем. Из документации можно почерпнуть информацию о том, что они не всемогущи и на разных архитектурах поддерживают разное количество потоков данных. Обращение к определенной строке массива, типа a[j][i] и есть такой поток данных. После достижения определенного числа одновременно обслуживаемых потоков должны появиться потоки, для которых предвыборка не работает. Более того, возможно, при большом количестве потоков аппаратная предвыборка вообще перестанет работать. Поэтому, я создал новый вид анализа, в который поместил события, связанные с работой L1D и L2 устройств аппаратной предвыборки:
На мой взгляд, этот анализ показывает следующее. Количество запросов (L1D_PREFETCH.REQUESTS), которые генерятся L1D устройством предвыборки в «хорошем» случае даже выше, чем аналогичный показатель в «медленном» случае. Хоть это и странно, но подтверждает с запасом мысль о том, что префетчер ограничен в возможностях обслуживать потоки данных. Что касается устройств предвыборки для L2 кэша, то тут есть два интересных события L2_DATA_RQSTS.DEMAND.MESI (L2 data demand requests) и L2_DATA_RQSTS.PREFETCH.MESI (All L2 data prefetchers).
Т.е. часть обращений к памяти обслуживается устройством предвыборки, а вторая часть обращений к памяти оказывается для вычислительного ядра сюрпризом. И здесь опять наблюдается интересная картина. В «хорошем» случае устройство предвыборки создает значительно больше упреждающих запросов. Также важно, что «плохом» случае почти в два раза больше необслуженных устройствами предвыборки запросов.
Пара цикловых оптимизаций объединение/разбиение циклов зависит от массы условий. Вполне вероятно, что в случае маленьких массивов, которые отлично размещаются в кэше, первый вариант оказался бы быстрее за счет наличия большего количества независимых вычислений на каждой итерации и за счет сокращения ветвлений. В данном случае анализ значительно упрощается за счет того, что нам известен размер массивов, известна вычислительная система на которой проводится эксперимент и т.д.
А что делает в этом случае компилятор?
Пришло время проверить, а что в этом случае делает оптимизирующий компилятор Интел? Чтобы поставить нас в равные условия заберем у компилятора возможность заниматься автовекторизацией. ( Здесь хочется поставить подмигивающий смайлик.)
icl -O2 /Qvec- distr.c -Fedistr_comp.exe
time distr_comp.exe
…
CPU time for command: 'distr_comp.exe'
real 41.799 sec
Вот тебе и на – компилятор с опцией –O1 показывает лучшую производительность чем с –O2. Не совсем понятно, как был оптимизирован тест. Существует опция /Qopt_report. Если ей воспользоваться, то можно увидеть, что компилятор сделал разбиение цикла:
LOOP DISTRIBUTION in _main at line 54
С помощью дополнительного анализа (возможность использовать дампы) можно понять, как примерно было сделано разбиение:
for(j=1;j<N-1;j++) {
for(i=0;i<N;i++) {
sum3 = sum3 + (c1[j][i]+c2[j][i]+c3[j][i]);
sum3 = sum3 - (c1[j-1][i]+c2[j-1][i]+c3[j-1][i]);
sum3 = sum3 - (c1[j+1][i]+c2[j+1][i]+c3[j+1][i]);
}
for(i=0;i<N;i++) {
sum1 = sum1 + (a1[j][i]+a2[j][i]+a3[j][i]);
sum2 = sum2 + (b1[j][i]+b2[j][i]+b3[j][i]);
sum1 = sum1 - (a1[j-1][i]+a2[j-1][i]+a3[j-1][i]);
sum2 = sum2 - (b1[j-1][i]+b2[j-1][i]+b3[j-1][i]);
sum1 = sum1 - (a1[j+1][i]+a2[j+1][i]+a3[j+1][i]);
sum2 = sum2 - (b1[j+1][i]+b2[j+1][i]+b3[j+1][i]);
}
}
Такие ситуации я называю «горе от ума». Очевидно, что с одной стороны у компилятора творческий потенциал налицо. Он разобрался и выбрал в одну группу зависящие вычисления и даже зачем-то вынес вычисление sum3 вперед. Но почему-то ограничился только разбиением внутреннего цикла, сведя на нет все возможные выгоды от улучшения локальности данных, с которыми работает этот цикл. Количество различных переходов увеличилось, а улучшение локальности данных при такой оптимизации не было достигнуто. Второй цикл выглядит громоздким и с точки зрения оценки количества потоков данных.
Чтобы как то подсластить компилятору эту горькую пилюлю, посмотрим что даст в этом случае автовекторизация:
icl -O2 distr.c -Fedistr_compvec.exe
CPU time for command: 'distr_compvec.exe'
real 24.020 sec
Заключение:
В этом маленьком исследовании я только пытался намекнуть, что анализ производительности довольно интересное и замысловатое занятие. Количество факторов, влияющее на скорость работы программы достаточно велико. Оценить вклад вносимый в производительность программы тем или иным фактором очень непросто, даже если у вас есть возможность измерять различные внутрипроцессорные события. В теории, для получения оптимального результата эврестический механизм компилятора должен анализировать массу каких-то закономерностей и это не включая сюда сложность доказательства правомерности той или иной оптимизации. При этом компилятор часто не имеет представления о данных, с которыми будет работать программа и о вычислительной системе, на которой эта программа будет выполняться.
Автор: andrei_an
