Способ и устройство для предсказания ветвлений
Изобретение относится к области предсказаний ветвлений команд микропроцессора и, в частности, к предсказанию следующей команды выбранной ветви команд микропроцессора. Технический результат заключается в улучшении рабочих характеристик процессора с конвейерной обработкой, заключающихся в снижении энергопотребления. Технический результат достигается за счет предсказания ветвлений (BPU) для предсказания следующей команды выбранной ветви в блоке обработки. BPU содержит память истории вариантов, содержащую адреса источника ветвления и указатели ветвления, буфер адресатов ветвлений и логическую схему предсказания ветвлений. При помощи поискового счетчика команд (PC) схема находит в памяти указатель ветвления, указывающий команду предсказанной выбранной ветви. Схема выбирает первый найденный указатель ветвления, и, используя первый найденный указатель ветвления, схема извлекает из памяти адрес источника ветвления первой команды предсказанной выбранной ветви. Если извлеченным адресом источника ветвления является адрес источника ветвления, ближайший к поисковому PC, схема выводит его в качестве следующего PC адресата ветвления. Затем осуществляет останов предсказания. 5 н. и 10 з.п. ф-лы, 6 ил., 3 табл.
ОБЛАСТЬ ТЕХНИКИ, К КОТОРОЙ ОТНОСИТСЯ ИЗОБРЕТЕНИЕ
Варианты осуществления в этом документе относятся к блоку предсказания ветвлений и способу, осуществляемому в нем. В частности варианты осуществления относятся к предсказанию следующей команды выбранной ветви.
ПРЕДШЕСТВУЮЩИЙ УРОВЕНЬ ТЕХНИКИ
Микропроцессоры - электронные устройства, которые могут выполнять множество вычислительных операций в ответ на команды, которые реализуют компьютерную программу. Общий способ осуществления реализации компьютерных программ состоит в посылке множества команд в заранее установленной последовательности на исполнительный блок микропроцессора. Исполнительный блок исполняет команды в соответствии с заранее установленной последовательностью. Порядок, в котором исполняются команды, называется потоком управления. При некоторых обстоятельствах поток управления не следует линейной ветви, а переходит на команду, которая не является следующей командой в последовательности. Команды, которые вызывают переходы в потоке управления, называются командами управления, примером такой команды управления является команда ветвления. Когда команда ветвления выполняется, исполнительный блок переходит к целевой команде, идентифицированной командой ветвления, и затем исполняет целевую команду, а не следующую последовательную команду.
Микропроцессоры часто обрабатывают команды, используя несколько стадий обработки, которые могут включать в себя стадию выборки команды, на которой команды выбираются из памяти команд; стадию декодирования команд, на которой декодируют выбранные команды; стадию исполнения команд, на которой команды исполняются, и стадию обратной записи, на которой результаты исполненных команд записываются обратно в некоторый вид памяти. Для повышения быстродействия, с которым множество команд обрабатываются на различных стадиях, некоторые микропроцессоры используют способ, известный как конвейерная обработка.
В так называемом процессоре с конвейерной обработкой, содержащим множественные стадии (ступени) обработки, множественные стадии обработки одновременно выполняют различные части процесса над несколькими различными командами. В иллюстративном процессоре с конвейерной обработкой первая команда обрабатывается первой стадией процессора с конвейерной обработкой в первом такте. Во втором такте первая команд обрабатывается на второй стадии процессора с конвейерной обработкой, и вторая команда обрабатывается первой стадией. В третьем такте первая команда обрабатывается третьей стадией процессора с конвейерной обработкой, вторая команда обрабатывается второй стадией, и третья команда обрабатывается первой стадией. Эта процедура продолжается для всех команд, пока они не будут обработаны общим числом стадий обработки.
В высокопроизводительных центральных процессорах (ЦП, 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 является количеством указателей ветвления для каждого адреса источника ветвления . Таким образом, указатели ветвления для адреса источника ветвления A0 могут именоваться 
, и указатели ветвления для адреса AN источника ветвления 1 могут именоваться 
,
. Однако, нужно подразумевать, что количество указателей ветвления для каждого адреса источника ветвления может отличаться для различных адресов источника ветвления.
В некоторых вариантах осуществления таблица 504 истории вариантов является первоначально пустой, содержащей нули в каждом элементе. Однако, в некоторых других вариантах осуществления все элементы могут предварительно заполняться по заранее установленной схеме, на основании, например, статического сканирования кода компилятором.
Память 504 истории вариантов может содержать, по меньшей мере, один указатель 
ветвления, относящийся, по меньшей мере, к одной ранее выбранной команде ветвления, то есть, по меньшей мере, к одной команде ветвления, выбранной в упомянутой истории, вследствие этого используется именование «история вариантов». Эта информация истории может использоваться в предсказании предстоящих команд перехода, означая, что предсказание ветвлений основано на ранее выбранных командах ветвления.
По меньшей мере один указатель 
ветвления находят, путем поиска в памяти 504 истории вариантов при помощи поискового счетчика команд.
По меньшей мере один указатель ветвления сконфигурирован для указания, по меньшей мере, одной команды предсказанной выбранной ветви, которая входит в выполняемую ветвь.
В некоторых вариантах осуществления выполняемая ветвь начинается на значении счетчика команд и завершается на последней команде, входящей в состав слова памяти команд.
По меньшей мере один указатель ветвления может отыскиваться одновременно для множества команд, содержащихся в слове памяти команд. Это означает, что в памяти 504 истории вариантов поиск должен осуществляться одновременно для множества команд.
В некоторых вариантах осуществления поисковый счетчик команд отображается на индекс i истории вариантов. При помощи индекса i истории вариантов находят, по меньшей мере, один указатель ветвления. По меньшей мере, один указатель ветвления содержится в элементе памяти 504 истории вариантов, соответствующем индексу i истории вариантов.
Поисковый счетчик команд может отображаться на один индекс i истории вариантов или на несколько индексов i истории вариантов. Отображение будет описано более подробно ниже.
Однако можно отметить, что согласно некоторым вариантам осуществления, когда не имеется ветвлений, подлежащих отысканию в памяти 504 истории вариантов, поиск может завершаться, и блок 500 предсказания ветвлений может входить в нерабочий режим, как только он приходит к такому выводу.
Действие 204
Первый найденный указатель ветвления выбирается в качестве указания первой команде предсказанной выбранной ветви в выполняемой ветви. Это означает, что первый найденный указатель ветвления из числа всех найденных указателей ветвления рассматривают в качестве указания первой команды предсказанной выбранной ветви в выполняемой ветви.
Действие 205
При помощи первого найденного указателя ветвления адрес источника ветвления извлекают из памяти 504 истории вариантов. Адрес источника ветвления является адресом источника ветвления для первой команды предсказанной выбранной ветви. Адрес источника ветвления первой предсказанной выбранной ветви используется, чтобы проверить, является ли первая команда предсказанной выбранной ветви первой командой предсказанной выбранной ветви для поискового счетчика команд, который будет проверяться в действии 206.
Действие 206
В этом действии проверяется, является ли извлеченный адрес источника ветвления ближайшим найденным адресом источника ветвления к поисковому счетчику команд или нет. Это выполняется для проверки того, является ли первая команда предсказанной выбранной ветви первой командой предсказанной выбранной ветви для поискового счетчика команд.
Действие 207
Когда извлеченный адрес источника ветвления является ближайшим адресом источника ветвления к поисковому счетчику команд, буфер 506 адресатов ветвлений, содержащий множество адресатов ветвлений, индексируется при помощи извлеченного адреса источника ветвления. Это означает, что извлеченный адрес источника ветвления используется для осуществления доступа к корректному элементу буфера адресатов ветвлений, чтобы иметь возможность найти адресат ветвления, см. действие 208.
В некоторых вариантах осуществления это действие исполняется индексированием буфера 506 адресатов ветвлений, путем отображения извлеченного адреса источника ветвления на индекс j буфера адресатов ветвлений. Кроме того, при помощи индекса j буфера адресатов ветвлений, целевой адресат 
ветвления для извлеченного адреса источника ветвления находят в буфере 506 адресатов ветвлений, причем М является количеством адресатов ветвлений, хранимых в буфере 506 адресатов ветвлений. Адресат ветвления содержится в элементе буфера 506 адресатов ветвлений, соответствующем индексу j буфера адресатов ветвлений. Отображение будет описано более подробно ниже.
В некоторых вариантах осуществления извлеченный адрес источника ветвления отображается на единственный индекс j буфера адресатов ветвлений или на несколько индексов j буфера адресатов ветвлений.
Адресат ветвления может содержать адрес команды для следующей команды предсказанной выбранной ветви или указатель на следующую команду предсказанной выбранной ветви.
Действие 208
Адресат ветвления, извлеченный из буфера 506 адресатов ветвлений, выводится в качестве следующего значения счетчика команд. В некоторых вариантах осуществления адресат ветвления выводится на блок 102 выборки команд, который выбирает релевантную команду и сохраняет ее в FIFO-памяти 106.
Действие 209
Когда адресат ветвления был выведен в качестве следующего значения счетчика команд, предсказание следующей команды выбранной ветви останавливается или приостанавливается.
В некоторых вариантах осуществления предсказание находится в неактивном режиме, пока не будет инициировано новое предсказание сигналом «новое ветвление», как описано выше в действии 201. Это означает, что энергопотребление в блоке 500 предсказания ветвлений снижается в течение неактивного периода.
Память 504 истории вариантов и/или буфер 506 адресатов ветвлений обновляются в течение периода, когда не осуществляется предсказание следующей команды выбранной ветви. Процедура обновления будет описана более подробно ниже.
Действие 210
Когда не является известным с уверенностью, что извлеченный адрес источника ветвления будет ближайшим адресом источника ветвления к поисковому счетчику команд, извлеченный адрес () источника ветвления сохраняется в памяти 510 для следующей ветви в качестве предсказанной выбранной ветви для последующей команды в выполняемой ветви, и действия 203, 204, 205, 206, 210 продолжаются до тех пор, пока не будет найден некоторый ближайший адрес источника ветвления к поисковому счетчику команд, согласно некоторым вариантам осуществления.
Под последующей командой подразумевается команда, которая идет следующей за командой, соответствующей поисковому счетчику команд в действии 201.
В первой итерации второй найденный указатель ветвления, указывающий вторую команду предсказанной выбранной ветви в выполняемой ветви, избирается в действии 204. В действии 205 адрес источника ветвления для второй команды предсказанной выбранной ветви извлекается из памяти 504 истории вариантов. Когда адрес источника ветвления для второй команды предсказанной выбранной ветви не является ближайшим адресом источника ветвления к поисковому счетчику команд, может начинаться вторая итерация в действии 203. Когда адрес источника ветвления второй команды предсказанной выбранной ветви является ближайшим адресом источника ветвления к поисковому счетчику команд, буфер 506 адресатов ветвлений индексируется при помощи извлеченного адреса источника ветвления в действии 207. В действии 208 адресат ветвления, извлеченный из буфера 506 адресатов ветвлений, выводится в качестве следующего счетчика команд, и в действии 209 блок предсказания ветвлений останавливает предсказание следующей команды выбранной ветви.
Пример осуществления способа в блоке 500 предсказания ветвлений
При заданном некотором значении счетчика команд, блок 500 предсказания ветвлений осуществляет поиск первой предсказанной выбранной ветви в линейной выполняемой ветви, начиная от счетчика команд.
Счетчик команд является начальным адресом поиска, и поисковый счетчик команд указывает на адрес командного слова, искомый в конкретном такте.
Исполняется поиск первого, при этом также называемого ближайшим, командного ветвления, происходящего в выполняемой ветви, которая начинается со счетчика команд. Поисковый счетчик команд отображается на индекс i памяти 504 истории вариантов посредством первой функции отображения. Пример первой функции отображения для памяти 504 истории вариантов с наличием восьми (8) элементов, причем каждый элемент содержит максимально четыре (4) указателя ветвления, и при этом каждое командное ветвление вмещается в байт и память 504 истории вариантов имеет побайтовую адресацию, i=((счетчик команд)/4) по модулю 8. Поскольку имеется много больше адресов, чем индексов, каждый индекс i может быть связан со множеством поисковых счетчиков команд.
Можно допустить, что память 504 истории вариантов имеет содержимое, проиллюстрированное в Таблице 1 ниже. Как проиллюстрировано, индекс i может принимать значение между 0 и 7. Кроме того, адрес A1 источника ветвления имеет значение 4, адрес A2 источника ветвления имеет значение 72, и адрес источника ветвления A7 имеет значение 60. Кроме того, память 504 истории вариантов, иллюстрируемая в Таблице 1, содержит для каждого индекса i четыре указателя 
ветвления, каждый указатель ветвления соответствует смещению относительно адреса источника ветвления, Aj. В этом примере указатели 
ветвления соответствуют смещению в +0 байтов, указатели 
ветвления соответствуют смещению +1 байт, указатели 
ветвления соответствуют смещению +2 байта, и указатели 
ветвления соответствуют смещению +3 байта относительно соответствующего адреса 
источника ветвления. В таблице 1 командные ветвления показаны в виде BR.
| Таблица 1 | |||||
| Иллюстративное содержимое памяти 504 истории вариантов | |||||
| Указатели ветвления, BI (смещения) | |||||
| Индекс i | Адрес источника ветвления, Ai | +0 | +1 | +2 | +3 |
| 0 | |||||
| 1 | 4 | BR | |||
| 2 | 72 | BR | |||
| 3 | |||||
| 4 | |||||
| 5 | |||||
| 6 | |||||
| 7 | 60 | BR | BR |
Кроме того, можно допустить, что счетчик команд имеет значение 6, что сигнал нового ветвления является активным и принятым в блоке 500 предсказания ветвлений. Это относится к действию 201. Затем поисковый счетчик 6 команд отображается на индекс 1 при помощи первой функции отображения, описанной выше. Следовательно, в такте 0, блок 500 предсказания ветвлений, при помощи поискового счетчика команд начинает поиск указателя ветвления, указывающего командное ветвление по индексу 1, смещение +2. Это относится к действиям 202 и 203.
В Таблице 2 ниже схематично иллюстрируется поисковый счетчик команд, индекс i, смещение и предпринятое действие для следующих тактов 1-7.
Как показано, в такте 1 поисковым счетчиком команд является 6, индексом является 1 и смещением является 2, и командное ветвление не найдено. Следовательно, блок 500 предсказания ветвлений продолжает поиск.
В такте 2 поисковым счетчиком команд является 8, индексом - 2 и смещением - 0. В этом такте найдено командное ветвление BR по адресу ветвления 75. Это командное ветвление сохраняется в памяти 510 следующего ветвления в качестве ближайшего найденного командного ветвления.
В такте 3 поисковый счетчик команд имеет значение 12, индекс - 3 и смещение - 0, и командное ветвление не найдено. Следовательно, блок 500 предсказания ветвлений продолжает поиск.
В такте 4 поисковый счетчик команд имеет значение 16, индекс - 4 и смещение - 0, и командное ветвление не найдено. Следовательно, блок 500 предсказания ветвлений продолжает поиск.
В такте 5 поисковый счетчик команд имеет значение 20, индекс - 5 и смещение - 0, и командное ветвление не найдено. Следовательно, блок 500 предсказания ветвлений продолжает поиск.
В такте 6 поисковый счетчик команд имеет значение 24, индекс - 6 и смещение- 0, и командное ветвление не найдено. Следовательно, блок 500 предсказания ветвлений продолжает поиск.
В такте 7 поисковый счетчик команд имеет значение 28, индекс - 7 и смещение - 0. В этом такте командное ветвление BR найдено по адресу ветвления 60. Это командное ветвление сравнивается с ветвлением, хранимым в памяти следующего ветвления, и поскольку команда ветвления ближе к счетчику команд из действия 201, чем ветвление, хранимое в памяти следующего ветвления, вновь найденная команда ветвления сохраняется в памяти следующего ветвления в качестве ближайшего найденного командного ветвления. После 7 тактов все элементы иллюстративной памяти 504 истории вариантов были просмотрены, поиск приходит к заключению, что адрес 60 источника ветвления является адресом источника ветвления, ближайшим к поисковому счетчику команд. Это относится к действиям 203, 204, 205, 206 и 210.
| Таблица 2 | ||||
| Схематичная иллюстрация поискового счетчика команд, индекса i, смещения и предпринятого действия для тактов 1-7 | ||||
| Такт | Поисковый PC | Индекс i | Смещение | Действие |
| 1 | 6 | 1 | 2 | Продолжать поиск |
| 2 | 8 | 2 | 0 | Найден BR на 75, сохранить в качестве ближайшего найденного |
| 3 | 12 | 3 | 0 | Продолжать поиск |
| 4 | 16 | 4 | 0 | Продолжать поиск |
| 5 | 20 | 5 | 0 | Продолжать поиск |
| 6 | 24 | 6 | 0 | Продолжать поиск |
| 7 | 28 | 7 | 0 | Найден BR на 60, сохранить в качестве ближайшего найденного, все элементы просмотрены, отчет 60 |
Теперь, если бы ветвлением на адресе 75 был ветвлением на адрес 9, то вышеприведенная таблица 2 будет имеет вид таблицы 3 ниже:
| Таблица 3 | ||||
| Такт | Поисковый PC | Индекс i | Смещение | Действие |
| 1 | 6 | 1 | 2 | Продолжать поиск |
| 2 | 8 | 2 | 0 | Найден BR на 9, совпадает с поисковым PC, ближайшее найденное, отчет 9 |
Таким образом, поиск завершается или приостанавливается, когда все элементы в памяти 504 истории вариантов просмотрены, или когда было найдено командное ветвление, для которого адрес Ai источника ветвления соответствует (игнорируя смещения/последние x битов) поисковому PC (подразумевается, что ближайшее ветвление было найдено). Ближайшее ветвление, если таковые имеются, будет использоваться, чтобы индексировать буфер 506 адресатов ветвлений, посредством чего адресат ветвления извлекается из буфера 506 адресатов ветвлений и выводится в качестве следующего счетчика команд. Индексация буфера 506 адресатов ветвлений исполняется сначала преобразованием ближайшего адреса источника ветвления в индекс j в соответствии со второй функцией отображения. Пример второй функции отображения: j = (адрес источника ветвления), по модулю 64 для буфера 506 адресатов ветвлений, содержащего 64 элемента. Это относится к действиям 207-209.
Обновление памяти 504 истории вариантов и буфера 506 адресатов ветвлений
В некоторых вариантах осуществления, см., например, Фиг. 5, по меньшей мере, одно обновление истории вариантов для памяти 504 истории вариантов буферизуется в FIFO-памяти 508, и память 504 истории вариантов обновляется буферизованным, по меньшей мере, одним обновлением истории вариантов, когда не осуществляется поиск в памяти 504 истории вариантов.
По меньшей мере одно обновление истории вариантов может относиться, по меньшей мере, к одному новому или обновленному адресу источника ветвления или, по меньшей мере, к одной новой или обновленной выбранной команде ветвления, принятой от блока 103 постпроцессора, то есть, принятой от блока 108 декодирования команд и/или от блока 110 исполнения команд.
В некоторых вариантах осуществления, по меньшей мере, одно обновление буфера адресатов ветвлений для буфера 506 адресатов ветвлений буферизуется в FIFO-памяти 508, и буфер 506 адресатов ветвлений обновляется буферизованным, по меньшей мере, одним обновлением буфера адресатов ветвлений, когда буфер 506 адресатов ветвлений не индексируется.
По меньшей мере одно обновление буфера адресатов ветвлений относится, по меньшей мере, к одному новому или обновленному адресату 
ветвления.
По меньшей мере одно обновление истории вариантов и/или обновление буфера адресатов ветвлений могут быть определены, когда блок 108 декодирования команд и/или блок исполнения команд 106 после декодирования и/или исполнения команды ветвления.
Посредством буферизации обновлений в FIFO-памяти 508 и обновления памяти 504 истории вариантов и буфера 506 адресатов ветвлений, когда не происходит предсказание следующего выбранного ветвления (так называемого фонового обновления), обновление не мешает процедуре предсказания и, следовательно, не оказывает негативного влияния на рабочую характеристику блока 500 предсказания ветвлений.
Отображение поискового счетчика команд на индекс i истории вариантов, и отображение адреса источника ветвления на индекс j буфера адресатов ветвлений
Отображение поискового счетчика команд на индекс i истории вариантов и отображение адреса источника ветвления на индекс j буфера адресатов ветвлений может выполняться различным образом, что будет описано ниже, см. Фиг. 6.
Отображение с одним индексом
В некоторых вариантах осуществления отображение поискового счетчика команд на индекс i является таким, что каждое значение поискового счетчика команд, которое используется для осуществления доступа к памяти 504 истории вариантов, связывается с одиночным индексом i.
Отображение адреса источника ветвления на индекс j буфера адресатов ветвлений может также быть одиночным отображением, то есть таким, что адресом источника ветвления, который используется для осуществления доступа к буферу 506 адресатов ветвлений, связывается с одним индексом j.
Посредством отображения поискового счетчика команд и адреса источника ветвления на один индекс i и один индекс j, соответственно, энергопотребление может быть снижено или минимизировано по сравнению со случаем, когда поисковый счетчик команд и/или адрес источника ветвления отображаются на множественные индексы, поскольку такое отображение на множественные индексы потребует политики, которая определяет, какой из индексов подлежит использованию, обуславливая повышение энергопотребления. Кроме того, отображение на одиночные индексы обеспечивает недорогую реализацию. Однако, отображение поискового счетчика команд и/или адреса источника ветвления на множественные индексы может иметь следствием лучшее предсказание ветвлений и, следовательно, требовать меньшего количества сбросов конвейера, что, в свою очередь, может привести к уменьшенному энергопотреблению.
Отображая поисковый счетчик команд и адрес источника ветвления на различные индексы, то есть, на индекс i и индекс j, соответственно, размер памяти 504 истории вариантов и буфер 506 адресатов ветвлений может быть тонко настроен или оптимизирован к требуемому размеру.
Отображение с множественными индексами
В некоторых вариантах осуществления отображение поискового счетчика команд на индекс i является таким, что каждое значение поискового счетчика команд, которое используется для осуществления доступа к памяти 504 истории вариантов, связывается с несколькими индексами i.
Отображение адреса источника ветвления на индекс j буфера адресатов ветвлений также может быть множественным отображением, то есть таким, что адресом источника ветвления, который используется для осуществления доступа к буферу 506 адресатов ветвлений, связывается с несколькими индексами j.
В некоторых вариантах осуществления, содержащих отображение с множественными индексами, используется политика, для определения того, какой из множества индексов использовать для осуществления доступа к памяти 504 истории вариантов или буферу 506 адресатов ветвлений.
В качестве примера, политика может сообщать, что индекс, ссылающийся на пустой элемент, должен использоваться при сохранении новых данных в памяти 504 истории вариантов и/или буфере 506 адресатов ветвлений. Однако, в качестве другого примера, политика может сообщать, что элемент, содержащий данные, сформированные в конкретном временном окне, должны использоваться при приеме данных из памяти 504 истории вариантов и/или буфера 506 адресатов ветвлений. Путем задания отметки времени данным при сохранении данных в памяти 504 истории вариантов, является возможным определять, какой из элементов содержит необходимые данные и извлекать эти данные.
Посредством отображения поискового счетчика команд на множественные индексы i памяти 504 истории вариантов, вероятность, что два элемента, подлежащие записи в память 504 истории вариантов, отобразятся на один и тот индекс и перезапишут друг друга, меньше чем в случае, когда поисковый счетчик команд отображается на один индекс i в памяти 504 истории вариантов. То же является справедливым для отображения адреса источника ветвления на множественные индексы j буфера 506 адресатов ветвлений.
Как описано выше, посредством отображения поискового счетчика команд и адреса источника ветвления на различные индексы, размер памяти 504 истории вариантов и буфера 506 адресатов ветвлений может быть настроен или оптимизирован к требуемому размеру.
Это можно выразить альтернативным образом, обращаясь к количеству элементов в таблице 504 истории вариантов и буфере 506 адресатов ветвлений, соответственно. Можно допустить, что память 504 истории вариантов, имеющая в качестве указателя поисковый счетчик команд, индексируется индексом i и имеет n элементов. Можно допустить также, что буфер 506 адресатов ветвлений, имеющий в качестве указателя адрес источника ветвления, индексируется индексом j и имеет m элементов. Кроме того, каждый индекс i связывается с множеством поисковых счетчиков команд, и каждый поисковый счетчик команд связывается либо с одним индексом j, либо с несколькими индексами j (то есть, две альтернативы отображения, описанные ранее, причем связывание с нескольким индексами i может привести к меньшему количеству перезаписей). Кроме того, каждый индекс j связывается с несколькими адресами источника ветвления, и каждый адрес источника ветвления связывается либо с одним индексом j, либо с несколькими индексами j (то есть, две альтернативы отображения, ранее описанные, причем связывание с несколькими индексами j может привести к меньшему количеству перезаписей). Возможность настройки или оптимизации тогда можно описать в виде допускающей, что число элементов n и m должны отличаться.
Несвязное предсказание ветвлений
Предсказание следующего выбранного ветвления может быть отделено от выборки команд из памяти команд. Это означает, что блок 500 предсказания ветвлений работает автономно и отделенным от блока 102 выборки команд. Это также называется несвязным предсказанием ветвлений и будет описано более подробно ниже со ссылкой на Фиг. 3 и Фиг 4.
На Фиг. 3 изображены варианты осуществления стадий обработки, содержащихся в блоке 102 выборки команд.
На первой стадии обработки, стадии 1, принимают счетчик команд PC от логической схемы управления конвейера (не показано) в блоке 101 препроцессора или от блока 500 предсказания ветвлений (не показано на этом чертеже). Когда счетчик команд PC принимается от блока 500 предсказания ветвлений, счетчиком команд PC является адресат ветвления, выводимый из блока 500 предсказания ветвлений, как ранее описано в действии 208 выше.
Кроме того, на стадии 1, счетчик команд PC передается от блока 102 выборки команд на блок 500 предсказания ветвлений. При помощи счетчика команд блок 500 предсказания ветвлений может запустить предсказание следующей команды выбранной ветви. Это относится к действию 201, описанному выше.
На второй стадии обработки, стадии 2, блок 102 выборки команд осуществляет выборку команды из функционального блока памяти, обозначенной Mem на Фиг. 3, при помощи счетчика команд. Функциональный блок памяти соответствует памяти команд 104 на Фиг.1.
На последующих стадиях обработки, стадии 3 до стадии N, блок 103 выборки команд обрабатывает данные, содержащиеся в выбранной команде. Блок 102 выборки команд может выполнять некоторые дополнительные операции, такие как коррекция расширения или выравнивания данных команды, пока в заключение на стадии N он не передаст данные в FIFO-память 106.
На Фиг. 4 изображены варианты осуществления стадий обработки, содержащиеся в блоке 500 предсказания ветвлений.
На первой стадии обработки, стадии 1, принимается счетчик команд PC в блоке 500 предсказания ветвлений. Это относится к действию 201, ранее описанному. На Фиг. 4 проиллюстрировано, что счетчик команд принимается в функциональном блоке поиска, обозначенном Поиск, который сконфигурирован для поиска в памяти 504 истории вариантов и извлечения адреса источника ветвления первой найденной команды предсказанной выбранной ветви.
В некоторых вариантах осуществления функциональный блок поиска сконфигурирован для выполнения действий от действия 201 до действия 206, ранее описанных. Функциональный блок поиска может соответствовать или содержаться в логической схеме 502 предсказания ветвлений.
На второй стадии обработки, стадии 2, логическая схема 502 предсказания ветвлений выполняет действия 207-209, ранее описанные. Таким образом, логическая схема 502 предсказания ветвлений индексирует буфер адресатов ветвлений 406 при помощи извлеченного адреса источника ветвления и извлекает адресат ветвления для извлеченного адреса источника ветвления из буфера 506 адресатов ветвлений. Кроме того, логическая схема 502 предсказания ветвлений выводит адресат ветвления в качестве следующего счетчика команд.
На Фиг. 5 изображены варианты осуществления блока 500 предсказания ветвлений для предсказания следующей команды выбранной ветви. Как ранее упомянуто, блок 500 предсказания ветвлений содержится в блоке 100 обработки. Блок 500 предсказания ветвлений согласно некоторым вариантам осуществления может быть сконфигурирован для выполнения предсказания в течение, например, двух тактов блока 100 обработки. Однако, в других вариантах осуществления, предсказание может выполняться в течение другого числа тактов, такого как например, один такт, или n тактов, где n является произвольным целым числом, если просто упомянуть некоторые неограничительные примеры.
Поскольку блок 500 предсказания ветвлений сконфигурирован для использования поисковых счетчиков команд, которые после каждого приращения поискового счетчика команд в течение процесса поиска указывают на адреса слова памяти команд, как описано выше, для блока 500 предсказания ветвлений является возможным обрабатывать команды фиксированного размера и команды переменных размеров.
В течение каждого неостановленного такта блока 100 обработки, блок 500 предсказания ветвлений может быть сконфигурирован для обеспечения предсказания для ветвлений всех команд в слове памяти команд вплоть до первой предсказанной выбранной ветви. Таким образом, блок 500 предсказания ветвлений может быть сконфигурирован для обработки множества команд одновременно. Таким образом, блок 500 предсказания ветвлений может быть сконфигурирован, чтобы не отставать от неостановленного конвейера блока 100 обработки, который использует команды переменной длины.
Блок 500 предсказания ветвлений содержит память 504 истории вариантов, содержащую несколько адресов источника ветвления и несколько указателей ветвления. Указатель ветвления сконфигурирован для указания, по меньшей мере, одной команды предсказанной выбранной ветви для адреса источника ветвления. Память 504 истории вариантов будет описана более подробно ниже со ссылкой на Фиг.6.
Блок 500 предсказания ветвлений содержит кроме того буфер 506 адресатов ветвлений, содержащий множество адресатов ветвлений. Буфер 506 адресатов ветвлений будет описан более подробно ниже со ссылкой на Фиг. 6.
Кроме того, блок 500 предсказания ветвлений содержит логическую схему 502 предсказания ветвлений. Логическая схема 502 предсказания ветвлений соединена с памятью 504 истории вариантов и с буфером 506 адресатов ветвлений.
Логическая схема 502 предсказания ветвлений сконфигурирована для приема счетчика команд, соответствующего адресу команды, и определения поискового счетчика команд на основании принятого счетчика команд. Логическая схема 502 предсказания ветвлений может принять счетчик команд от блока 102 выборки команд.
В некоторых вариантах осуществления логическая схема 502 предсказания ветвлений сконфигурирована для запуска предсказания следующей команды выбранной ветви при приеме сигнала нового ветвления, указывающего, что предсказание следующей команды выбранной ветви подлежит выполнению, например, когда командное ветвление было предсказано как выбранное.
При помощи поискового счетчика команд логическая схема 502 предсказания ветвлений конфигурируется для отыскания в памяти 504 истории вариантов, по меньшей мере, одного указателя ветвления. По меньшей мере, один указатель ветвления сконфигурирован для указания, по меньшей мере, одной команды предсказанной выбранной ветви, которая содержится в выполняемой ветви.
В некоторых вариантах осуществления логическая схема 502 предсказания ветвлений сконфигурирована для отыскания, по меньшей мере, одного указателя ветвления, содержащегося в памяти 504 истории вариантов, одновременно для множества команд, содержащихся в слове памяти команд.
Логическая схема 502 предсказания ветвлений может быть сконфигурирована для отыскания, по меньшей мере, одного указателя ветвления в памяти 504 истории вариантов путем отображения поискового счетчика команд на индекс i истории вариантов. При помощи индекса i истории вариантов логическая схема 502 предсказания ветвлений может искать, по меньшей мере, один указатель ветвления. По меньшей мере, один указатель ветвления может содержаться в элементе памяти 504 истории вариантов, соответствующем индексу i истории вариантов.
В некоторых вариантах осуществления логическая схема 502 предсказания ветвлений сконфигурирована для отображения поискового счетчика команд на один индекс i истории вариантов или на несколько индексов j истории вариантов, как ранее описано.
Логическая схема 502 предсказания ветвлений дополнительно сконфигурирована для выборки первого найденного указателя ветвления в качестве указания первой команды предсказанной выбранной ветви в выполняемой ветви, и при помощи первого найденного указателя ветвления извлечь адрес источника ветвления из первой команды предсказанной выбранной ветви из памяти 504 истории вариантов.
Если извлеченный адрес источника ветвления является ближайшим адресом источника ветвления к поисковому счетчику команд, логическая схема 502 предсказания ветвлений конфигурируется для индексирования буфера 506 адресатов ветвлений при помощи извлеченного адреса источника ветвления ().
В некоторых вариантах осуществления логическая схема 502 предсказания ветвлений сконфигурирована с возможностью индексировать буфер 506 адресатов ветвлений путем отображения извлеченного адреса источника ветвления на индекс j буфер адресатов ветвлений.
Логическая схема 502 предсказания ветвлений может быть сконфигурирована для отображения извлеченного адреса источника ветвления на один индекс j буфера адресатов ветвлений, или несколько индексов j буфера адресатов ветвлений.
При помощи индекса j буфера адресатов ветвлений, логическая схема 502 предсказания ветвлений может отыскивать в буфере 506 адресатов ветвлений, адресат ветвления для извлеченного адреса источника ветвления. Адресат ветвления может содержаться в элементе буфера 506 адресатов ветвлений, соответствующем индексу j буфера адресатов ветвлений.
Логическая схема 502 предсказания ветвлений дополнительно сконфигурирована для извлечения адресата ветвления из буфера 506 адресатов ветвлений и вывода извлеченного адресата ветвления в качестве следующего счетчика команд. Когда следующий счетчик команд выдан, логическая схема 502 предсказания ветвлений конфигурируется для останова или приостановки предсказания следующей команды выбранной ветви, пока не будет принят сигнал нового ветвления.
В некоторых вариантах осуществления, когда извлеченный адрес источника ветвления не является адресом источника ветвления, ближайшим к поисковому счетчику команд, логическая схема 502 предсказания ветвлений дополнительно сконфигурирована, чтобы продолжать поиск.
Блок 500 предсказания ветвлений может дополнительно содержать или соединяться с FIFO памятью 508. FIFO память 508 сконфигурирована для сохранения, по меньшей мере, одного обновления истории вариантов в памяти 504 истории вариантов или, по меньшей мере, одного обновления буфера адресатов ветвлений в буфере 506 адресатов ветвлений.
По меньшей мере одно обновление истории вариантов относится, по меньшей мере, к одному новому или обновленному адресу источника ветвления или, по меньшей мере, к одной новой или обновленной выбранной команде ветвления. По меньшей мере, одно обновление буфера адресатов ветвлений относится к, по меньшей мере, одному новому или обновленному адресату ветвления.
В некоторых вариантах осуществления логическая схема 502 предсказания ветвлений сконфигурирована для буферизации, по меньшей мере, одного обновления истории вариантов для памяти 504 истории вариантов в FIFO-памяти 508 и обновления памяти 504 истории вариантов буферизованным, по меньшей мере, одним обновлением истории вариантов, когда в памяти 504 истории вариантов поиск не осуществляется. Кроме того, логическая схема 502 предсказания ветвлений может быть сконфигурирована для буферизации, по меньшей мере, одного обновления буфера адресатов ветвлений для буфера 506 адресатов ветвлений в FIFO-памяти 508 и обновления буфера 506 адресатов ветвлений буферизованным, по меньшей мере, одним обновлением буфера адресатов ветвлений, когда буфер 506 адресатов ветвлений не индексируется.
Блок 500 предсказания ветвлений может дополнительно содержать или быть соединен с памятью 510 следующего ветвления, сконфигурированной для сохранения ближайшего найденного командного ветвления, как ранее описано.
Варианты осуществления при этом также относятся к блоку 100 обработки, содержащему блок 500 адресатов ветвлений, к интегральной схеме, содержащей блок 100 обработки, и к устройству связи, содержащему интегральную схему. Такое устройство связи может содержать, например, базовую станцию, сетевой узел, ретрансляционную станцию, пользовательское оборудование или любое другое устройство, сконфигурированное для связи.
На Фиг. 6 изображены варианты осуществления памяти 504 истории вариантов и буфера 506 адресатов ветвлений.
Как ранее упомянуто, память 504 истории вариантов содержит по меньшей мере один указатель ветвления, относящийся к по меньшей мере одной ранее выбранной команде ветвления, то есть к по меньшей мере одной команде ветвления, выбранной в предыстории, откуда наименование “история вариантов”. Эта информация истории может использоваться в предсказании предстоящих команд ветвления, означая, что предсказание ветвлений основано на командах ранее исполнявшихся ветвей. Таким образом, указатель ветвления сконфигурирован для указания, по меньшей мере, одной команды предсказанной выбранной ветви для адреса источника ветвления. Однако, как символически представлено индексом K в , K указателей ветвления могут существовать для каждого адреса источника ветвления. Это означает, что для каждого адреса источника ветвления в качестве начального адреса в слове памяти команд, множество команд ветвления, содержащихся в слове памяти команд, может указываться в памяти 504 истории вариантов. Однако, нужно подразумевать, что количество указателей ветвления для каждого адреса источника ветвления может отличаться, то есть, значение K может отличаться для различных адресов источника ветвления .
Однако, согласно некоторым вариантам осуществления, когда нет ветвлений, подлежащих отысканию в памяти 504 истории вариантов, поиск может завершаться и блок 500 предсказания ветвлений может входить в нерабочий режим, как только он приходит к тому выводу.
В некоторых вариантах осуществления память 504 истории вариантов выполняется в виде таблицы и называется таблицей 504 истории вариантов. Таблица 504 истории вариантов может быть кратким перечнем, содержащим упорядоченный набор значений. Однако, нужно подразумевать, что информация истории вариантов могла бы храниться и другим подходящим образом, таким как неупорядоченный набор значений с идентификаторами, причем идентификаторы сконфигурированы для идентификации значений, содержащиеся в неупорядоченном наборе.
Как ранее упомянуто, буфер 506 адресатов ветвлений включает несколько адресатов ветвлений. В некоторых вариантах осуществления буфер 506 адресатов ветвлений сконфигурирован с возможностью содержать информацию адресатов ветвлений 
, такую как тип команды ветвления, адрес источника ветвления, и информация, является ли ветвь выбранной.
Адресат ветвления может содержать адрес команды для следующей команды предсказанной выбранной ветви или указатель на следующую команду предсказанной выбранной ветви.
Память 504 истории вариантов и буфер 506 адресатов ветвлений могут быть реализованы как кэши процессора, сконфигурированные для сохранения и предоставления часто используемой информации. Память 504 истории вариантов и буфер 506 адресатов ветвлений могут быть сконфигурированы для предоставления информации в одном такте.
На Фиг. 6 это схематично проиллюстрировано, что поисковый счетчик команд используется для осуществления доступа к памяти 504 истории вариантов и что адрес источника ветвления, принятый из памяти 504 истории вариантов, используется для осуществления доступа к буферу 506 адресатов ветвлений. Кроме того, как ранее описано, поисковый счетчик команд может отображаться на, по меньшей мере, один индекс из index0-indexi памяти 504 истории вариантов, и извлеченный адрес источника ветвления может отображаться на, по меньшей мере, один индекс из index0-indexj буфера 506 адресатов ветвлений.
При использовании слова "содержит" или "содержащий", его следует интерпретировать неограничительно, то есть, имеющим значение "состоит, по меньшей мере, из".
При использовании слова "действие/действия" его следует интерпретировать в широком смысле, а не подразумевать, что действия должны выполняться в упомянутом порядке. Вместо этого действия могут выполняться в любом подходящем порядке, отличном от упомянутого порядка. Кроме того, некоторые действие/действия могут быть необязательными.
Варианты осуществления при этом не ограничиваются вышеописанными предпочтительными вариантами осуществления. Могут использоваться различные альтернативы, модификации и эквиваленты.
Следовательно, вышеупомянутые варианты осуществления не должны рассматриваться в качестве ограничения объема изобретения, который определяется прилагаемой формулой изобретения.
1. Способ в блоке (500) предсказания ветвлений для предсказания следующей команды выбранной ветви в процессорном блоке (100), содержащем блок (500) предсказания ветвлений, при этом способ содержит этапы, на которых:
принимают из счетчика команд соответствующий адрес команды (действие 201);
определяют поисковый счетчик команд на основе адреса команды, принятого из счетчика команд (действие 202);
при помощи поискового счетчика команд находят в памяти (504) истории вариантов, в которой содержится множество адресов источников ветвления и множество указателей ветвления, по меньшей мере один указатель ветвления, сконфигурированный для указания по меньшей мере одной команды предсказанной выбранной ветви, которая входит в выполняемую ветвь (действие 203);
выбирают первый найденный указатель ветвления в качестве указания первой команды предсказанной выбранной ветви в выполняемой ветви (действие 204);
при помощи первого найденного указателя ветвления извлекают из памяти (504) истории вариантов адрес источника ветвления для первой команды предсказанной выбранной ветви (действие 205); и
когда извлеченный адрес источника ветвления является адресом источника ветвления, ближайшим к поисковому счетчику команд,
индексируют буфер (506) адресатов ветвлений при помощи извлеченного адреса источника ветвления (действие 207),
выводят адресат ветвления, извлеченный из буфера (506) адресатов ветвлений, в качестве следующего счетчика команд (действие 208) и
останавливают предсказание следующей команды выбранной ветви (действие 209).
2. Способ по п. 1, дополнительно содержащий этап, на котором, если извлеченный адрес источника ветвления не является адресом источника ветвления, ближайшим к поисковому счетчику команд, продолжают поиск (действие 210).
3. Способ по п. 1, в котором нахождение по меньшей мере одного указателя ветвления в памяти (504) истории вариантов для по меньшей мере одного указателя ветвления выполняется одновременно, в течение одного такта, для множества команд, содержащихся в слове памяти команд.
4. Способ по п. 1, дополнительно содержащий этапы, на которых:
буферизуют по меньшей мере одно обновление памяти (504) истории вариантов или по меньшей мере одно обновление буфера (506) адресатов ветвлений в FIFO-памяти (508); и
обновляют память (504) истории вариантов или буфер (506) адресатов ветвлений буферизованным по меньшей мере одним обновлением, когда в памяти (504) истории вариантов или буфере (506) адресатов ветвлений не осуществляется поиск.
5. Способ по п. 1, который выполняется в течение двух тактов процессорного блока (100).
6. Блок (500) предсказания ветвлений для предсказания следующей команды выбранной ветви в процессорном блоке (100), содержащем блок (500) предсказания ветвлений, при этом блок (500) предсказания ветвлений отличается тем, что содержит:
память (504) истории вариантов, содержащую множество адресов источника ветвления и множество указателей ветвления, причем указатель ветвления сконфигурирован для указания по меньшей мере одной команды предсказанной выбранной ветви для адреса источника ветвления;
буфер (506) адресатов ветвлений, содержащий множество адресатов ветвлений; и
логическую схему (502) предсказания ветвлений, соединенную с памятью (504) истории вариантов и с буфером (506) адресатов ветвлений, при этом логическая схема (502) предсказания ветвлений сконфигурирована:
принимать из счетчика команд адрес команды, соответствующий начальному адресу слова памяти команд,
определять поисковый счетчик команд на основе адреса команды, принятого из счетчика команд;
при помощи поискового счетчика команд находить в памяти (504) истории вариантов по меньшей мере один указатель ветвления, причем этот по меньшей мере один указатель ветвления сконфигурирован для указания по меньшей мере одной команды предсказанной выбранной ветви, которая входит в выполняемую ветвь;
выбирать первый найденный указатель ветвления в качестве указания первой команды предсказанной выбранной ветви в выполняемой ветви;
при помощи первого найденного указателя ветвления извлекать из памяти (504) истории вариантов адрес источника ветвления для первой команды предсказанной выбранной ветви;
если извлеченный адрес источника ветвления является ближайшим адресом источника ветвления к поисковому счетчику команд,
индексировать буфер (506) адресатов ветвлений при помощи извлеченного адреса источника ветвления,
выводить извлеченный адресат ветвления из буфера (506) адресатов ветвлений в качестве следующего счетчика команд и
останавливать предсказание следующей команды выбранной ветви.
7. Блок (500) предсказания ветвлений по п. 6, отличающийся тем, что логическая схема (502) предсказания ветвлений дополнительно сконфигурирована, когда извлеченный адрес источника ветвления не является адресом источника ветвления, ближайшим к поисковому счетчику команд, продолжать поиск адреса источника ветвления, который является адресом источника ветвления, ближайшим к поисковому счетчику команд.
8. Блок (500) предсказания ветвлений по п. 6, отличающийся тем, что логическая схема (502) предсказания ветвлений сконфигурирована находить по меньшей мере один указатель ветвления, содержащийся в памяти (504) истории вариантов, одновременно для множества команд, содержащихся в слове памяти команд.
9. Блок (500) предсказания ветвлений по п. 6, отличающийся тем, что логическая схема (502) предсказания ветвлений сконфигурирована находить по меньшей мере один указатель ветвления в памяти (504) истории вариантов посредством:
отображения поискового счетчика команд на индекс i истории вариантов и
нахождения при помощи индекса i истории вариантов по меньшей мере одного указателя ветвления, причем этот по меньшей мере один указатель ветвления содержится в элементе памяти (504) истории вариантов, соответствующем индексу i истории вариантов.
10. Блок (500) предсказания ветвлений по п. 6, отличающийся тем, что содержит:
FIFO-память (508), сконфигурированную сохранять по меньшей мере одно обновление памяти (504) истории вариантов или буфера (506) адресатов ветвлений,
при этом логическая схема (502) предсказания ветвлений сконфигурирована буферизовать по меньшей мере одно обновление памяти (504) истории вариантов или буфера (506) адресатов ветвлений в FIFO-памяти (508) и сконфигурирована обновлять память (504) истории вариантов или буфер (506) адресатов ветвлений буферизованным по меньшей мере одним обновлением, когда в памяти (504) истории вариантов не осуществляется поиск или когда буфер (506) адресатов ветвлений не индексируется.
11. Блок (500) предсказания ветвлений по п. 10, отличающийся тем, что упомянутое по меньшей мере одно обновление относится к по меньшей мере одному новому или обновленному адресу источника ветвления, к по меньшей мере одной новой или обновленной команде выбранной ветви или к по меньшей мере одному новому или обновленному адресату ветвления.
12. Блок (500) предсказания ветвлений по п. 6, отличающийся тем, что логическая схема (502) предсказания ветвлений сконфигурирована запускать предсказание следующей команды выбранной ветви по приему сигнала нового ветвления, указывающего, что должно быть выполнено предсказание следующей команды выбранной ветви.
13. Процессорный блок (100), содержащий блок (500) предсказания ветвлений по любому из пп. 6-12.
14. Интегральная схема, выполненная с возможностью предсказания ветвлений, содержащая процессорный блок (100) по п. 13.
15. Устройство связи, содержащее интегральную схему по п. 14.
