Способ и устройство для предсказания ветвлений

Способ и устройство для предсказания ветвлений

Иллюстрации

Показать все

Реферат

ОБЛАСТЬ ТЕХНИКИ, К КОТОРОЙ ОТНОСИТСЯ ИЗОБРЕТЕНИЕ

Варианты осуществления в этом документе относятся к блоку предсказания ветвлений и способу, осуществляемому в нем. В частности варианты осуществления относятся к предсказанию следующей команды выбранной ветви.

ПРЕДШЕСТВУЮЩИЙ УРОВЕНЬ ТЕХНИКИ

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

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

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

В высокопроизводительных центральных процессорах (ЦП, CPU) необходимы конвейеры с большим числом стадий обработки для получения высокой тактовой частоты. Эти процессоры с конвейерной обработкой являются эффективными при исполнении линейного кода, то есть, команд в заранее установленном последовательном порядке, но имеют трудности в исполнении команд ветвления (перехода). Изменения в потоке управления, вызываемые командами ветвления, могут вести к существенной потере рабочих характеристик. Например, ошибка в предсказании ветвлений, такая как некорректное предсказание следующей команды, может вызвать останов процессора. Некорректное предсказание может также вызывать, что конвейерно-обрабатываемая в текущий момент последовательность команд будет выталкиваться или "сбрасываться" из процессора с конвейерной обработкой, и новая последовательность команд будет загружаться в конвейер. Сброс конвейера имеет следствием циклы останова для стадии исполнения, и, следовательно, ухудшает рабочие характеристики процессора. Количество остановов, являющихся следствием сброса, пропорционально глубине конвейера и называется штрафом неверного предсказания.

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

Одна из основных функций спекулятивного препроцессора состоит в предсказании ветвлений. Предсказание ветвлений состоит из двух задач: 1) предсказания, имеется ли ветвь, которую следует выбрать, и 2) предсказания, куда перейти, то есть, предсказания целевого адресата ветвления.

Имеются два основных атрибута ветвления, имеющих последствия для функции предсказания:

1. Условие ветвления. Условные ветви выбираются только тогда, когда условие выполняется, тогда как ветви без условия ветвления выбираются всегда.

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

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

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

В US 2008/0168263 (Park) раскрыт процессор с конвейерной обработкой, содержащий блок выборки команд, принимающий команду из памяти. Блок выборки команд поставляет принятую команду на блок декодера команд, который декодирует команду и поставляет декодированную команду на исполнительный блок для исполнения. В дополнение к предоставлению принятой команды на блок декодера, блок выборки команд поставляет часть команды на блок предсказания ветвлений. Часть команды содержит адрес команды. При помощи части команды блок предсказания ветвлений предсказывает следующую команду и поставляет предсказанный адрес на блок выборки команд. Блок выборки команд осуществляет выборку команды, соответствующей предсказанному адресу, из памяти и загружает ее в конвейер. Блок предсказания ветвлений также принимает точно определенный следующий адрес от исполнительного блока, где команда была исполнена, и с помощью этого точно определенного следующего адреса блок предсказания ветвлений может определить, была ли ранее предсказанная следующая команда корректной следующей командой. Если предсказание было корректным, конвейер продолжает продвигать конвейерно-организованную последовательность команд. Однако, если предсказание было некорректным, процессор сбрасывает конвейер и загружает команду, указанную указателем следующего адреса.

US 7519798 (Chung) раскрывает систему предсказания ветвлений, содержащую процессорное ядро, предсказатель ветвлений и буфер адресатов ветвлений. Процессорное ядро может выводить информацию ветвления на предсказатель ветвлений. Информация ветвления может представлять адрес текущей команды и/или может указывать, является ли предшествующая команда командой ветвления. Предсказатель ветвлений может предсказывать ветвление для текущей команды, используя адрес текущей команды, и может выводить конечный результат предсказания ветвлений на процессорное ядро. С помощью конечного результата предсказания ветвления предсказатель ветвлений может указывать процессорному ядру, когда осуществлять выборку адреса ветвления из буфера адресатов ветвлений.

Недостаток способов и устройств, раскрытых в патентных документах US 2008/0168263 и US 7519798, состоит в том, что они основаны на работе одной команды за один раз, то есть, в каждом такте, обуславливая, что эти способы и устройства будут емкими и по времени, и по потреблению энергии.

