Это приблизительная расшифровка лекции о предсказании переходов (предсказании ветвлений) на localhost, новом цикле лекций, организованном RC. Выступление состоялось 22 августа 2017 года в Two Sigma Ventures.

Кто из вас использует ветвления в своём коде? Можете поднять руку, если применяете операторы if или сопоставление с образцом?

Большинство присутствующих в аудитории поднимают руки

Сейчас я не буду просить вас подымать руки. Но если я спрошу, сколько из вас думают, что хорошо понимают действия CPU при обработке ветвления и последствия для производительности, и сколько из вас может понять современную научную статью о предсказании ветвлений, то руки подымет меньше людей.

Цель моего выступления — объяснить, как и почему процессоры осуществляют предсказание переходов, а затем вкратце объяснить классические алгоритмы предсказания переходов, о которых вы можете прочитать в современных статьях, чтобы у вас появилось общее понимание темы.

Перед тем как обсуждать предсказание переходов, поговорим о том, зачем вообще процессоры это делают. Для этого нужно немного знать о работе CPU.

В раках этой лекции можете воспринимать компьютер как CPU плюс немного памяти. Инструкции живут в памяти, а CPU выполняет последовательность инструкций из памяти, где сами инструкции имеют вид вроде «сложить два числа», «перенести фрагмент данных из памяти в процессор». Обычно после выполнения одной инструкции CPU выполняет инструкцию со следующим по порядку адресом. Однако есть инструкции типа «переходы», которые позволяют изменить адрес следующей инструкции.

Вот абстрактная диаграмма CPU, выполняющего некоторые инструкции. По горизонтальной оси отложено время, а по вертикальной — отличия между разными инструкциями.



Здесь мы сначала выполняем инструкцию A, затем инструкции B, C и D.

Один способ проектирования CPU — делать всю работу по очереди. Здесь нет ничего плохого; многие старые CPU так работают, как и некоторые современные очень дешёвые процессоры. Но если вы хотите сделать более быстрый CPU, то нужно превратить его в подобие конвейера. Для этого вы разбиваете процессор на две части, так что первая половина находится на фронтенде работы с инструкциями, а вторая половина — в бэкенде, как на конвейере. Это обычно называют конвейерным процессором (pipelined CPU).



Если вы сделаете так, то выполнение инструкций будет происходить примерно как на иллюстрации. После выполнения первой половины инструкции A процессор начинает работать над второй половиной инструкции A одновременно с первой половиной инструкции B. А когда завершается выполнение второй половины A, процессор может одновременно начать вторую половину B и первую половину C. На этой диаграмме вы видите, что конвейерный процессор способен выполнять за промежуток времени вдвое больше инструкций, чем обычный процессор, показанный ранее.

Нет никакой причины разделять CPU всего на две части. Мы можем разделить его на три части и получить трёхкратный прирост производительности или на четыре части для четырёхкратного прироста. Хотя это не совсем верно и на самом деле обычно прирост не будет трёхкратным для трёхступенчатого конвейера или четырёхкратным для четырёхступенчатого конвейера, потому что есть определённые накладные расходы при разделении CPU на части.

Один источник накладных расходов — то, как обрабатываются ветвления. Первым делом CPU должен получить инструкцию. Для этого он должен знать, где она находится. Например, возьмём следующий код:

if (x == 0) {
  // Do stuff
} else {
  // Do other stuff (things)
}
  // Whatever happens later

Его можно перевести в ассемблер:

branch_if_not_equal x, 0, else_label
// Do stuff
goto end_label
else_label:
// Do things
end_label:
// whatever happens later

В этом примере мы сравниваем x с нулём. Если он не равен нулю (if_not_equal), то мы переходим к else_label и выполняем код в блоке else. Если это сравнение не выполняется (то есть если x равен нулю), то мы проваливаемся, выполняем код в блоке if, а затем перепрыгиваем к end_label, чтобы избежать выполнения кода в блоке else.

Для конвейера проблематичной является конкретная последовательность инструкций:

branch_if_not_equal x, 0, else_label
???

Процессор не знает, что будет дальше:

branch_if_not_equal x, 0, else_label
// Do stuff

или

branch_if_not_equal x, 0, else_label
// Do things

Он не знает этого, пока не завершилось (или почти завершилось) выполнение ветви. Одним из первых действий CPU должно быть извлечение инструкции из памяти, а мы даже не знаем, какой будет инструкция ??? и не можем с ней работать, пока предыдущая инструкция почти не закончена.

