Предсказатель переходов в цифровых схемах

Введение

Цифровая схема

В компьютерной архитектуре предсказатель ветвлений — это цифровая схема, которая пытается угадать, по какой ветви пойдет переход (например, структура if–then–else) до того, как это станет окончательно известно. Цель предсказателя ветвлений — улучшить пропускную способность конвейера команд. Предсказатели ветвлений играют критически важную роль в достижении высокой производительности во многих современных конвейерных архитектурах микропроцессоров. Двойное ветвление обычно реализуется с помощью инструкции условного перехода. Условный переход может быть либо "выполнен" (taken) и перенаправить выполнение в другое место в памяти программы, либо "не выполнен" (not taken) и продолжить выполнение сразу после инструкции условного перехода. До тех пор, пока условие не будет вычислено и инструкция условного перехода не достигнет стадии выполнения в конвейере команд (см. рис. 1), неизвестно наверняка, будет ли выполнен условный переход или нет. Без предсказания ветвлений процессору пришлось бы ждать, пока инструкция условного перехода не пройдет стадию выполнения, прежде чем следующая инструкция сможет войти в стадию выборки (fetch) в конвейере. Предсказатель ветвлений пытается избежать этой потери времени, пытаясь угадать, с большей вероятностью условный переход будет выполнен или нет. Затем выбирается и спекулятивно выполняется ветвь, которая, как предполагается, является наиболее вероятной. Если впоследствии обнаруживается, что предположение было неверным, спекулятивно выполненные или частично выполненные инструкции отбрасываются, и конвейер перезапускается с правильной ветви, что приводит к задержке. Время, теряемое в случае ошибочного предсказания ветвления, равно количеству стадий в конвейере от стадии выборки до стадии выполнения. Современные микропроцессоры, как правило, имеют довольно длинные конвейеры, поэтому задержка при ошибочном предсказании составляет от 10 до 20 тактовых циклов. Следовательно, увеличение длины конвейера повышает потребность в более совершенном предсказателе ветвлений. В первый раз, когда встречается инструкция условного перехода, информации для предсказания немного. Однако предсказатель ветвлений ведет статистику выполненных и не выполненных переходов. Когда он сталкивается с условным переходом, который встречался ранее несколько раз, он может основывать предсказание на истории. Например, предсказатель ветвлений может определить, что условный переход выполняется чаще, чем не выполняется, или что он выполняется каждый второй раз. Предсказание ветвлений отличается от предсказания цели ветвления. Предсказание ветвлений пытается угадать, будет ли выполнен условный переход или нет. Предсказание цели ветвления пытается угадать цель выполненного условного или безусловного перехода до того, как она будет вычислена путем декодирования и выполнения самой инструкции. Предсказание ветвлений и предсказание цели ветвления часто объединяются в одну и ту же схему.

In computer architecture, a branch predictor is a digital circuit that tries to guess which way a branch (e. g., an if–then–else structure) will go before this is known definitively. The purpose of the branch predictor is to improve the flow in the instruction pipeline. Branch predictors play a critical role in achieving high performance in many modern pipelined microprocessor architectures. Two way branching is usually implemented with a conditional jump instruction. A conditional jump can either be "taken" and jump to a different place in program memory, or it can be "not taken" and continue execution immediately after the conditional jump. It is not known for certain whether a conditional jump will be taken or not taken until the condition has been calculated and the conditional jump has passed the execution stage in the instruction pipeline (see fig. 1). Without branch prediction, the processor would have to wait until the conditional jump instruction has passed the execute stage before the next instruction can enter the fetch stage in the pipeline. The branch predictor attempts to avoid this waste of time by trying to guess whether the conditional jump is most likely to be taken or not taken. The branch that is guessed to be the most likely is then fetched and speculatively executed. If it is later detected that the guess was wrong, then the speculatively executed or partially executed instructions are discarded and the pipeline starts over with the correct branch, incurring a delay. The time that is wasted in case of a branch misprediction is equal to the number of stages in the pipeline from the fetch stage to the execute stage. Modern microprocessors tend to have quite long pipelines so that the misprediction delay is between 10 and 20 clock cycles. As a result, making a pipeline longer increases the need for a more advanced branch predictor. The first time a conditional jump instruction is encountered, there is not much information to base a prediction on. But the branch predictor keeps records of whether branches are taken or not taken. When it encounters a conditional jump that has been seen several times before, then it can base the prediction on the history. The branch predictor may, for example, recognize that the conditional jump is taken more often than not, or that it is taken every second time. Branch prediction is not the same as branch target prediction. Branch prediction attempts to guess whether a conditional jump will be taken or not. Branch target prediction attempts to guess the target of a taken conditional or unconditional jump before it is computed by decoding and executing the instruction itself. Branch prediction and branch target prediction are often combined into the same circuitry.