В US 2010/0169625 (Wang) раскрыт микропроцессор с конвейерной обработкой, содержащий стадию выборки команд, на которой несколько команд выбираются из кэша команд для последующей обработки и исполнения. Команды разделяются на команды потока управления и команды, не относящиеся к потоку управления, и было определено, что только команды потока управления могут быть командами ветвления. Микропроцессор содержит кроме того буфер целевых адресатов ветвлений, таблицу истории ветвлений и блок идентификации команды управления. Блок идентификации команды управления сконфигурирован идентифицировать команды управления в извлеченной группе команд. Как только команды управления идентифицированы, доступ к буферу адресатов ветвлений и таблице истории ветвлений может быть ограничен с тем, чтобы в буфере адресатов ветвлений осуществлять поиск только команд потока управления.

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

КРАТКОЕ ОПИСАНИЕ СУЩНОСТИ ИЗОБРЕТЕНИЯ

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

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

Согласно первому аспекту представленных здесь вариантов осуществления, решение задачи изобретения обеспечивается способом в блоке предсказания ветвлений для предсказания следующей команды выбранной ветви в блоке обработки, содержащем блок предсказания ветвлений. Принимается счетчик команд, соответствующий начальному адресу слова памяти команд, и определяется «поисковый» счетчик команд на основании принятого счетчика команд. В памяти истории вариантов, содержащей несколько исходных адресатов ветвления и несколько указателей ветвления, отыскивается, по меньшей мере, один указатель ветвления, сконфигурированный для указания, по меньшей мере, одной команды предсказанной выбранной ветви, которая содержится в выполняемой ветви. Это осуществляется при помощи поискового счетчика команд. Затем первый найденный указатель ветвления выбирается в качестве указания первой команды предсказанной выбранной ветви в выполняемой ветви. При помощи первого найденного указателя ветвления адрес источника ветвления первой команды предсказанной выбранной ветви извлекают из памяти истории вариантов. Если извлеченный адрес источника ветвления является ближайшим адресом источника ветвления к поисковому счетчику команд, буфер адресатов ветвлений индексируется при помощи извлеченного адреса источника ветвления, и адресат ветвления, извлеченный из буфера адресатов ветвлений, выводится в качестве следующего счетчика команд. Затем предсказание следующей команды выбранной ветви останавливается.

Согласно второму аспекту предложенных здесь вариантов осуществления решение задачи изобретения обеспечивается блоком предсказания ветвлений для предсказания следующей команды выбранной ветви в блоке обработки, содержащем блок предсказания ветвлений. Блок предсказания ветвлений содержит память истории вариантов, каковая память истории вариантов содержит несколько исходных адресатов ветвления и несколько указателей ветвления. Указатель ветвления сконфигурирован для указания, по меньшей мере, одной команды предсказанной выбранной ветви для адреса источника ветвления. Блок предсказания ветвлений содержит кроме того буфер адресатов ветвлений, содержащий несколько адресатов ветвлений. Логическая схема предсказания ветвлений, соединенная с памятью истории вариантов и с буфером адресатов ветвлений, также содержится в блоке предсказания ветвлений. Логическая схема предсказания ветвлений сконфигурирована принимать счетчик команд, соответствующий начальному адресу слова памяти команд, и определять поисковый счетчик команд на основании принятого счетчика команд. При помощи поискового счетчика команд логическая схема предсказания ветвлений конфигурируется с возможностью отыскивать в памяти истории вариантов, по меньшей мере, один указатель ветвления. Этот, по меньшей мере, один указатель ветвления сконфигурирован для указания, по меньшей мере, одной команды предсказанной выбранной ветви, которая содержится в выполняемой ветви. Логическая схема предсказания ветвлений дополнительно сконфигурирована для выборки первого найденного указателя ветвления в качестве указания первой команды предсказанной выбранной ветви в выполняемой ветви. При помощи первого найденного указателя ветвления логическая схема предсказания ветвлений конфигурируется для извлечения из памяти истории вариантов адреса источника ветвления для первой команды предсказанной выбранной ветви. Если извлеченный адрес источника ветвления является ближайшим адресом источника ветвления к поисковому счетчику команд, логическая схема предсказания ветвлений конфигурируется для индексирования буфера адресатов ветвлений при помощи извлеченного адреса источника ветвления и вывода извлеченного адресата ветвления из буфера адресатов ветвлений в качестве следующего счетчика команд. Затем логическая схема предсказания ветвлений конфигурируется для останова предсказания следующей команды выбранной ветви.

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

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

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

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

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

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

КРАТКОЕ ОПИСАНИЕ ЧЕРТЕЖЕЙ

Примеры вариантов осуществления в документе описаны более подробно со ссылкой на прилагаемые чертежи, на которых:

Фиг. 1 - структурная схема, иллюстрирующая варианты осуществления бока обработки;

Фиг. 2 - структурная схема, иллюстрирующая варианты осуществления способа в блоке предсказания ветвлений;

Фиг. 3 - функциональная блок-схема, иллюстрирующая варианты осуществления стадий в блоке выборки команд;

Фиг. 4 - функциональная блок-схема, иллюстрирующая варианты осуществления стадий в блоке предсказания ветвлений;

Фиг. 5 - структурная схема, иллюстрирующая варианты осуществления блока предсказания ветвлений; и

Фиг. 6 - схемы вариантов осуществления памяти истории вариантов и буфера адресатов ветвлений.

ПОДРОБНОЕ ОПИСАНИЕ СУЩНОСТИ ИЗОБРЕТЕНИЯ

Варианты осуществления иллюстрируются в следующем не являющемся ограничительным описании.

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

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

На Фиг. 1 изображен блок 100 обработки, в котором могут быть реализованы варианты осуществления, предложенные здесь. Блок 100 обработки является блоком 100 конвейерной обработки. Термин "блок обработки", при его использовании здесь, охватывает любое цифровое логическое устройство или систему, способную исполнять или отвечать на последовательность команд. Данный термин охватывает, например, центральные процессоры (ЦП), микропроцессоры, цифровой процессор сигналов (DSP), процессоры с сокращенной системой команд (RISC), векторные процессоры и процессоры "с одним потоком команд и множеством потоков данных" (SIMD).

Блок 100 обработки содержит блок 101 препроцессора и блок 103 постпроцессора.

Блок 101 препроцессора сконфигурирован для выполнения обработки команд на стадиях препроцессорной обработки блока 100 конвейерной обработки. Блок 101 препроцессора содержит блок 102 выборки команд, сконфигурированный для приема счетчика команд (pc).

Счетчик команд - регистр, указывающий, где блок 100 обработки находится в своей обработке команд в последовательности команд. Счетчик команд сконфигурирован для хранения адреса команды для следующей команды, подлежащей выборке, или адреса слова памяти команд, содержащего одну или несколько команд, из числа которых подлежит выборке следующая команда.

Блок 102 выборки команд сконфигурирован для выборки команд из памяти команд 104 на основании принятого счетчика команд. Блок 102 выборки команд дополнительно сконфигурирован для сохранения выбранных команд в памяти 106 обратного магазинного типа (FIFO), соединенной с блоком 102 выборки команд.

В FIFO-памяти 106 первый сохраненный элемент также является первым элементом, который будет удаляться из FIFO-памяти 106 для его обработки. Кроме того, второй элемент, сохраненный после первого элемента, является вторым элементом, который будет удаляться из элемента FIFO и обрабатываться, и т.д. Таким образом, в том же последовательном порядке, в каком элементы сохраняются в FIFO-памяти 106, они также и удаляются из FIFO-памяти 106.

Память 104 команд может содержаться в блоке 101 препроцессора и сконфигурирована для сохранения команд. В некоторых вариантах осуществления память 104 команд выполняется в блоке 102 выборки команд. В других вариантах осуществления память 104 команд выполняется с возможностью связи с блоком 102 выборки команд. Кроме того, в некоторых вариантах осуществления память 104 команд выполняется внешней по отношению к блоку 100 обработки и с возможностью связи с блоком 100 обработки.

Блок 101 препроцессора содержит кроме того блок 500 предсказания ветвлений (BPU), сконфигурированный для выполнения предсказания ветвлений на основании принятого счетчика команд. Как проиллюстрировано на Фиг. 5, блок 500 предсказания ветвлений содержит логическую схему 502 предсказания ветвлений, память 504 истории вариантов, буфер 506 адресатов ветвлений, FIFO-память 508 и память 510 следующих переходов. Блок 500 предсказания ветвлений будет описан более подробно ниже.

Память 504 истории вариантов и буфер 506 адресатов ветвлений могут быть реализованы как кэши процессора, сконфигурированные для сохранения и предоставления часто используемой информации. Память 504 истории вариантов и буфер 506 адресатов ветвлений могут быть сконфигурированы для обеспечения информации в одном такте. Память 504 истории вариантов и буфер 506 адресатов ветвлений будут описаны более подробно ниже и со ссылкой на Фиг. 6.

Блок 103 постпроцессора сконфигурирован для выполнения обработки команд на стадиях постпроцессорной обработки в блоке 100 обработки. Блок 103 постпроцессора сконфигурирован для извлечения команд, подлежащих обработке, из FIFO-памяти 106.

