Недавно задался вопросом, а где вообще почитать про процессоры и как они устроены. К сожалению, архитектура практически всех современных процессоров закрыта.
С одним небольшим исключением, которое мне скинули друзья из ARM. Это процессоры Exynos, которые делались для каких-то Samsung вплоть до S20. Это единственные продакшен процессоры, которые соревновались с Snapdragon и Apple A* на мобильных устройствах. Серверные процессоры скорее отличаются большими кешами, а вот branch predictions, pipelining достаточно похожи. Статья сложная, но хочу рассказать о ментальной моделе, которую я выучил.
Branch Predictor во всех процессорах это мелкие перцептроны (однослойные нейронные сети), которые собирают три-четыре объекта
GHIST (Global History) — хэш информации о том, как последние N бранчей были взяты или не взяты. В статье сказали, что в M1 модели было 160 бит, к 4 поколению 200
PHIST (Path History) — хэш нескольких бит адресов (со второго по четвёртый) последних бранчей, массив длины 80
PC (Program Counter) — хэш указателя на сам бранч
RAS (Return Address Stack, опционально) — хэш возвращаемого значения из функции
Два уровня для TAKEN и NOT-TAKEN бранчей (c некоторыми разделителями для always-, often-, rare-, always-not-), чтобы запоминать всю информацию выше. В итоге получилось 32kb на перцептрон, 280kb на таблицы.
Recovery buffer — когда происходит mispredict, инструкции, которые были уже загружены и операции, которые были выполнены, должны уйти из буффера. В M5 также появился совсем маленький буффер для миспредикта often-taken бранчей, который сокращает latency при миспредикте.
Тем не менее, большинство улучшений были от увеличения буфферов и для редких бинарей. Увеличиваешь буффер в два раза, получаешь на 0.01-0.1% меньше проблем.
С точки зрения кода расстановка бранчей практически никак не влияет на современных процессорах. Если бранч непредсказуем, будет какая-то latency, если предсказуем, процессор почти всегда поймёт. Есть патологические случаи:
Много горячих функций нельзя, скорее всего 8-10 бит берется из адреса, поэтому уже с 256 будут проблемы. Обычно так и не происходит.
Если много холодных блоков и прыжок далекий, то могут быть проблемы с фрагментацией памяти. Если вы собираете свой бинарь с Profile Guided Optimization (что я настоятельно рекомендую), то никаких проблем с бранчами не будет, ставить [[likely]] и [[unlikely]] тоже бесполезно. Не бесполезно, если вы собираете библиотеку. PGO также поможет компилятору понять, стоить ли векторизировать некоторые циклы
Поэтому проблема с бранчами в целом решена для процессоров, лучшее, что вы можете сделать — убирать эти бранчи.
Статья также описывает то, как работают L1, L2-3 кеши. Скажем, сейчас процессоры через другой перцептрон предсказывают паттерны и даже непростые как p+2, p+4, p+9, p+11, p+13, p+18 предскажут, что надо подгрузить в кэш p+20, p+22, p+27 (+2, +2, +5). В L2 кеше из интересного размер кэшлинии 64 байта, но при загрузке из кэша также подгружается соседняя линия.
В общем, статья безумно интересная. Мне как человеку, который занимается перфом, было полезно прочитать. Видимо, буду ещё разбираться месяц-два до конца.
Это более глобальная проблема, мало людей, которые понимают как устроено hardware, чтобы делать быстрее software. В какой-то степени в последнее время развиваюсь в этом направлении — а как я могу утилизировать лучше код, зная как вещи работают изнутри, а не просто экспериментировав. Спасибо, что есть люди, которые рассказывают про технологии как Exynos.
Потихоньку отвечаю себе на вопрос, а как мой компьютер работает.
[1] Пост danluu о branch prediction, прям с нуля с 90 годов. Нет сложных вещей
[2] Перцептронные branch predictions
[3] Эксперименты cloudflare с branch predictions в AMD и Apple M1 (тоже нулевой порог входа)
[4] Статья про процессоры Exynos
[5] LLVM Profile Guided Optimization
[6] Agner Fog x86 branch predictors — без новых процов
С одним небольшим исключением, которое мне скинули друзья из ARM. Это процессоры Exynos, которые делались для каких-то Samsung вплоть до S20. Это единственные продакшен процессоры, которые соревновались с Snapdragon и Apple A* на мобильных устройствах. Серверные процессоры скорее отличаются большими кешами, а вот branch predictions, pipelining достаточно похожи. Статья сложная, но хочу рассказать о ментальной моделе, которую я выучил.
Branch Predictor во всех процессорах это мелкие перцептроны (однослойные нейронные сети), которые собирают три-четыре объекта
GHIST (Global History) — хэш информации о том, как последние N бранчей были взяты или не взяты. В статье сказали, что в M1 модели было 160 бит, к 4 поколению 200
PHIST (Path History) — хэш нескольких бит адресов (со второго по четвёртый) последних бранчей, массив длины 80
PC (Program Counter) — хэш указателя на сам бранч
RAS (Return Address Stack, опционально) — хэш возвращаемого значения из функции
Два уровня для TAKEN и NOT-TAKEN бранчей (c некоторыми разделителями для always-, often-, rare-, always-not-), чтобы запоминать всю информацию выше. В итоге получилось 32kb на перцептрон, 280kb на таблицы.
Recovery buffer — когда происходит mispredict, инструкции, которые были уже загружены и операции, которые были выполнены, должны уйти из буффера. В M5 также появился совсем маленький буффер для миспредикта often-taken бранчей, который сокращает latency при миспредикте.
Тем не менее, большинство улучшений были от увеличения буфферов и для редких бинарей. Увеличиваешь буффер в два раза, получаешь на 0.01-0.1% меньше проблем.
С точки зрения кода расстановка бранчей практически никак не влияет на современных процессорах. Если бранч непредсказуем, будет какая-то latency, если предсказуем, процессор почти всегда поймёт. Есть патологические случаи:
Много горячих функций нельзя, скорее всего 8-10 бит берется из адреса, поэтому уже с 256 будут проблемы. Обычно так и не происходит.
Если много холодных блоков и прыжок далекий, то могут быть проблемы с фрагментацией памяти. Если вы собираете свой бинарь с Profile Guided Optimization (что я настоятельно рекомендую), то никаких проблем с бранчами не будет, ставить [[likely]] и [[unlikely]] тоже бесполезно. Не бесполезно, если вы собираете библиотеку. PGO также поможет компилятору понять, стоить ли векторизировать некоторые циклы
for (int i = 0; i < some_value; ++i) { ... }
И обычно компилятор векторизирует из-за незнания some_value, но профиль собирает эту информацию и в итоге лучше компилирует код.Поэтому проблема с бранчами в целом решена для процессоров, лучшее, что вы можете сделать — убирать эти бранчи.
Статья также описывает то, как работают L1, L2-3 кеши. Скажем, сейчас процессоры через другой перцептрон предсказывают паттерны и даже непростые как p+2, p+4, p+9, p+11, p+13, p+18 предскажут, что надо подгрузить в кэш p+20, p+22, p+27 (+2, +2, +5). В L2 кеше из интересного размер кэшлинии 64 байта, но при загрузке из кэша также подгружается соседняя линия.
В общем, статья безумно интересная. Мне как человеку, который занимается перфом, было полезно прочитать. Видимо, буду ещё разбираться месяц-два до конца.
Это более глобальная проблема, мало людей, которые понимают как устроено hardware, чтобы делать быстрее software. В какой-то степени в последнее время развиваюсь в этом направлении — а как я могу утилизировать лучше код, зная как вещи работают изнутри, а не просто экспериментировав. Спасибо, что есть люди, которые рассказывают про технологии как Exynos.
Потихоньку отвечаю себе на вопрос, а как мой компьютер работает.
[1] Пост danluu о branch prediction, прям с нуля с 90 годов. Нет сложных вещей
[2] Перцептронные branch predictions
[3] Эксперименты cloudflare с branch predictions в AMD и Apple M1 (тоже нулевой порог входа)
[4] Статья про процессоры Exynos
[5] LLVM Profile Guided Optimization
[6] Agner Fog x86 branch predictors — без новых процов