Ранее мы говорили, что получаем почти трёхкратное ускорение при использовании трёхступенчатого конвейера или почти 20-кратное при использовании 20-ступенчатого. Предполагалось, что на каждом цикле вы можете начинать выполнение новой инструкции, но в данном случае две инструкции практически сериализованы.



Один из вариантов решения проблемы — использовать предсказание переходов. Когда появляется ветвь, CPU будет предполагать, взята эта ветвь или нет.



В этом случае процессор предсказывает, что ветвь не будет занята, и начинает выполнение первой половины stuff, одновременно заканчивая выполнение второй половины ветви. Если предсказание верно, то CPU выполнит вторую половину stuff и может начать выполнение ещё одной инструкции, работая со второй половиной stuff, как мы видели на первой диаграмме конвейера.



Если предсказание ошибочно, то после завершения выполнения ветви CPU отбросит результаты stuff.1 и начнёт выполнение правильных инструкций вместо неправильных. Поскольку в отсутствие предсказания переходов мы бы остановили процессор и не выполнили бы никаких инструкций, мы ничего не теряем в такой ситуации (по крайней мере, на том уровне приближения, с которым рассматриваем ситуацию).



Каково влияние на производительность? Чтобы оценить его, нужно смоделировать производительность и нагрузку. Для этой лекции возьмём карикатурную модель конвейерного CPU, где не-ветвления отрабатываются примерно одной инструкцией за цикл, непредсказанные или неправильно предсказанные переходы занимают 20 циклов, а правильно предсказанные — один цикл.

Если взять самый популярных бенчмарк для целочисленных нагрузок на «рабочую станцию» SPECint, то распределение может быть 20% ветвей и 80% других операций. Без предсказания переходов мы ожидаем, что «средняя» инструкция займёт branch_pct * 1 + non_branch_pct * 20 = 0.8 * 1 + 0.2 * 20 = 0.8 + 4 = 4.8 цикла. При идеальном на 100% точном предсказании переходов средняя инструкция займёт 0.8 * 1 + 0.2 * 1 = 1 цикл, что означает ускорение в 4,8 раза! Другими словами, если у нас конвейер со «штрафом» в 20 циклов за непредсказанный переход, то мы получаем почти пятикратные издержки по сравнению с идеальным конвейером, только за счёт предсказания ветвлений.

Посмотрим, что можно с этим сделать. Начнём с самых простых вещей, и постепенно выработаем решение получше.

Берём все переходы

Вместо случайных предсказаний мы можем посмотреть на все ветви выполнения всех программ. В этом случае мы увидим, что взятые и невзятые ветви неодинаково сбалансированы — взятых ветвей гораздо больше, чем невзятых. Одной из причин являются ветви цикла, которые часто выполняются.

Если предсказывать взятие каждой ветви, то мы можем выйти на уровень точности предсказаний 70%, так что будем оплачивать только неверно предсказанные 30% переходов, что снижает стоимость средней инструкции до (0.8 + 0.7 * 0.2) * 1 + 0.3 * 0.2 * 20 = 0.94 + 1.2. = 2.14. Если сравнить обязательное предсказание всех переходов с отсутствием предсказания и с идеальным предсказанием, то обязательное предсказание отыгрывает бoльшую часть преимущества идеального предсказания, хотя это очень простой алгоритм.

Берём переходы назад, не берём переходы вперёд (BTFNT)

Предсказывать взятие всех ветвей хорошо работает для циклов, но не для других ветвей. Если посмотреть на процент выполнения переходов вперёд по программе или назад по программе (возвращение к предыдущему коду), то мы увидим, что переходы назад выполняются гораздо чаще, чем переходы вперёд. Поэтому можно попробовать предиктор, который предсказывает взятие всех переходов назад и невзятие всех переходов вперёд (BTFNT, backwards taken forwards not taken). Если мы реализуем эту схему на аппаратном уровне, то компиляторы подстроятся под нас и начнут организовывать код таким образом, чтобы ветви с наибольшими шансами выполнения становились переходами назад, а ветви с наименьшими шансами выполнения становились переходами вперёд.