Блок 103 постпроцессора содержит блок 108 декодирования команд, сконфигурированный для декодирования команд, как известно в области техники. Блок 108 декодирования команд дополнительно сконфигурирован для проверки того, является ли команда, следующая после команды непосредственного перехода в FIFO-памяти 106, корректной командой. Команда непосредственного перехода может быть командой условного перехода с непосредственной адресацией или командой безусловного перехода с непосредственной адресацией. Поскольку команда непосредственного перехода имеет адресат ветвления, закодированный в качестве части команды, блоку 108 декодирования команд будет известен адресат ветвления, когда команда декодирована. Затем блок 108 декодирования команд может сравнивать адресат ветвления с адресом команды для следующей команды в FIFO-памяти 106. Если адресат ветвления не соответствует адресу следующей команды, то следующая команда не является корректной командой, и конвейер, например, FIFO-память 106, подлежит сбросу, как описано ранее.

Кроме того, блок 108 декодирования команд может быть сконфигурирован для предоставления информации ветвления на блок 101 препроцессора.

Блок 103 постпроцессора дополнительно содержит блок 110 исполнения команд, сконфигурированный для исполнения декодированных команд. Блок 110 исполнения команд дополнительно сконфигурирован для проверки того, является ли команда, следующая за командой ветвления, то есть, командой косвенного перехода или командой непосредственного перехода, в FIFO-памяти 106 корректной командой.

Командой косвенного перехода может быть команда условного перехода с косвенной адресацией или команда безусловного перехода с косвенной адресацией. Поскольку команда косвенного перехода обращается к ячейке памяти за адресом перехода, команда косвенного перехода должна исполняться прежде, чем является известным адресат ветвления. Таким образом, блоку 110 исполнения команд адресат ветвления будет известным, когда команда исполнена. Затем блок 110 исполнения команд может сравнивать адресат ветвления с адресом команды для следующей команды в FIFO-памяти 106.

Командой непосредственного перехода может быть команда условного перехода с непосредственной адресацией или команда безусловного перехода с непосредственной адресацией. Поскольку адресат ветвления для команды непосредственного перехода закодирован как часть команды, блоку 108 декодирования команд адресат ветвления будет известным после того, как команда была декодирована. В случае команды безусловного непосредственного перехода сравнение адресата ветвления с адресом команды для следующей команды в FIFO-памяти 106 может иметь место уже после декодирования команд перехода. Для команды условного непосредственного перехода сравнение с адресом команды следующей команды в FIFO-памяти 106 может исполняться только после того, как команда условного непосредственного перехода исполнена.

Если адресат ветвления соответствует адресу следующей команды, то следующая команда является корректной командой. Если адресат ветвления не соответствует адресу следующей команды, следующая команда не является корректной командой, и конвейер, например, FIFO-память 106, подлежит сбросу.

Кроме того, блок 110 исполнения команд сконфигурирован для предоставления информации ветвления на блок 101 препроцессора.

Информация ветвления, таким образом предоставленная на блок 101 препроцессора, относится к декодированным командам ветвления или исполняемым командам ветвления и может содержать информацию о типе ветвления, например, условный или безусловный переход и непосредственный или косвенный переход, адрес команды для ветвления-источника, адрес команды для ветвления-адресата, то есть, адрес целевой команды, и/или информацию о том, была ли ветвь выбранной или нет. Блок 500 предсказания ветвлений может использовать информацию о ветвлении, чтобы обновлять память 504 истории вариантов.

Варианты осуществления способа в блоке 500 предсказания ветвлений для предсказания следующей команды выбранной ветви в блоке 100 обработки теперь будут описаны со ссылкой на блок-схему, изображенную на Фиг. 2, с дополнительной ссылкой на Фиг. 5 и 6.

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