Предсказание статической ветви

Статическое предсказание является простейшей техникой предсказания ветвлений, поскольку оно не опирается на информацию о динамической истории выполнения кода. Вместо этого, оно предсказывает исход ветвления, основываясь исключительно на самой инструкции ветвления. Ранние реализации SPARC и MIPS (две из первых коммерческих RISC-архитектур) использовали однонаправленное статическое предсказание ветвлений: они всегда предсказывали, что условный переход не будет выполнен, и поэтому всегда извлекали следующую последовательную инструкцию. Только когда ветвление или переход вычисляется и обнаруживается, что он был выполнен, указатель инструкции устанавливается на не последовательный адрес. Оба процессора вычисляют ветвления на стадии декодирования и имеют одноцикловый захват инструкций. В результате, время восстановления целевого адреса ветвления составляет два цикла, и процессор всегда извлекает инструкцию, следующую непосредственно за выполненным ветвлением. Обе архитектуры определяют слоты задержки ветвлений для использования этих извлеченных инструкций. Более продвинутая форма статического предсказания предполагает, что обратные ветвления будут выполнены, а прямые – нет. Обратное ветвление – это ветвление, у которого целевой адрес меньше его собственного адреса. Этот метод может повысить точность предсказания циклов, которые обычно являются обратными ветвлениями и выполняются чаще, чем не выполняются. Некоторые процессоры позволяют вставлять в код подсказки для предсказания ветвлений, чтобы указать, следует ли выполнять статическое предсказание или нет. Intel Pentium 4 принимал подсказки для предсказания ветвлений, но эта функция была упразднена в более поздних процессорах Intel. Статическое предсказание используется как резервная техника в некоторых процессорах с динамическим предсказанием ветвлений, когда динамические предсказатели не располагают достаточной информацией для работы. И Motorola MPC7450 (G4e), и Intel Pentium 4 используют эту технику в качестве резервной. В статическом предсказании все решения принимаются на этапе компиляции, до выполнения программы.

Двухуровневый прогнозный индикатор

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

Двухуровневый адаптивный предиктор

Если оператор if выполняется три раза, решение, принятое при третьем выполнении, может зависеть от того, были ли выполнены предыдущие два. В таких сценариях двухуровневый адаптивный предсказатель работает эффективнее, чем счетчик насыщения. Условные переходы, которые выполняются каждый второй раз или имеют другую регулярно повторяющуюся закономерность, плохо предсказываются счетчиком насыщения. Двухуровневый адаптивный предсказатель запоминает историю последних n обращений к ветвлению и использует один счетчик насыщения для каждого из возможных 2n исторических шаблонов. Этот метод иллюстрирован на рисунке 3. Рассмотрим пример n = 2. Это означает, что последние два обращения к ветвлению хранятся в двухбитовом сдвиговом регистре. Этот регистр истории ветвлений может иметь четыре различных двоичных значения: 00, 01, 10 и 11, где ноль означает "не выполнено", а единица – "выполнено". Таблица истории шаблонов содержит четыре записи для каждого ветвления, по одной для каждой из 22 = 4 возможных историй ветвлений, и каждая запись в таблице содержит двухбитный счетчик насыщения того же типа, что и на рисунке 2, для каждого ветвления. Регистр истории ветвлений используется для выбора одного из четырех счетчиков насыщения. Если история 00, то используется первый счетчик; если история 11, то используется последний из четырех счетчиков. Предположим, например, что условный переход выполняется каждые три раза. Последовательность ветвлений: 001001001. В этом случае запись номер 00 в таблице истории шаблонов перейдет в состояние "сильно выполнено", указывая, что после двух нулей следует единица. Запись номер 01 перейдет в состояние "сильно не выполнено", указывая, что после 01 следует ноль. То же самое относится к записи номер 10, в то время как запись номер 11 никогда не используется, поскольку никогда не бывает двух последовательных единиц. Общее правило для двухуровневого адаптивного предсказателя с n-битной историей заключается в том, что он может предсказать любую повторяющуюся последовательность с любым периодом, если все n-битные подпоследовательности различны. С момента первой публикации в 1991 году этот метод стал очень популярным. Варианты этого метода прогнозирования используются в большинстве современных микропроцессоров.