Если это сделать, то можно добиться точности предсказаний около 80%, что снижает стоимость выполнения инструкции до (0.8 + 0.8 * 0.2) * 1 + 0.2 * 0.2 * 20 = 0.96 + 0.8 = 1.76 цикла.



Кто использует:

• PPC 601 (1993): также использует советы компилятора в виде сгенерированных переходов
• PPC 603

Один бит

До сих пор мы рассматривали схемы, которые не сохраняют никакого состояния, то есть такие схемы, где предиктор игнорирует историю выполнения программы. В литературе они называются статическими методами предсказания переходов. Их преимущество в простоте, но они плохо справляются с предсказанием переходов, которые изменяются со временем. Вот пример такого перехода:

if (flag) {
  // things
  }

В ходе выполнения программы на одном этапе флаг может быть установлен и переход осуществлён, а на другом этапе флага нет и переход не происходит. Статические методы никак не могут хорошо предсказывать ветвления вроде этого, так что рассмотрим динамические методы, где предсказание может изменяться в зависимости от истории выполнения программы.

Одна из простейших вещей — предсказывать на основе последнего результата, то есть предсказывать переход в том случае, если в прошлый раз он состоялся, и наоборот.

Поскольку назначать по биту на каждый переход — слишком много для разумного хранения, то сделаем таблицу для некоторого количества переходов, которые состоялись в последнее время. Для этой лекции предположим, что отсутствию перехода соответствует 0, а взятие ветви — 1.



В нашем случае, чтобы всё поместилось на иллюстрации, возьмём таблицу на 64 записи. Такое количество записей позволяет проиндексировать таблицу 6 битами, так что мы используем нижние 6 бит адреса перехода. После выполнения перехода мы обновляем состояние в таблице предсказаний (выделено внизу), а следующий раз по индексу используем уже обновлённое состояние.



Возможно, произойдёт наложение и две ветки из разных мест укажут на один и тот же адрес. Схема не идеальна, но это компромисс между скоростью работы таблицы и её размером.

Если использовать однобитную схему, то мы можем добиться точности 85%, что соответствует в среднем (0.8 + 0.85 * 0.2) * 1 + 0.15 * 0.2 * 20 = 0.97 + 0.6 = 1.57 цикла на инструкцию.



Кто использует:

• DEC EV4 (1992)
• MIPS R8000 (1994)

Два бита

Однобитная схема хорошо работает для шаблонов вида TTTTTTTT… или NNNNNNN…, но будет выдавать неправильные предсказания для потока ветвлений, где происходит большинство переходов, но один из них не происходит, ...TTTNTTT.... Это можно исправить, добавив к каждому адресу второй бит и внедрив счётчик, реализующий арифметику с насыщением. Например, будем отнимать единицу, если переход не состоялся, и добавлять единицу, если он состоялся. Результаты в двоичном виде будут такими:

00: predict Not
01: predict Not
10: predict Taken
11: predict Taken

«Насыщающая» часть счётчика означает, что если мы досчитаем до 00, то остаёмся на этом значении. Точно так же, если досчитаем до 11, то остаёмся на нём. Эта схема идентична однобитной, но только вместо одного бита в таблице предсказаний мы используем два бита.



По сравнению с однобитной схемой в двухбитной может быть вдвое меньше записей при тех же размере и стоимости (если мы учитываем только стоимость хранения, но не учитываем стоимость логики счётчика). Но даже так для любого разумного размера таблицы двухбитная схема обеспечивает лучшую точность.

Несмотря на свою простоту, схема работает довольно успешно, и мы можем ожидать повышения точности в двухбитном предикторе примерно до 90%, что соответствует 1,38 цикла на инструкцию.



Кажется логичным обобщить схему для n-битного счётчика с насыщением, но оказывается, что увеличение битности практически не влияет на точность. Мы не обсуждали цену предсказателя ветвлений, но переход с двух на три бита увеличивает размер таблицы в полтора раза ради незначительной выгоды. В большинстве случаев это не стоит того. Самые простые и наиболее распространённые случаи, которые мы не сможем хорошо предсказывать двухбитным предиктором — это шаблоны вроде NTNTNTNTNT... или NNTNNTNNT…, но переход на большее количество бит тоже не улучшит точность в этих случаях!

Кто использует:

