Evg |
СОДЕРЖАНИЕ
Влияние конвейера на скорость исполнения кода
Запись от Evg размещена 02.05.2012 в 17:53
Показов 202253
Комментарии 38
|
1. Предисловие Одно из стандартных заблуждений начинающих программистов заключается в том, что многие думают, что чем короче исходник программы, тем быстрее программа будет работать. На самом деле для больших проектов первоочередным показателем является грамотное проектирование программы, а не количество строк кода. Но это всего лишь лирическое отступление, которое упомянуто к слову. В статье речь пойдёт немного о другом. Ещё одним из стандартных заблуждений является то, что если написать программу на ассемблере, то программа будет работать быстрее. В данной статье я не буду рассматривать какую-то большую программу, а рассмотрю лишь коротенькую функцию, которая выполняет весьма простое действие. При этом всё равно возникает подсознательное ощущение, что фрагмент кода будет работать быстро, если количество операций в нём минимизировать. Чисто на всякий случай. Кода речь идёт об intel'овских процессорах, то имеются в виду процессоры с intel'овской системой команд, коими, помимо процессоров Intel, являются и процессоры AMD 2. Постановка простой задачи В качестве постановки задачи я просто напишу коротенькую функцию, глядя на которую легко понять, что она делает.
Указанный "горячий" фрагмент кода является определяющим с точки зрения скорости работы, т.к. он будет исполняться часто, а потому паровоз операций, который стоит до цикла и после цикла на скорость работы программы не оказывают практически никакого влияния. Потому что эти операции будут работать только один раз за один вызов функции, против, условно говоря, нескольких тысяч исполнений операций, находящихся внутри цикла. Таким образом, глядя на ассемблерный код, дело выглядит так, что компилятор построил его самым оптимальны образом и сокращать тут просто нечего. Ну а теперь вопрос: а можно ли как-то ускорить этот код? 3. Каким образом происходит исполнение в процессоре В учебниках по ассемблеру обычно рассказывают только то, что делает та или иная машинная операция. Но довольно редко уделяется внимание тому, а каким же образом происходит выполнение операций в процессоре. И это вполне логично: мы имеем последовательность машинных команд на входе и имеем однозначный результат в виде значений в регистрах и в памяти на выходе, а каким образом это достигается - это дело процессора. Но на самом деле есть целая куча тонкостей, на хорошее понимание которых может потребоваться несколько лет. В данном разделе я ограничусь лишь поверхностным описанием тех сведений, которые необходимы для последующего понимания статьи. Кто-то эти моменты знает, а кто-то о них ещё не задумывался Все процессоры содержат исполнительное устройство - конвейер. Я видел в книгах, что про это немного рассказывают, но лишь для общего понимания. Современные процессоры имеют несколько конвейеров, которые могут исполнять команды параллельно. Можно две операции выполнять параллельно, или нельзя, решает аппаратура в процессе декодирования операции. Т.е., к примеру, если есть операция чтения из памяти в регистр %eax и операция инкрементации регистра %ebx, то эти две операции аппаратура может исполнять параллельно, поскольку они не конфликтуют по ресурсам. Но вот если бы вторая операция была операцией инкрементирования регистра %eax, то параллельное исполнение было бы невозможным: сначала нужно дождаться загрузки значения из памяти в %eax и только потом значение регистра инкрементировать. Есть ещё один момент, которому тоже нечасто уделяют внимание - это время исполнения операций. Простые операции типа целочисленного сложения-вычитания или битовой арифметики исполняются за один такт на любом более-менее приличном процессоре. Более сложные операции типа умножения или деления, как правило, исполняются несколько тактов (причём на разных процессорах время исполнения может сильно различаться). Связано это со сложным устройством апаратных элементов, которые исполняют данные операции. Операции чтения из памяти на любом современном высокоскоростном процессоре исполняется несколько тактов. Точной причины этого я не знаю, но есть некоторый минимальный порог времени, требуемый для прочтения данных из транзисторной матрицы: нужно вычислить, из какого места нужно данные прочитать, а потом ещё и прочитать сами данные. Дальше эти данные через шину нужно передать на процессор. На всех железках процессор и память представляют физически разведённые друг от друга устройства на общей плате. Чтение из памяти может исполняться несколько десятков или даже сотен машинных тактов. Именно из-за этого в современных процессорах присутсвует кэш (и даже не один), который физически находится на процессоре или очень близко к нему, а потому имеет более короткое время доступа к данным, но ограниченный размер памяти. И даже в тех случаях, когда данные оказываются в кэше первого уровня, их чтение занимает порядка трёх машинных тактов На этом данный раздел можно закончить. Мне кажется, что для общего понимания данных сведений вполне достаточно 4. Что происходит при исполнении нашей тестовой программы FIXME Данный раздел получился очень сложным для восприятия. Надо как-то его более внятно переписать Посмотрим, как исполняется на процессоре наша тестовая программа. Для удобства ещё раз приведу ассемблерный код "горячего" участка
5. Переписываем программу под параллельное исполнение При вычислении выражения "dst[i] = src[i] + 1023", как мы уже выяснили, практически ничего нельзя распараллелить по разным конвейерам, т.к. все операции цепочкой зависят друг от друга. Но если посмотреть, как исполняется не одна итерация цикла, а весь цикл, то легко можно заметить, что две соседние итерации цикла являются полностью независимыми. Т.е. при вычислении двух операторов "dst[0] = src[0] + 1023" и "dst[1] = src[1] + 1023" нету той цепочной зависимости, о которой писалось в разделе 4. А потому нашу функцию можно переписать по другому:
6. Результаты замеров В заключение статьи осталось померить тот выигрыш, который даёт нам оптимизированный вариант кода по сравнению с "простым". Итоговый вариант программы, на которой я проводил замеры, приведён ниже. Важные моменты, связанные с методикой измерения, отмечены в комментариях. Внутри функции copy имеются две реализации под макросом. По умолчанию работает "простой" вариант, при замене "#if 1" на "#if 0" будет работать оптимизированный вариант
Результаты получились следующие: Code Процессор: Intel Core2 Q9400, 2.66 ГГц ОС: linux Компилятор: gcc-4.1.2 Опции компилятора: -m32 -O3 "Обычный" вариант: time: 10.270 time: 10.050 time: 10.140 time: 10.100 time: 10.120 Оптимизированный вариант: time: 8.940 time: 8.960 time: 9.080 time: 8.950 time: 8.980 Code Процессор: AMD Athlon 64 X2, 2.8 ГГц ОС: windows Компилятор: borland builder 2007 Опции компилятора: те, что по умолчанию стоят в режиме RELEASE, 32-битный режим "Обычный" вариант: time: 10.015 time: 10.000 time: 10.000 time: 10.015 time: 10.000 Оптимизированный вариант: time: 8.799 time: 8.798 time: 8.799 time: 8.798 time: 8.783 Code Процессор: Sun UltraSPARC-III+, 1.2 ГГц ОС: solaris Компилятор: Sun cc Опции компилятора: -xarch=v8plusb -xO4 (32-битный режим) "Обычный" вариант: time: 10.020 time: 10.030 time: 10.020 time: 10.040 time: 10.030 Оптимизированный вариант: time: 8.830 time: 8.830 time: 8.840 time: 8.840 time: 8.840 Code Процессор: TI UltraSparc IIi, 400 МГц ОС: linux Компилятор: gcc-4.2.4 Опции компилятора: -m32 -mcpu=ultrasparc3 -O3 "Обычный" вариант: time: 10.310 time: 10.310 time: 10.310 time: 10.310 time: 10.320 Оптимизированный вариант: time: 8.340 time: 8.340 time: 8.340 time: 8.330 time: 8.340 Первым делом хочется сказать, что пример, рассматриваемый в данной статье - это всего лишь демонстрационный пример, на котором можно пощупать, как работает многоконвейерный процессор. Ни в коем случае данный пример не стОит рассматривать как рекомендацию к самостоятельному переписыванию циклов в подобном стиле. Компилятор, надлежащим образом настроенный, справится с задачей лучше, чем среднестатистический программист (см. этот, этот и этот посты в комментариях). Построить код лучше компилятора сможет разве что эксперт, хорошо понимающий работу конвейера FIXME Что-то ещё хотел сказать 8. Ссылки на темы, где обсуждался данный вопрос | ||||||||||||||||||||||||||||||||||||||||
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Всего комментариев 38
Комментарии
-
Внесём немного разнообразия в результаты
Подкрутил только значение LOOP до 160000
Видимо всё от того, что компилятор сам разворачивает "простой" цикл с использованием SSE (смотрел в листинг).Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
Процессор: Intel Core2 E6600, 2.4 ГГц ОС: linux (64 бита) Компилятор: gcc-4.5.3 Опции компилятора: -O3 "Обычный" вариант: time: 10.030 time: 10.030 time: 10.020 time: 10.040 time: 10.030 Оптимизированный вариант: time: 10.080 time: 10.070 time: 10.070 time: 10.210 time: 10.130
Запись от grizlik78 размещена 02.05.2012 в 18:28
-
Запись от Evg размещена 02.05.2012 в 19:57
-
Да, в 32-битном режиме картинка заметно другая. LOOP не стал менять, результаты на той же машине в той же системе.
По умолчанию в этом режиме SSE не используется. Если его разрешить, то результаты становятся ровнееCode 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
Процессор: Intel Core2 E6600, 2.4 ГГц ОС: linux (64 бита) Компилятор: gcc-4.5.3 Опции компилятора: -O3 -m32 "Обычный" вариант: time: 13.340 time: 13.360 time: 13.340 time: 13.360 time: 13.360 Оптимизированный вариант: time: 9.140 time: 9.160 time: 9.140 time: 9.160 time: 9.400
Наглядно развевается миф, что 64-битные программы работают быстрееCode 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
Процессор: Intel Core2 E6600, 2.4 ГГц ОС: linux (64 бита) Компилятор: gcc-4.5.3 Опции компилятора: -O3 -m32 -msse -msse2 -msse3 -mssse3 "Обычный" вариант: time: 10.000 time: 10.020 time: 10.000 time: 10.020 time: 10.000 Оптимизированный вариант: time: 9.100 time: 9.240 time: 9.100 time: 9.120 time: 9.180
Хотя в специальных случаях они действительно быстрее.Запись от grizlik78 размещена 02.05.2012 в 20:34
-
Запись от Evg размещена 02.05.2012 в 21:41
-
Запись от grizlik78 размещена 02.05.2012 в 22:19
-
Запись от grizlik78 размещена 02.05.2012 в 22:28
-
Запись от Evg размещена 02.05.2012 в 22:41
-
Стандартный метод оптимизации разворачиванием цикла. Так как длина массива заранее задана, то то же самое можно сделать через опции:
-funroll-loops --param max-unroll-times=2
(для gcc)
ну и если развернуть до 4-х (max-unroll-times=4), то на моей машине работает еще быстрее.
А вообще, странно, но, блин, у меня даже до краев оптимизнутый код работает медленее чем у вас неоптимизированные - 14.5 секунд, это минимум с циклом развернутым до 4-х. До 2-х - 16.5, обычный - ~17. Бида...Запись от Vourhey размещена 05.05.2012 в 02:33
-
gcc. Если указать опцию -march=native, то оптимизированный вариант кода работает в 2 раза медленней неоптимизированного. Обычный вариант - ~9 секунд, оптимизированный - ~16.5. Не все йогурты одинаково полезны... С ней он цикл без указания unroll-опций разворчивает до 8 (если включен -O3). Тестирую на AMD Phenom(tm) II X4 955 ProcessorЗапись от Vourhey размещена 05.05.2012 в 02:51
-
Vourhey, у меня основной целью было показать, что размер кода - не показатель скорости исполнения, а так же хотя бы на каком-то ощутимом примере дать людям понять, как наличие нескольких конвейеров влияет на исполнение. Просто конвейер - это такая штука, которым не умею пользоваться даже многие среди тех, кто на ассемблере программирует (ибо слишком специфичная вещь). По-честному нужно было демонстрировать при помощи ассемблера, а не компилятора, но всяких разных ассемблеров слишком много, а потому тут аккуратно свести концы с концами было бы сложно.
То, что у компилятора есть опции - это хорошо, но в реальной жизни они, как правило, сильно помогают только в частных случаях, а в общем случае только увеличивают время компиляции, но практически не ускоряют код. Это так называемые опции пиковых оптимизаций. По-хорошему к ним должна прилагаться методичка страниц на 500 с описанием, в каких случаях от каждой конкретной опции будет хороший эффект. Да и задача статьи состояла немного в другом
Так мы подгоняли параметр LOOP под каждый конкретный процессор, чтобы обычный вариант работал 10 секунд (чтобы сравнивать было удобнее)
Сообщение от Vourhey
Запись от Evg размещена 05.05.2012 в 09:22
-
Да, это понятно, какая основная цель. Просто тот, кто потом прочитает, будет и это иметь ввиду. А то можно неприятный эффект получить неожиданно при компиляции с различными опциями.Запись от Vourhey размещена 05.05.2012 в 11:00
-
В случае одного конвейера бонусы будут следующие:
- в два раза меньше переходов, чем в обычном варианте
- две подряд операции чтения из памяти, а потому ожидание результата (т.е. щёлканье вхолостую конвейера) будет практически то же самое количество тактов, но это количество тактов потеряется на двух итерациях, вместо одной
Т.е. и вправду тут эффект будет даже на одном конвейереЗапись от Evg размещена 05.05.2012 в 12:35
-
Запись от DenQ размещена 08.07.2012 в 02:20
-
Запись от talis размещена 11.07.2012 в 19:48
-
Буквально пару месяцев глубоко "варюсь" в этой теме, хочу дополнить:
Честно говоря лень описывать это своими словами, поэтому просто скопипастил кусок статьи с wasm'а.
Переименование регистров.
Команды в любой более-менее сложной программе обычно зависят друг от друга по данным. Зачастую зависимость по данным не является необходимой – просто так уж повелось у программистов: чем меньше переменных (и регистров в программах на ассемблере) использует программа – тем лучше, хороший тон и все такое.
В результате получаем шедевры, в которых вся программа использует один-два регистра с зависимостью по данным чуть ли не в каждой паре команд. Это сильно тормозило бы работу классического конвейера.
Чтобы исправить ситуацию был разработан механизм переименования регистров, который позволял устранить все зависимости по данным, кроме реально существующих.
Суть механизма в том, что процессор имеет больше регистров, чем доступно программисту. Каждый раз, когда команда прямо или косвенно пишет в регистр, ей выделяется новый физический регистр. Имеется также таблица отображения логических (видимых программисту) регистров на физические (видимые только процессору). Когда команде выделяется новый физический регистр, обновляется таблица – логический регистр, на который ссылалась команда, ставится в соответствие выделенному физическому регистру.
При определении операндов команды имена логических регистров преобразуются в имена физических, после чего, значения последних заносятся в поля операндов микрооперации. Микрооперации работают только с физическими регистрами.
Как можно увидеть, после декодирования команды N которая пишет в логический регистр R, все прочие команды, использующие в качестве операнда R будут обращаться к физическому регистру, выделенному для команды N. При этом, если какая-то команда после N будет писать в тот же логический регистр ей будет выделен новый регистр и все команды после нее будут использовать уже новый регистр. Это лучше показать на примере.
1 Команда пишет в R0 С этого момента R0 соответствует выделенному для команды регистру PHY0 2 Команда читает из R0 Читает из PHY0 3 Команда пишет в R0 С этого момента R0 соответствует выделенному для команды регистру PHY1 4 Команда читает из R0 Читает из PHY1
Эффект от этого такой: по таблице видно, что команды стали независимы. Если команды, работающие с логическим R0, зависят друг от друга и их нельзя выполнять параллельно, то микрооперации, «разведены» по PHY0 и PHY1 и независимы, их можно выполнять параллельно.
В современных процессорах набор архитектурных регистров отделен от файла временных регистров. Запись в архитектурные регистры возможна только в результате восстановления команды.
И еще
должно же бытьC 1
for (i = 0; i < length; i += 2)
C 1
for (i = 0; i < length - 1; i += 2)
Запись от Kastaneda размещена 08.09.2012 в 18:43
-
Kastaneda, не понял, а как тогда процессор определяет, значение какого физического регистра хочет получить команда, когда она читает из eax? Например, при syscall по int 80h, если мне не изменяет склероз, номер вызова мы пишем в eax. Сначала я что-то там в eax суммировал, оно пошло в PHY0, потом в eax же я кинул какой-нибудь 23h, оно пошло в PHY1, и сделал int 80h. Откуда int знает, что 23h в eax идёт ему, а не параллельно выполняемому суммированию?Запись от talis размещена 09.09.2012 в 12:52
-
Ну можно предположить, что add это суммирование (понятно, что результат нужен), а mov тут понятно, что старое значение регистра тебе уже не нужно, значит новое значение нужно для следующей операции.
Честно говоря тонкостей этого процесса я не знаю, похоже есть какая-то система, разруливающая подобные ситуации.
Может Evg что-нибудь прояснит?Запись от Kastaneda размещена 09.09.2012 в 16:20
-
Смысл переименования регистров примерно следующий
Есть следующий фрагмент кода:
В параллель тут ничего нельзя исполнить, т.к. всё завязано на один и тот же регистр %eax. Однако процессор в момент исполнения переделывает этот код во что-то типа:Codemov 1 -> %eax st %eax -> [mem1] mov 2 -> %eax st %eax -> [mem2]
Где %eax-2 - некий фиктивный (внутренний) регистр процессора, который пользователю по системе команд недоступен. А такой код уже можно распараллелить: сначала одновременно исполняются два mov'а, а затем два store'а. Переименовывание происходит для первой связки операций, но не для второй, т.к. ещё не известно, каким макаром далее используется регистр %eax, а в данной группе из 4 операций заведомо известно, что после первого store'а значение регистра %eax некритично. Процессор занимается подобными переименованиями лишь на небольшом фрагменте кодаCodemov 1 -> %eax-2 st %eax-2 -> [mem1] mov 2 -> %eax st %eax -> [mem2]
Всё это делается аппаратно и незаметно для пользовательской программы. Т.е. программа на самом деле и не знает, есть ли вообще такой механизм в процессоре. Думаю, что на всяких облегчённых версиях процессоров для нетбуков такого механизма нету, дабы упростить процессор и уменьшить энергопотреблениеЗапись от Evg размещена 09.09.2012 в 20:32
-
Запись от snake32 размещена 17.09.2012 в 19:25




