При работе с современными CPU устранение ошибочного предсказания ветвления — ключевой способ повышения скорости программ. Один из самых эффективных способов снижения количества ошибочных предсказаний — полное устранение ветвлений.
Рубрика «предсказание ветвлений»
Если if вас замедляют, откажитесь от них
2026-05-13 в 9:04, admin, рубрики: безусловная оптимизация, ветвление, предсказание ветвленийПроцессор в вашем компьютере угадывает будущее. И ошибается в 5% случаев
2026-03-22 в 10:14, admin, рубрики: branch prediction, cpu, spectre, Алгоритмы, архитектура процессоров, конвейер, оптимизация кода, предсказание ветвлений, производительностьВ прошлую пятницу я объяснял джуну, почему его код на отсортированном массиве работает в шесть раз быстрее, чем на неотсортированном. Тот же массив, тот же алгоритм, и те же данные. Просто в другом порядке. Джун смотрел на меня как на сумасшедшего и, честно говоря, я его понимаю.
Потому что ответ звучит безумно: процессор внутри вашего ноутбука постоянно пытается предсказать будущее. Буквально. Он гадает, какая ветка if выполнится ещё до того, как условие будет вычислено. И на отсортированных данных ему угадывать проще.
Ну, давайте разбираться.
Конвейер, или почему процессору вообще нужно гадать
Неожиданное взаимодействие предсказания ветвлений и подсистем памяти
2024-01-07 в 10:00, admin, рубрики: ruvds_перевод, Алгоритмы, быстрая сортировка, память, пирамидальная сортировка, предсказание ветвлений, Процессоры
Это 15-я статья в серии, посвящённая оптимизации подсистем памяти. Остальные доступны здесь (англ.).
В ней мы изучим взаимодействие механизма предсказания ветвлений с подсистемой памяти. В повествовании мы будем исходить из предположения, что вам знаком принцип предсказания ветвлений и работы подсистем памяти в современных процессорах.Читать полностью »
Ошибочно предсказанное ветвление может в разы увеличить время выполнения программы
2019-10-23 в 4:30, admin, рубрики: amd, branch prediction, intel, Skylake, Компиляторы, предсказание ветвлений, Программирование, Процессоры, суперскалярность
Современные процессоры суперскалярны, то есть способны выполнять несколько инструкций одновременно. Например, некоторые процессоры могут обрабатывать за цикл от четырёх до шести инструкций. Более того, многие такие процессоры способны инициировать команды не по порядку: они могут начать работать с командами, расположенными в коде намного позже.
В то же время, код часто содержит ветвления (операторы if–then). Такие ветвления часто реализуются как «переходы», при которых процессор или переходит к выполнению инструкции ниже по коду, или продолжает текущий путь.
При суперскалярном выполнении команд вне порядка с ветвлениями справляться сложно. Для этого у процессоров имеются изощрённые блоки предсказания ветвления. То есть процессор пытается предсказать будущее. Когда он видит ветвление, а значит, переход, то пытается догадаться, каким путём пойдёт программа.
Читать полностью »
Как разрабатываются и производятся процессоры: основы архитектуры компьютеров
2019-06-21 в 4:23, admin, рубрики: amd, IBM, intel, risc-v, x86, архитектура процессоров, Компьютерное железо, кэш процессора, Научно-популярное, предсказание ветвлений, Производство и разработка электроники, суперскалярная архитектура
Мы воспринимаем центральный процессор как «мозг» компьютера, но что это значит на самом деле? Что именно происходит внутри миллиардов транзисторов, благодаря которым работает компьютер? В нашей новой мини-серии из четырёх статей мы рассмотрим процесс создания архитектуры компьтерного оборудования и расскажем о принципах его работы.
В этой серии мы расскажем об компьютерной архитектуре, проектировании процессорных плат, VLSI (very-large-scale integration), производстве чипов и тенденциях будущего в области вычислительной техники. Если вам было интересно разобраться в подробностях работы процессоров, то начинать изучение лучше с этой серии статей.
Мы начнём с очень высокоуровневого объяснения того, чем занимается процессор и как строительные блоки соединяются в функционирующую конструкцию. В том числе мы рассмотрим процессорные ядра, иерархию памяти, предсказание ветвлений и другое. Во-первых, нам нужно дать простое определение тому, что делает ЦП. Простейшее объяснение: процессор следует набору инструкций для выполнения определённой операции над множеством входящий данных. Например, это может быть считывание значения из памяти, затем прибавление его к другому значению, и наконец сохранение результата в память по другому адресу. Это может быть и нечто более сложное, например, деление двух чисел, если результат предыдущего вычисления больше нуля.
Программы, например, операционная система или игра, сами по себе являются последовательностями инструкций, которые должен выполнять ЦП. Эти инструкции загружаются из памяти и в простом процессоре выполняются одна за другой, пока программа не завершится. Разработчики программного обеспечения пишут программы на высокоуровневых языках, например, на C++ или на Python, но процессор не может их понимать. Он понимает только единицы и нули, поэтому нам нужно каким-то образом представить код в этом формате.
Читать полностью »
Исследователи из Google: для защиты от Spectre требуется изменение архитектуры процессоров, программные патчи не помогут
2019-02-22 в 18:21, admin, рубрики: meltdown, spectre, архитектура процессоров, информационная безопасность, предсказание ветвлений, Процессоры, спекулятивное выполнение
В январе 2018 года исследователи Google раскрыли в публичном доступе информацию о фундаментальной аппаратной уязвимости в большинстве современных процессоров, имеющих спекулятивное выполнение команд. Уязвимость Spectre (и смежная Meltdown) эксплуатирует механизм предсказания ветвлений в CPU и позволяет проводить чтение данных через сторонний канал в виде общей иерархии кэш-памяти. Другими словами, любое приложение на компьютере может получить доступ на чтение к произвольным местам памяти, что нарушает изоляцию программ, провоцирует утечку данных, отказ в обслуживании и прочие неприятности.
Хуже всего, что уязвимости подвержены практически все современные процессоры (кроме RISC и российского «Эльбруса»), потому что предсказание ветвлений стало фундаментальной частью архитектуры современных CPU, от которой невозможно отказаться без значительной потери производительности.
Читать полностью »
Серьёзные перемены в ведущих архитектурах микросхем
2018-09-10 в 8:28, admin, рубрики: Arteris IP, cadence, dram, eSilicon, HBM2, IBM, M2, M3, ml, NetSpeed Systems, Nvidia, NVM, Samsung, ssd, xilinx, аппаратный ИИ, архитектура фон Неймана, Интернет вещей, искусственный интеллект, Компьютерное железо, машинное обучение, нейроморфные вычисления, оптимизация памяти, предсказание ветвлений, Производство и разработка электроникиВнедрение ИИ на уровне микросхем позволяет обрабатывать локально больше данных, потому что увеличение количества устройств уже не даёт прежнего эффекта
Производители микросхем работают над новыми архитектурами, которые значительно увеличивают объём обрабатываемых данных на ватт и такт. Готовится почва для одной из крупнейших революций в архитектуре чипов за последние десятилетия.
Все основные производители чипов и систем меняют направление развития. Они вступили в гонку архитектур, которая предусматривает изменение парадигмы во всём: от методов чтения и записи в память до их обработки и, в конечном счёте, компоновки различных элементов на чипе. Хотя миниатюризация продолжается, уже никто не делает ставку на масштабирование, чтобы справится со взрывным ростом данных от сенсоров и увеличения объёма трафика между машинами.
Читать полностью »
История предсказания переходов с 1 500 000 года до н.э. по 1995 год
2017-09-02 в 20:05, admin, рубрики: agree, BTFNT, gshare, Алгоритмы, Компиляторы, Перцептрон, предсказание ветвлений, предсказание переходов, Программирование, статическое предсказаниеЭто приблизительная расшифровка лекции о предсказании переходов (предсказании ветвлений) на localhost, новом цикле лекций, организованном RC. Выступление состоялось 22 августа 2017 года в Two Sigma Ventures.
Кто из вас использует ветвления в своём коде? Можете поднять руку, если применяете операторы if или сопоставление с образцом?
Большинство присутствующих в аудитории поднимают руки
Сейчас я не буду просить вас подымать руки. Но если я спрошу, сколько из вас думают, что хорошо понимают действия CPU при обработке ветвления и последствия для производительности, и сколько из вас может понять современную научную статью о предсказании ветвлений, то руки подымет меньше людей.
Цель моего выступления — объяснить, как и почему процессоры осуществляют предсказание переходов, а затем вкратце объяснить классические алгоритмы предсказания переходов, о которых вы можете прочитать в современных статьях, чтобы у вас появилось общее понимание темы.
Читать полностью »