• LLNL S-1 (1977)
• CDC Cyber? (начало 80-х)
• Burroughs B4900 (1982): состояние хранится в потоке инструкций; на аппаратноми уровне инструкция перезаписывается для обновления состояния перехода
• Intel Pentium (1993)
• PPC 604 (1994)
• DEC EV45 (1993)
• DEC EV5 (1995)
• PA 8000 (1996): в действительности реализовано в виде трёхбитного регистра сдвига с большинством голосов

Двухуровневое адаптивное глобальное предсказание переходов (1991)

Если подумать о таком коде

for (int i = 0; i < 3; ++i) {
  // code here.
  }

То он генерирует шаблон ветвлений вроде TTTNTTTNTTTN....

Если мы знаем три предыдущих результата ветвления, то можем предсказать четвёртый:

TTT:N
TTN:T
TNT:T
NTT:T

Предыдущие схемы использовали адрес ветвления для помещения индекса в таблицу, которая сообщала, состоится ли с большей вероятностью переход или нет, в зависимости от истории выполнения программы. Она говорит, в каком направлении скорее произойдёт ветвление, но не способна угадать, что мы находимся в середине повторяющегося шаблона. Чтобы исправить это, будем хранить историю большинства последних переходов, а также таблицу предсказаний.



В этом примере мы связываем четыре бита истории переходов с двумя битами адреса перехода для помещения индекса в таблицу предсказаний. Как и раньше, источником предсказания является двухбитный счётчик с насыщением. Здесь мы не хотим использовать для индекса только историю переходов. Если так сделать, то любые две ветви с одинаковой историей будут ссылаться на одну и ту же запись в таблице. В настоящем предикторе у нас, вероятно, была бы таблица большего размера и больше битов для адреса перехода, но чтобы вместить таблицу в слайд, мы вынуждены использовать шестибитный индекс.

Ниже мы видим, какое значение обновляется при осуществлении перехода.



Жирным выделены обновляемые части. На этой диаграмме мы сдвигаем новые биты истории переходов справа налево, обновляя историю ветвлений. Поскольку история обновлена, нижние биты индекса в таблице предсказаний тоже обновляются, так что в следующий раз, когда столкнёмся с этой ветвью, мы используем другое значение из таблицы для предсказания перехода, в отличие от предыдущих схем, где индекс был зафиксирован в адресе перехода.

Поскольку в этой схеме хранится глобальная история, то она правильно предскажет шаблоны вроде NTNTNTNT… во внутренних циклах, но может не всегда правильно предсказывать высокоуровневые ветвления, потому что у глобальная история засорена информацией из других ветвлений. Однако здесь компромисс в том, что хранить глобальную историю дешевле, чем таблицу локальных историй. Вдобавок, использование глобальной истории позволяет корректно предсказывать коррелированные ветви. Например, у нас может быть что-то подобное:

if x > 0:
  x -= 1
if y > 0:
  y -= 1
if x * y > 0:
  foo()

Если произойдёт переход по первой или второй ветви, то третья определённо останется незадействованной.

С этой схемой мы можем добиться точности 93%, что соответствует 1,27 цикла на инструкцию.



Кто использует:

• Pentium MMX (1996): 4-битная глобальная история переходов

Двухуровневое адаптивное локальное предсказание переходов (1992)

Как упомянуто выше, у схемы с глобальной историей есть проблема, что история локальных ветвлений засоряется другими ветвями.

Хороших локальных предсказаний можно добиться, если отдельно хранить историю локальных ветвлений.



Вместо хранения единой глобальной истории мы сохраняем таблицу локальных историй, проиндексированную по адресу перехода. Такая схема идентична глобальной схеме, которую мы только что рассматривали, за исключением хранения историй нескольких ветвлений. Можно представить глобальную историю как частный случай локальной истории, где количество хранимых историй равно 1.

С этой схемой мы можем добиться точности 94%, что соответствует 1,23 цикла на инструкцию



Кто использует:

• Pentium Pro (1996): 4-битная история локальных ветвлений, нижние биты используются для индекса. Обратите внимание, что насчёт этого вопроса ведутся споры, а Эндрю Фог заявляет, что в PPro и последующих процессорах используется 4-битная глобальная история
• Pentium II (1997): такое же, как в PPro
• Pentium III (1999): такое же, как в PPro

gshare

В глобальной двухуровневой схеме приходится идти на компромисс: в таблице предсказаний фиксированного размера биты должны соответствовать или истории переходов, или адресу перехода. Мы хотели бы выделить больше бит под историю переходов, потому что это позволит отслеживать корреляции на большем «расстоянии», а также отслеживать более сложные паттерны. Но мы также хотим отдать больше бит под адрес, чтобы избежать взаимных помех между несвязанными ветвями.