Если для поискового счетчика команд командный переход находится под администрированием в блоке 500 предсказания ветвлений, то есть, регистрируется в блоке 500 предсказания ветвлений для этого поискового счетчика команд, блоку 500 предсказания ветвлений может потребоваться один дополнительный такт, чтобы обеспечить предсказание ветвлений. Это означает, что, когда блок 102 выборки команд и блок 500 предсказания ветвлений, оба, установлены на одинаковый адрес, то есть, имеют одинаковый счетчик команд, блоку 500 предсказания ветвлений может потребоваться один дополнительный такт, чтобы обеспечить предсказание ветвлений для этого адреса. Это, например, может иметь место после сброса конвейера и означает, что, если команды выбранной ветви имеются в слове памяти команд, которое соответствует этому адресу, блок 102 выборки команд будет уже (некорректно) перешедшим к следующему командному слову. Это некорректно выбранное командное слово может быть сброшено из конвейера согласно некоторым вариантам осуществления. Нужно отметить, что эта проблема существует только тогда, когда у блока 500 предсказания ветвлений не было возможности работать с опережением блока 102 выборки команд. Обычно блок 102 выборки команд может останавливаться часто, поскольку блок 102 выборки команд работает над одним (1) командным словом за один такт, тогда как блок 108 декодирования команд может обрабатывать только одну (1) команду за один такт. Наличие множественных команд в слове памяти может, следовательно, приводить к остановам блока 102 выборки команд. Во время этих остановов блок 500 предсказания ветвлений может работать с опережением блока 102 выборки команд, и это обычно компенсирует один такт дополнительной задержки для создания предсказания согласно некоторым вариантам осуществления.

Действия далее выполняются отдельно от и одновременно с выборкой команды в блоке 100 обработки. Это означает, что действия предсказания следующей выбранной ветви выполняются независимо от действий по выборке команд и одновременно с таковыми. Таким образом, предсказание ветвлений может выполняться независимо от выборки команды и одновременно с таковой согласно некоторым вариантам осуществления. Однако, нужно подразумевать, что действия предсказания следующей выбранной ветви можно выполнять в другом подходящем порядке, отличном от описанного ниже.

Действие 201

Принимается счетчик команд, соответствующий начальному адресу команды в слове памяти команд. Начальный адрес команды является адресом команды для первой команды, входящей в состав слова памяти команд. Слово памяти команд может содержать несколько команд, каждая команда из которых может являться командой ветвления. Это означает, что слово памяти команд может содержать множество команд перехода. Кроме того, команды могут иметь фиксированный размер команды или могут иметь переменный размер команды. Слово памяти команд может содержаться в памяти команд 104.

В некоторых вариантах осуществления предсказание следующей команды выбранной ветви инициируется сигналом «новое ветвление», посылаемым на блок 500 предсказания ветвлений. Сигнал нового ветвления указывает, что предсказание следующей команды выбранной ветви подлежит выполнению, например, указание начала программы, сброса конвейера или уточненного счетчика команд, или указание, что командное ветвление предсказывается как «выбранное» (taken), или что командное ветвление было некорректно предсказано. В основном, сигнал нового ветвления посылается всякий раз, когда счетчик команд начинает новую линейную последовательность приращений.

Блок 103 постпроцессора может посылать сигнал нового ветвления на блок 500 предсказания ветвлений, когда текущее предсказание используется для выборки следующей команды или произошел сброс в конвейере.

Действие 202

Определяют поисковый счетчик команд (поисковый pc) на основании принятого счетчика команд.

В некоторых вариантах осуществления поисковый счетчик команд соответствует или равен счетчику команд.

Действие 203

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

Указатели ветвления, содержащиеся в памяти 504 истории вариантов, именуются , причем N является количеством адресов источника ветвления, содержащихся в памяти 504 истории вариантов, и K является количеством указателей ветвления для каждого адреса источника ветвления . Таким образом, указатели ветвления для адреса источника ветвления A₀ могут именоваться , и указатели ветвления для адреса A_N источника ветвления 1 могут именоваться ,. Однако, нужно подразумевать, что количество указателей ветвления для каждого адреса источника ветвления может отличаться для различных адресов источника ветвления.

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

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

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

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

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

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

В некоторых вариантах осуществления поисковый счетчик команд отображается на индекс i истории вариантов. При помощи индекса i истории вариантов находят, по меньшей мере, один указатель ветвления. По меньшей мере, один указатель ветвления содержится в элементе памяти 504 истории вариантов, соответствующем индексу i истории вариантов.

Поисковый счетчик команд может отображаться на один индекс i истории вариантов или на несколько индексов i истории вариантов. Отображение будет описано более подробно ниже.

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

Действие 204

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

Действие 205

При помощи первого найденного указателя ветвления адрес источника ветвления извлекают из памяти 504 истории вариантов. Адрес источника ветвления является адресом источника ветвления для первой команды предсказанной выбранной ветви. Адрес источника ветвления первой предсказанной выбранной ветви используется, чтобы проверить, является ли первая команда предсказанной выбранной ветви первой командой предсказанной выбранной ветви для поискового счетчика команд, который будет проверяться в действии 206.

Действие 206

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

Действие 207

Когда извлеченный адрес источника ветвления является ближайшим адресом источника ветвления к поисков