If an if statement is executed three times, the decision made on the third execution might depend upon whether the previous two were taken or not. In such scenarios, a two level adaptive predictor works more efficiently than a saturation counter. Conditional jumps that are taken every second time or have some other regularly recurring pattern are not predicted well by the saturating counter. A two level adaptive predictor remembers the history of the last n occurrences of the branch and uses one saturating counter for each of the possible 2n history patterns. This method is illustrated in figure 3. Consider the example of n = 2. This means that the last two occurrences of the branch are stored in a two bit shift register. This branch history register can have four different binary values, 00, 01, 10, and 11, where zero means "not taken" and one means "taken". A pattern history table contains four entries per branch, one for each of the 22 = 4 possible branch histories, and each entry in the table contains a two bit saturating counter of the same type as in figure 2 for each branch. The branch history register is used for choosing which of the four saturating counters to use. If the history is 00, then the first counter is used; if the history is 11, then the last of the four counters is used. Assume, for example, that a conditional jump is taken every third time. The branch sequence is 001001001 In this case, entry number 00 in the pattern history table will go to state "strongly taken", indicating that after two zeroes comes a one. Entry number 01 will go to state "strongly not taken", indicating that after 01 comes a zero. The same is the case with entry number 10, while entry number 11 is never used because there are never two consecutive ones. The general rule for a two level adaptive predictor with an n bit history is that it can predict any repetitive sequence with any period if all n bit sub sequences are different. Since the initial publication in 1991, this method has become very popular. Variants of this prediction method are used in most modern microprocessors.

Двухуровневый нейронный предиктор

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

Прогноз местного филиала

У локального предсказателя ветвлений есть отдельный буфер истории для каждой инструкции условного перехода. Он может использовать двухуровневый адаптивный предсказатель. Буфер истории отделен для каждой инструкции условного перехода, в то время как таблица истории шаблонов может быть отдельной, либо совместно использоваться для всех условных переходов. Процессоры Intel Pentium MMX, Pentium II и Pentium III используют локальные предсказатели ветвлений с локальной 4-битной историей и локальной таблицей истории шаблонов, содержащей 16 записей для каждого условного перехода. На эталонных тестах SPEC'89 очень большие локальные предсказатели достигают точности 97,1% и перестают улучшаться. Комбинированный подход объединяет принципы локального и глобального предсказания, объединяя локальную и глобальную историю ветвлений, возможно, с некоторыми битами счётчика команд. Результаты тестов указывают на то, что процессор VIA Nano может использовать эту технику.

Гибридный предсказатель

Гибридный предиктор, также называемый комбинированным предиктором, реализует более одного механизма прогнозирования. Итоговое предсказание основывается либо на мета-предсказателе, который запоминает, какой из предикторов давал лучшие результаты в прошлом, либо на функции голосования большинства, основанной на нечетном количестве различных предикторов. Скотт Макфарлинг предложил комбинированное предсказание переходов в своей статье 1993 года. Новые процессоры от Intel и AMD могут предсказывать косвенные переходы, используя двух уровневый адаптивный предиктор. Этот тип инструкции вносит вклад в буфер истории более чем одним битом. Процессоры zEC12 и более поздние процессоры z/Architecture от IBM поддерживают инструкцию, которая может предварительно загрузить запись предиктора переходов для данной инструкции целевым адресом перехода, сформированным путем добавления содержимого регистра общего назначения к непосредственному смещению. Процессоры, не имеющие этого механизма, просто предскажут косвенный переход к той же цели, что и в прошлый раз.