Можно попробовать решить обе задачи, применив одновременное хеширование, а не сцепление истории переходов и адреса перехода. Это одна из самых простых и разумных вещей, которые мы можем сделать, и первым кандидатом на роль механизма для этой операции приходит xor. Такая двухуровневая адаптивная схема, где мы применяем xor, называется gshare.



С этой схемой мы можем повысить точность примерно до 94%. Это такая же точность, как в локальной схеме, но в gshare не нужно хранить большую таблицу локальных историй. То есть мы получаем такую же точность при меньших затратах, что является существенным улучшением.

Кто использует:

• MIPS R12000 (1998): 2K записей, 11 бит PC, 8 бит истории
• UltraSPARC-3 (2001): 16K записей, 14 бит PC, 12 бит истории

agree (1997)

Одна из причин неправильного предсказания переходов — помехи между разными ветвями, которые ссылаются на один адрес. Есть много способов уменьшить помехи. На самом деле, в этой лекции мы рассматриваем схемы 90-х годов именно потому, что с тех пор предложено большое количество схем устранения помех, и их слишком много, чтобы уложиться в полчаса.

Посмотрим на одну схему, которая даёт общее представление о том, как может выглядеть устранение помех — это предсказатель “agree”. Когда происходит коллизия двух пар история-переход, то предсказания или совпадают, или нет. Если совпадают, мы называем это нейтральной интерференцией, а если нет, то отрицательной интерференцией. Идея в том, что большинство ветвей имеют сильный уклон в какую-то сторону (то есть если мы используем двухбитные записи в таблице предсказаний, то ожидаем, что без интерференции большинство записей бoльшую часть времени будет равняться 00 или 11, а не 01 или 10). Для каждого перехода в программе мы будем хранить один бит, который назовём “bias”. Вместо хранения абсолютных предсказаний переходов таблица будет хранить информацию о том, соответствует или не соответствует предсказание биту “bias”.



Если посмотреть, как это работает, то здесь предиктор идентичен предиктору gshare, за исключением изменения, которое мы сделали — предсказание теперь выглядит как agree/disagree (согласен или не согласен), а не taken/not-taken (переход осуществлён или не осуществлён), и у нас есть бит “bias”, который проиндексирован в адресе перехода, что даёт нам материал для принятия решения agree/disagree. Авторы оригинальной научной статьи предлагают использовать “bias” непосредственно, но другие специалисты выдвинули идею определять “bias” путём оптимизации, основанной на профилировании (по существу, когда работающая программа передаёт данные обратно компилятору).

Заметьте, что если мы выполняем переход, а затем возвращаемся назад к тому же ветвлению, то мы будем использовать тот же бит “bias”, потому что он проиндексирован адресом перехода, но мы будем использовать другую запись в таблице предсказаний, потому что она проиндексирована одновременно и адресом перехода, и историей переходов.



Если вам кажется странным, что такое изменение имеет значение, рассмотрим его на конкретном примере. Скажем, у нас есть два ветвления, ветвь A, по которой происходит переход с вероятностью 90%, и ветвь B, по которой происходит переход с вероятностью 10%. Если предположить, что вероятности переходов по каждой ветке независимы друг от друга, то вероятность принятия решения disagree и отрицательной интерференции составляет P(A taken) * P(B not taken) + P(A not taken) + P(B taken) = (0.9 * 0.9) + (0.1 * 0.1) = 0.82.

Если мы используем схему agree, мы можем повторить этот расчёт, но вероятность принятия решения disagree для двух ветвей и отрицательной интерференции составляет P(A agree) * P(B disagree) + P(A disagree) * P(B agree) = P(A taken) * P(B taken) + P(A not taken) * P(B taken) = (0.9 * 0.1) + (0.1 * 0.9) = 0.18. Другими словами, чтобы появилась деструктивная интерференция, одна из ветвей должна не согласиться с “bias”. По определению, если мы правильно определили этот бит, то вероятность этого события не может быть велика.

С этой схемой мы можем добиться точности 95%, что соответствует 1,19 цикла на инструкцию.



Кто использует:

• PA-RISC 8700 (2001)

Hybrid (1993)

