Comments 77
хороший перевод, спасибо
Скрытый текст
- Knock knock
- Branch prediction
- Who's there?
В основном, каждое отдельное ветление часто срабатывают в одном направвлении, и очень редко в другом. Если каждый переход, еще на уровне компилятора, помечать в какую сторону он срабатывает чаще, то можно без сякого предсказания получать очень высокую вероятность правильного попадания.
Компании столько тысяч человеко-лет инвестировали в патенты, а ты им предлогаеш всю эту лавочку похерить.
В gcc на это есть __builtin_expect
Если «чаще» — это только 75%, то получаем проигрыш в сравнении с динамическими предикторами, которые дают 95%.
В основном, каждое отдельное ветление часто срабатывают в одном направвлении, и очень редко в другом.
Так себе гипотеза.
Почему вдруг? Гипотеза, что ветвления чаще всего срабатывают в одном направлении (назад, BTFNT), дает очень хороший прирост производительности, на фоне которого все остальные изыски — мелкие оптимизации.
Так считали люди, для которых оптимизация на 30% — не мелкая.
Очевидным вариантом является, что при наличии пустых таблиц для оптимизации предсказаний — считать, что все переходы — назад. При накоплении некоторой достаточной статистики — плавно переключаться на более продвинутые методы. Что интересно, именно такой подход используется в Pentium и, видимо, более поздних процессорах…
Таким образом мы получаем начальный уровень успеха предсказания не 50:50, а 80:20. Что дает хорошую прибавку к пенсии, пока накапливается статистика для остальных предикторов.
Таким образом мы получаем начальный уровень успеха предсказания не 50:50, а 80:20. Что дает хорошую прибавку к пенсии, пока накапливается статистика для остальных предикторов.
Почему же? Intel в старых процессорах её использовала. Переходы назад — likely, переходы вперёд — unlikely.
Скорее всего, этого можно достичь с PGO. Скорее всего, разработчики компиляторов в курсе, какие ветвления лучше предсказываются процессором, и строят код именно так, чтобы достичь минимума ошибок перехода для тестового случая.
Интересно, а как процессор контролирует изменение кода? Например при выгрузке/загрузке в своп. Или никак, просто некоторое время перезаполняет таблицу переходов с кучей промахов?
При Page Fault происходит аппаратное прерывание, приводящее к сбросу конвейера.
Ничего страшного в этом нет: по сравнению с чтением из диска, разгон конвейера — мгновение.
Ничего страшного в этом нет: по сравнению с чтением из диска, разгон конвейера — мгновение.
А таблицы переходов являются частью конвейера или привязаны к оперативке? Или при каждом переключении задачи это всё сбрасываться в 0? Не очень понял этот момент. Или это какие-то внутренние регистры проца?
Всё, что я могу сказать — никакой привязки к оперативке быть не должно: в инструкциях x86 просто не предусмотрено хранения соответстующего флага предпочтительной ветки, да и в случае ROM непонятно, как быть.
Скорее всего, в процессоре присутствует просто небольшая табличка на несколько значений (т.е. внутренние регистры процессора), содержащая в себе физический адрес инструкции перехода и статистические данные для неё.
А вообще, это нужно уже инженеров Intel спрашивать, потому что гадание на кофейной гуще получается.
Скорее всего, в процессоре присутствует просто небольшая табличка на несколько значений (т.е. внутренние регистры процессора), содержащая в себе физический адрес инструкции перехода и статистические данные для неё.
А вообще, это нужно уже инженеров Intel спрашивать, потому что гадание на кофейной гуще получается.
Иными словами, хорошей практикой является упрощение ветвлений до такой степени, чтобы их ветки (по возможности) выполнялись всегда и без ошибок. Правильно?
GPU так и работают, поскольку условные переходы там весьма дороги (если получаются разные переходы в пределах одной группы потоков). Там куча встроенных инструкций (типа min, max, clamp), которые позволяют избавиться от очень большого количества условных переходов. А некоторые переходы бывает дешевле (и достаточно не сложно) свести к чуть более громоздким вычислениям, чем пихать лишний if. Например вместо
if( a < 10.) b = 20.; else b = 30.;
можно
b = 20. + step(a, 10.) * 10.;
if( a < 10.) b = 20.; else b = 30.;
можно
b = 20. + step(a, 10.) * 10.;
обычно есть способ заинвалидировать таблицу переходов, чтобы избежать ложных срабатываний. Ядро операционки должно это делать при переключении контекста
Не совсем так. В x86/amd64 архитектуре этого делать не нужно. А вот в ARM есть соответствующая команда.
Думаю, здесь путаница с инвалидированием кеша.
А зачем кэш инвалидировать? Внутренний кэш декодированных инструкций очистится сам. Кэш памяти же ещё пригодится, когда ОС вернёт управление процессу.
Я лишь о том, что эта возможность есть.
В случае x86 ни branch predictor ни кэш инвалид рожать не нужно. Что касается ARM, там инструкция branch predictor invalidate действительно присутствует, но с некоторых пор ничего не делает и оставлена в целях совместимости. Кэш же в ARM программист обязан инвалидировать в случае self-modified code, а именно, если код был перезаписан, программист обязан выполнить Data Cache Clean by VA at Point of Unification и Instruction Cache Invalidate by VA at Point of Unification. Связано это с тем, что в ARM кэш инструкций согласно архитектуре не является когерентным.
Можно ли перенести предсказание переходов с аппаратной части на программную (компилятор, стат.анализатор, правила написания кода) и будет ли это выгоднее с точки зрения скорости исполнения? Я имею в виду не взаимодействие с пользователем или оборудованием, а числомолотилки.
В числомолотилках эта проблема не настолько актуальна.
Разворот циклов, условное выполнение операций (в SSE/AVX расширениях) — и ветвлений становится значительно меньше.
Разворот циклов, условное выполнение операций (в SSE/AVX расширениях) — и ветвлений становится значительно меньше.
Возьмём, например, умножение матриц:
При n=3 динамический предиктор рано или поздно выявит паттерн, что во внутреннем цикле каждый 3-й переход не выполняется, а как это должен понять компилятор?
void mult(int n, double *a, *b, *c) {
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
....При n=3 динамический предиктор рано или поздно выявит паттерн, что во внутреннем цикле каждый 3-й переход не выполняется, а как это должен понять компилятор?
На практике размер матриц, особенно небольших, редко является произвольным.
Поэтому n будет константой, и оптимизирующий компилятор просто развернёт цикл.
Поэтому n будет константой, и оптимизирующий компилятор просто развернёт цикл.
Это модельный пример. На практике может быть любой другой цикл обработки данных, который программист сделал параметризуемым, а параметр читается из конфига.
Если n константное, то можно развернуть цикл. Если неконстантное, но вычислимое заранее, то тоже можно, если язык есть поддержка самомодифицирующегося кода. Можно попробовать векторизовать и раскидать на разные ядра, предвычислив i и/или j
PS Компиляторов не писал, процессоров не разрабатывал, так что все мои рассуждения сугубо теоретические
PS Компиляторов не писал, процессоров не разрабатывал, так что все мои рассуждения сугубо теоретические
Цикл менее 1000 итераций, внутри которых пара арифметических действий, нет смысла раскидывать по ядрам. Больше потеряешь на создании потоков.
Насколько я видел (OpenMP, TPL и т.п.), везде программист даёт указания, что можно попробовать запараллелить. Поскольку программисты оптимизируют только горячие места, а не всё подряд, оптимизации всего остального лучше переложить на процессор.
Насколько я видел (OpenMP, TPL и т.п.), везде программист даёт указания, что можно попробовать запараллелить. Поскольку программисты оптимизируют только горячие места, а не всё подряд, оптимизации всего остального лучше переложить на процессор.
Подскажите, если не сложно, статью, где обобщенно (я понимаю, что серебряной пули нет) рекомендуется, начиная со скольки итераций/инструкций и какого объёма памяти раскидывание по ядрам или на GPU становится выгодным.
Ха, у процессора есть таймер с потактовой точностью замера (RDTSC).
Можете сами померять, сколько что стоит, и сделать соответствующие расчёты.
Можете сами померять, сколько что стоит, и сделать соответствующие расчёты.
Проверяется просто: создаёте поток в играете с ним в пинг-понг через средства синхронизации.
Вот одна из простейших реализаций parallel do: https://gist.github.com/e673/31b73495bfb83e818f226d2300568176
Варьируете N и смотрите, сколько итераций будет в зависимости от N.
Оптимальное значение N = числу логических ядер минус 1 (текущий поток тоже должен выполнять задачу).
Под Windows на 4-ядерном процессоре при N = 3 у меня получается 400к переключений в секунду (при N = 1, кстати, получается ~2 миллиона), т.е. ~10000 тактов уходит только на одну синхронизацию. Под Linux на 2-ядернике вдвое меньшей частоты при N = 1 — 80к переключений.
Чем на большее число потоков вы параллелите задачу, тем выше накладные расходы. Я даже боюсь представить, что будет твориться на Threadripper при 32 потоках, ведь блокировка шины при изменении атомарной переменной, за которую борется куча потоков — штука очень неприятная.
То есть, чтобы задачу вообще имело смысл параллелить, задача должна выполняться ощутимое время — несколько десятков микросекунд.
Кстати, низкая гранулярность тоже может оказаться не в фаворе, если будет страдать локальность доступа к памяти.
Вот одна из простейших реализаций parallel do: https://gist.github.com/e673/31b73495bfb83e818f226d2300568176
Варьируете N и смотрите, сколько итераций будет в зависимости от N.
Оптимальное значение N = числу логических ядер минус 1 (текущий поток тоже должен выполнять задачу).
Под Windows на 4-ядерном процессоре при N = 3 у меня получается 400к переключений в секунду (при N = 1, кстати, получается ~2 миллиона), т.е. ~10000 тактов уходит только на одну синхронизацию. Под Linux на 2-ядернике вдвое меньшей частоты при N = 1 — 80к переключений.
Чем на большее число потоков вы параллелите задачу, тем выше накладные расходы. Я даже боюсь представить, что будет твориться на Threadripper при 32 потоках, ведь блокировка шины при изменении атомарной переменной, за которую борется куча потоков — штука очень неприятная.
То есть, чтобы задачу вообще имело смысл параллелить, задача должна выполняться ощутимое время — несколько десятков микросекунд.
Кстати, низкая гранулярность тоже может оказаться не в фаворе, если будет страдать локальность доступа к памяти.
Update: при использовании Windows-specific варианта при больших N (N = 8 и выше) накладные расходы становятся ниже, чем при кросс-платформенном варианте.
Кстати в командах x86 есть ведь и команды для цикла ( loop и иже с ними ). Нельзя ли их как-то оптимизировать и делать циклы по возможности на них. Правда для вложенных циклов необходимо, чтобы компилятор достаточно заранее восстанавливал CX, чтобы все ступени конвейера успели среагировать.
Кстати, с VLIW-компиляторами как-то выкрутились, или по прежнему не получается выжать всё из архитектуры?
У меня ощущение, что они не нужны никому. Тот же Intel прекратил развитие Itanium.
Есть ещё неподимый и легендарный Эльбрус, но документацию я одолеть не смог, она гораздо грустнее интеловской, и компилятор я не знаю, где скачать
В DSP активно используются. Вот, например, свежий 8-way VLIW для 5G модемов: www.ceva-dsp.com/product/ceva-xc12
Можно-то можно, но есть один нюанс. Дешифрация команды не происходит мгновенно, и сколько тактов пройдет, прежде чем процессор поймет, что он испольняет команду ветвления — одному Аллаху ведомо. А знать это процессору необходимо сразу, ибо следующую команду надо выбирать уже на следующем такте.
Современные процессоры не читают по одной инструкции — они гребут код, что называется, «большой лопатой». В частности, мне приходилось видеть CPU, который читает по 2 кэшлайна кода за такт.
это никак не отменяет того, что я сказал
Согласен. Только декодирование — процесс достаточно быстрый, и, соответственно, на out of order CPU о том, что инструкция является переходом, может быть известно сильно раньше, чем она реально начнёт исполняться. Что же касается двухстадийного конвейера, который нам упорно рисуют в статье, так в нём вообще можно обойтись без предсказания переходов — человечество изобрело такое понятие как delay slot.
Довольно интересная ситуация, когда предсказание переходов можно пощупать на практике:
Задача: пробежаться по массиву байт и посчитать количество байт, больших 128.
Наблюдение: при случайном заполнении скорость работы алгоритма в 6 раз медленнее, чем при неслучайном (отсортированный массив).
Я может быть глупость спрошу, но вот это предсказание нужно чтобы выбрать одну из двух ветвей выполнения. Если предсказание не сбылось, то результат работы с неверной веткой просто отбрасывается. Можно ли пойти сразу по двум веткам одновременно и отбросить результат работы той, что не сбылась?
> Можно ли пойти сразу по двум веткам одновременно и отбросить результат работы той, что не сбылась?
Можно, но это дорого: в процессоре лишних вычислительных блоков под такое просто нет.
Возможно, это и используется, но очень ограничено: для выборки команд в кэш из обеих веток, например.
Можно, но это дорого: в процессоре лишних вычислительных блоков под такое просто нет.
Возможно, это и используется, но очень ограничено: для выборки команд в кэш из обеих веток, например.
По такому принципу кстати работают GPU. Но там это обусловлено тем, что блоки по 32 ядра (warpы в cuda) в один момент времени могут выполнять только одинаковые инструкции.
UFO just landed and posted this here
В наборе x86/x64 нет такой инструкции.
С другой стороны, зачем? Если ветвление выполняется часто, оно будет запомнено и не вытеснится из буфера предсказаний. А если редко, потеря нескольких тактов не важна.
С другой стороны, зачем? Если ветвление выполняется часто, оно будет запомнено и не вытеснится из буфера предсказаний. А если редко, потеря нескольких тактов не важна.
UFO just landed and posted this here
Касательно процессоров Intel:
https://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-optimization-manual.pdf, раздел 3.4.1.
Про статическое предсказание (п. 3.4.1.3) вполне конкретно написано: The Intel Core microarchitecture does not use the static prediction heurist.
https://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-optimization-manual.pdf, раздел 3.4.1.
Про статическое предсказание (п. 3.4.1.3) вполне конкретно написано: The Intel Core microarchitecture does not use the static prediction heurist.
может даже так сложиться, что именно вторая, малоприоритетная ветка станет выполняться чаще, что добавит тактов 10 на перезагрузку конвейера в случае, когда код должен быть максимально быстрымНе понимаю примера. Статически — это значит один раз при компиляции, без возможности изменения. То есть, эта ветка 100 раз выполнялась, её предиктор пометил как приоритетную, а потом она 3 раза не выполнилась и предиктор промахнулся? А что будет, если её статически пометить как не приоритетную? Будет 100 промахов и 3 попадания?
Если они близки к случайным, то в половине случаев (!) предсказатель будет ошибаться и результат работы будет ужасныйЧто предлагается? Например, в цикле
for (int i = 0; i < N; i++) { if (i & 1) { .... } }Перед условным переходом вычислить i&1 и выполнить какую-то команду, которая подскажет по значению i, будет ли переход? Так такая команда — то же самое, что и ветвление, почему бы эти 2 команды не объединить в логику инструкции ветвления. На самом дела, нужно загрузить конвеер намного заранее до вычисления условия, а не прямо перед ним.
UFO just landed and posted this here
На самом деле не совсем. Например в циклах о том, будет ли переход часто известно ещё в начале цикла, что (теоретически) можно использовать. Кстати у x86 есть встроенная команда (loop и её вариации) которую можно было бы оптимизировать предсказанием, если бы были какие-то гарантии, что её рабочий регистр (CX для основного варианта) не используют подо что-то другое. Правда там ещё есть варианты, которые по флагам работаю, и тут уже ничего не предскажешь.
А про 1 500 000 год до н.э. — это юмор?
Мне кажется что лучше было бы использовать не «цель перехода», а «целевой адрес перехода». К слову «цель» напрашивается вопрос «зачем», но это совсем не то, что имелось в виду.
Замените пожалуйста везде по тексту «подым(\S+)» на «подним$1». А то читать тяжело с самого начала.
Замените «в раках» на «в рамках».
Объясните, пожалуйста следующий момент:
Пусть x = 3, y = 3… Независимо от того, по какой из ветвей пойдёт код (даже если по обеим), условие выполнения третьей всегда будет истинно (2*2 > 0). Или какой это язык? Возможно имелось ввиду x = -1?
В чём смысл вставок с кодом, если они никаких пояснений не вносят?
if x > 0:
x -= 1
if y > 0:
y -= 1
if x * y > 0:
foo()
Если произойдёт переход по первой или второй ветви, то третья определённо останется незадействованной.
Пусть x = 3, y = 3… Независимо от того, по какой из ветвей пойдёт код (даже если по обеим), условие выполнения третьей всегда будет истинно (2*2 > 0). Или какой это язык? Возможно имелось ввиду x = -1?
В чём смысл вставок с кодом, если они никаких пояснений не вносят?
Sign up to leave a comment.
История предсказания переходов с 1 500 000 года до н.э. по 1995 год