Как мы видели, локальные предикторы могут хорошо предсказывать некоторые типы ветвлений (например, встроенные циклы), а глобальные предикторы хорошо справляются с другими типами (например, с некоторыми коррелированными ветвями). Можно попробовать совместить преимущества обоих предикторов и получить мета-предиктор, который предсказывает, использовать локальный или глобальный предиктор. Простой способ — использовать для мета-предиктора такую же схему, как в вышеописанном двухбитном предикторе, но только вместо предсказания taken или not taken он предсказывает локальный или глобальный предиктор.



Также как существует много схем для устранения помех, одна из которых — вышеупомянутая схема agree, также много существует гибридных схем. Мы можем использовать любые два предиктора, а не только локальный и глобальный, и количество предикторов даже бывает больше двух.

Если использовать глобальный и локальный предикторы, мы можем добиться точности 96%, что соответствует 1,15 цикла на инструкцию.



Кто использует:

• DEC EV6 (1998): комбинация локального (1k записей, 10 бит истории, 3 бита на счётчик) и глобального (4k записей, 12 бит истории, 2 бита на счётчик) предикторов
• IBM POWER4 (2001): локальный (16k записей) и gshare (16k записей, 11 бит истории, xor с адресом перехода, таблица селекторов на 16k)
• IBM POWER5 (2004): сочетание бимодального (не освещён здесь) и двухуровневого адаптивного предикторов
• IBM POWER7 (2010)

Что мы пропустили

В этой лекции мы о многом не рассказали. Как вы могли ожидать, объём пропущенного материала гораздо больше, чем того, о котором мы рассказали. Я кратко упомяну некоторые пропущенные темы со ссылками, так что вы можете почитать о них, если хотите знать больше.

Одна важная вещь, о которой мы не говорили — как предсказать целевой адрес перехода. Обратите внимание, что это нужно делать даже для некоторых безусловных переходов (то есть для переходов, которые не нуждаются в специальном предсказании, потому что они происходят в любом случае), потому что у (некоторых) безусловных переходов есть неизвестные цели.

Предсказание цели перехода настолько дорого обходится, что у некоторых ранних CPU политикой предсказания переходов было «всегда предсказывать отсутствие перехода», потому что целевой адрес перехода не потребуется, если переход отсутствует! У постоянного предсказания отсутствия переходов низкая точность, но она всё равно выше, чем если вообще не делать предсказаний.

Среди предикторов со снижением помех, которые мы не обсудили, bi-mode, gskew и YAGS. Если очень кратко, bi-mode похож на agree в том, что пытается разделить переходы по направлению, но здесь используется другой механизм: мы ведём несколько таблиц предсказаний, а третий предиктор на основе адреса перехода используется для предсказания, какую таблицу использовать для определённой комбинации перехода и истории переходов. Bi-mode кажется более успешным, чем agree, поскольку получил более широкое использование. В случае с gksew мы ведём минимум три таблицы предсказаний и отдельные хеши для внесения индекса в каждую таблицу. Идея в том, что если два перехода накладываются друг на друга в индексе, то это происходит лишь в одной таблице, так что мы можем провести голосование и результатом из двух других таблиц перекрыть потенциально плохой результат из таблицы с наложением. Я не знаю, как очень кратко описать схему YAGS :-).

Поскольку мы не говорили о скорости (задержке), то не говорили о такой стратегии предсказания как использование маленького/быстрого предиктора, результат которого может быть перекрыт более медленным и точным предиктором.

У некоторых современных CPU совершенно иные предсказатели переходов; в процессорах AMD Zen (2017) и AMD Bulldozer (2011) вроде бы используются предикторы переходов на перцептронах. Перцептроны — это одноуровневые нейронные сети.

Как утверждается, в процессоре Intel Haswell (2013) используется разновидность предиктора TAGE. TAGE означает тегированный геометрический (TAgged Geometric) предиктор с размером истории. Если изучить описанные нами предикторы и посмотреть на реальное выполнение программ — какие переходы там предсказываются неправильно, то среди них есть один большой класс: это переходы, которым нужна большая история. Значительному количеству переходов нужны десятки или сотни бит истории, а некоторым требуется даже более тысячи бит истории переходов. Если у нас единственный предиктор или даже гибридный, который сочетает несколько разных предикторов, будет неэффективным хранить тысячу бит истории, поскольку это снижает качество предсказаний для переходов, которым нужна относительно небольшая история (снижает особенно относительно цены), а таких переходов большинство. Одна из идей, заложенных в предиктор TAGE, состоит в том, чтобы сохранять геометрические длины размеров историй, и тогда каждый переход будет использовать соответствующую историю. Это объяснение части GE в аббревиатуре. Часть TA означает, что переходы помечаются тегами. Мы не обсуждали этот механизм, предиктор использует его для определения, какая история соответствует каким переходам.

В современных CPU часто используются специализированные предикторы. Например, предсказатель циклов может точно предсказывать переходы в циклах там, где общий предсказатель переходов не способен хранить разумный размер истории для идеального предсказания каждой итерации цикла.

Мы вообще не говорили о компромиссе между использованием объёма памяти и лучшими предсказаниями. Изменение размера таблицы не только меняет эффективность предиктора, но и меняет расстановку сил в том, какой предиктор лучше по сравнению с другими.

Мы также вообще не говорили о том, как разные задачи влияют на производительность предикторов разного типа. Их эффективность зависит не только от размера таблицы, но также от того, какая конкретно программа запущена.

Ещё мы обсуждали стоимость неправильного предсказания перехода так, будто это постоянная величина, но это не так, и в этом отношении стоимость инструкций без переходов тоже сильно отличается, в зависимости от типа выполняемой задачи.

Я пытался избежать непонятной терминологии где возможно, так что если будете читать литературу, там терминология немного другая.

Заключение

Мы рассмотрели ряд классических предсказателей переходов и очень кратко обсудили пару более новых предикторов. Некоторые из рассмотренных нами классических предикторов до сих пор используются в процессорах, и если бы у меня был час времени, а не полчаса, мы могли бы обсудить самые современные предикторы. Думаю, у многих людей есть мысль, что процессор — это загадочная и трудная для понимания вещь, но по моему мнению, процессоры на самом деле проще для понимания, чем программное обеспечение. Я могу быть не объективен, потому что раньше работал с процессорами, но всё-таки мне кажется, что дело не моей необъективности, а это нечто фундаментальное.

Если подумать о сложности софта, то единственным ограничивающим фактором этой сложности будет ваше воображение. Если вы можете вообразить нечто в такой подробной детализации, что это можно записать, то вы можете это сделать. Конечно, в некоторых случаях ограничивающим фактором является нечто более практичное (например, производительность крупномасштабных приложений), но я думаю, что большинство из нас проводит бoльшую часть времени за написанием программ, где ограничивающий фактор — это способность создавать и управлять сложностью.

Аппаратное обеспечение тут заметно отличается, потому что есть силы, которые противостоят сложности. Каждый кусок железа, которое вы внедряете, стоит денег, так что вы хотите использовать минимум оборудования. Вдобавок, для большинства железа важна производительность (будь то абсолютная производительность или производительность на доллар, или на ватт, или на другой ресурс), а увеличение сложности замедляет работу железа, что ограничивает производительность. Сегодня вы можете купить серийный CPU за $300, который разгоняется до 5 ГГц. На 5 ГГц одна единица работы выполняется за одну пятую наносекунды. Для информации, свет проходит примерно 30 сантиметров за одну наносекунду. Ещё один сдерживающий фактор — то, что люди весьма расстраиваются, если CPU не работает идеально всё время. Хотя у процессоров есть баги, количество багов гораздо меньше, чем почти в любом программном обеспечении, то есть стандарты для их проверки/тестирования гораздо выше. Увеличение сложности затрудняет тестирование и проверку. Поскольку процессоры придерживаются более высокого стандарта точности, чем большинство программного обеспечения, то увеличение сложности добавляет слишком тяжёлое бремя тестирования/проверки для CPU. Таким образом, одинаковое усложнение намного дороже обходится для железа, чем для софта, даже без учёта других факторов, которые мы обсуждали.

Побочный эффект этих факторов, которые противостоят усложнению микросхемы состоит в том, что каждая «высокоуровневая» функция процессора общего назначения обычно достаточно концептуально проста, чтобы описать её в получасовой или часовой лекции. Процессоры проще, чем думают многие программисты! Кстати, я сказал «высокоуровневая», чтобы исключить всякие штуки вроде устройства транзисторов и схемотехники, для понимания которых нужен определённый низкоуровневый бэкграунд (физика или электроника).