СПОСОБЫ И УСТРОЙСТВА ДЛЯ ПРОАКТИВНОГО УПРАВЛЕНИЯ КЭШЕМ АДРЕСОВ ВЕТВЛЕНИЙ Российский патент 2011 года по МПК G06F9/38 G06F12/00 

Описание патента на изобретение RU2421783C2

Область техники

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

Уровень техники

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

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

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

Одна известная форма прогнозирования ветвлений включает в себя разделение прогнозирования ветвлений на два модуля прогнозирования: начальный кэш адресов ветвлений (BTAC) и таблица истории ветвлений (BHT). BTAC, так же известный, как буфер адресов ветвлений (BTB), индексируется посредством адреса вызова инструкций и содержит следующий вызванный адрес, также упоминаемый как адрес ветвления, соответствующий адресу вызова инструкций. Записи добавляются в традиционный BTAC после того, как инструкция ветвления прошла через процессорный конвейер, и ее ветвление осуществлено. Если традиционный BTAC полон, записи традиционно удаляются из BTAC с помощью стандартных алгоритмов замены в кэше (таких как циклический алгоритм или "дольше всех не использовался"), когда добавляется следующая запись.

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

BTAC, в общем, используются вместе с более точным модулем прогнозирования направления отдельных ветвлений, таким как таблица истории ветвлений (Branch History Table, BHT), так же известная, как таблица истории шаблонов (Pattern History Table, PHT). К традиционным BHT осуществляется доступ на более поздней стадии в конвейере, чем к традиционным BTAC. По существу, дополнительная информация может потенциально присутствовать для того, чтобы выполнять более оптимальное прогнозирование. Традиционная BHT может содержать набор насыщенных счетчиков прогнозных направлений, чтобы формировать более точное решение "осуществлено/не осуществлено" для отдельных инструкций ветвления. Например, каждый насыщенный счетчик прогнозных направлений может содержать двухбитовый счетчик, который допускает одно из четырех состояний, каждому из которых назначено взвешенное значение прогнозирования, например:

11 - строгое прогнозирование "осуществлено",

10 - нестрогое прогнозирование "осуществлено",

01 - нестрогое прогнозирование "не осуществлено",

00 - строгое прогнозирование "не осуществлено".

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

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

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

Раскрытие изобретения

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

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

Другой вариант осуществления относится к способу управления кэшем адресов ветвлений (BTAC). Направление ветвления традиционной инструкции ветвления, которое фактически разрешено, принимается. Информация состояния схемы модуля прогнозирования ветвления оценивается в ответ на принятое направление ветвления. Запись в BTAC, связанная с инструкцией условного ветвления, управляется согласно информации состояния схемы модуля прогнозирования ветвлений.

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

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

Краткое описание чертежей

Фиг. 1 - функциональная блок-схема процессора.

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

Фиг. 3 - функциональная блок-схема первого примерного варианта осуществления схемы сигналов управления BTAC.

Фиг. 4 - функциональная блок-схема второго примерного варианта осуществления схемы сигналов управления BTAC.

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

Фиг. 6 - это блок-схема последовательности операций, иллюстрирующая способ уменьшения вероятности нескольких циклов очистки конвейера.

Подробное описание изобретения

Фиг. 1 иллюстрирует функциональную блок-схему процессора 100. Процессор 100 приводит в исполнение инструкции в конвейере 112 приведения в исполнение инструкций согласно управляющей логике 114. В некоторых вариантах осуществления конвейер 112 может иметь суперскалярную архитектуру с несколькими параллельными конвейерами. Конвейер 112 включает в себя различные регистры или триггеры-защелки 116A-D, организованные в ступени конвейера, и один или более модулей приведения в исполнение, таких как арифметико-логическое устройство (Arithmetic Logic Unit, ALU) 18. Файл 20 регистров общего назначения (General Purpose Register, GPR) предоставляет регистры, составляющие вершину иерархии памяти.

Доступ к данным осуществляется из кэша данных (D-кэша) 140, причем преобразование адресов памяти и разрешения управляются посредством основного буфера быстрой переадресации (Translation Lookaside Buffer, TLB) 142. В различных вариантах осуществления ITLB 124 может содержать копию части TLB 142. Альтернативно ITLB 124 и TLB 142 могут быть интегрированы. Аналогично, в различных вариантах осуществления процессора 100 I-кэш 122 и D-кэш 140 могут быть интегрированы или объединены. Промахи в I-кэше 122 и/или D-кэше 140 вызывают доступ в основную (вне микросхемы) память 144 под управлением интерфейса 146 памяти.

Процессор 100 может включать в себя интерфейс 148 ввода/вывода (I/O), управляющий доступом к различным периферийным устройствам 150. Специалисты в области техники признают, что возможны многочисленные вариации процессора 100. Например, процессор 100 может включать в себя кэш второго уровня (L2) либо для одного из двух, либо для обоих I- и D-кэшей 122, 140. Помимо этого один или более функциональных блоков, проиллюстрированных в процессоре 100, могут быть опущены из конкретного варианта осуществления.

Процессор 100 включает в себя систему 143 многостадийного прогнозирования ветвлений. Система 143 многостадийного прогнозирования ветвлений включает в себя BTAC 141 (первую стадию) и схему 126 модуля прогнозирования ветвлений (вторую стадию). BTAC 141 выполнен с возможностью сохранять одну или более записей, причем каждая запись содержит адрес результата выполнения ветвления, соответствующий адресу вызова. Модуль 128 предварительного вызова инструкций вызывает инструкции из кэша 122 инструкций (I-кэша, или I$), причем трансляция адресов памяти и разрешения управляются посредством буфера быстрого преобразования адреса команд (Instruction-side Translation Lookaside Buffer, ITLB) 124. Система 143 многостадийного прогнозирования ветвлений определяет то, попадает ли адрес вызова в BTAC 141, прогнозирует направление инструкции ветвления посредством использования сохраненных шаблонов прогнозирования в схеме 126 модуля прогнозирования ветвлений и обновляет BTAC 141 на основе состояния сохраненных шаблонов прогнозирования в схеме 126 модуля прогнозирования ветвлений. Система 143 многостадийного прогнозирования ветвлений, а также работа модуля 128 предварительного вызова инструкций и конвейера 112 описывается подробнее в связи с описанием по фиг. 2.

Фиг. 2 - это функциональная блок-схема системы 143 модуля прогнозирования ветвлений по фиг. 1. Конвейер 112 и модуль 128 предварительного вызова инструкций включают в себя одну или более стадий обработки. Схема 126 модуля прогнозирования инструкций может включать в себя регистр 203 истории ветвлений, таблицу истории ветвлений (BHT) 207 и схему 205 логики прогнозирования и обновления таблицы ветвлений. Примерные варианты осуществления секции управления BTAC схемы 205 логики прогнозирования и обновления таблицы ветвлений описываются в связи с фиг. 3 и 4.

При работе адрес вызова отыскивается в BTAC 141 по пути 219, чтобы определять то, соответствует ли он инструкции осуществленного ветвления, которая ранее обработана посредством конвейера 112. Модуль 128 предварительного вызова инструкций «по предположению» предварительно вызывает инструкции из кэша 122 инструкций по пути 221, начиная с адреса ветвления, возвращенного из BTAC 141 для ветвей, неявно спрогнозированных как "осуществлено", или начиная со следующего последовательного адреса для ветвей, неявно спрогнозированных как "не осуществлено". В любом случае предварительно вызванные инструкции загружаются в модуль 128 предварительного вызова инструкций по пути 223.

Когда инструкция условного ветвления обработана посредством стадий модуля 128 предварительного вызова инструкций или конвейера 112, определяется дополнительная информация об инструкции условного ветвления, такая как информация, переносимая в битах предварительного декодирования, вызванных из I-кэша 122 по пути 223. Схема 126 модуля прогнозирования ветвления, используя сохраненные шаблоны прогнозирования и эту дополнительную информацию, активируется по пути 121, чтобы прогнозировать с более высоким уровнем доверия, чем поиск в BTAC, направление инструкции условного ветвления.

Схема 205 логики прогнозирования и обновления таблицы ветвлений использует адрес инструкций ветвления, регистр истории ветвлений (BHR) 203 и таблицу истории ветвлений (BHT) 207 для того, чтобы прогнозировать направления инструкции условного ветвления. BHR 203 выступает в качестве сдвигового регистра для инструкции условного ветвления. Например, если инструкция условного ветвления фактически осуществлена, “1” сдвигается в BHR 203. Если инструкция условного ветвления фактически не осуществлена, “0” сдвигается в BHR 203, приводя к тому, что BHR 203 сохраняет архивное направление ветвления для конкретной инструкции ветвления. В одном варианте осуществления BHR 203 включает в себя специальный регистр для каждой инструкции ветвления, обработанной посредством конвейера 112 за период времени. В другом варианте осуществления BHR 203 может иметь глобальную область, которая содержит предыдущее направление ветвления для недавно обработанных инструкций условного ветвления. BHT 207 может включать в себя двухбитовые счетчики для конкретной инструкции ветвления, как описано в разделе уровня техники выше. Следует отметить, что различные известные методы для прогнозирования направления ветвления могут использовать BHR 203 и BHT 207. Также следует отметить, что эти известные методы прогнозирования используют различные реализации BHR 203 и BHT 207. Также следует отметить, что данное раскрытие предполагает использование других методов прогнозирования, которые реализуют альтернативы для BHR или BHT.

На основе BHR 203 и BHT 207 схема 126 модуля прогнозирования направления ветвлений в примере, проиллюстрированном на фиг. 2, прогнозирует направление ветвления, которое конфликтует с неявным прогнозированием BTAC 141. Как результат, все из инструкций выше "осуществленного пути1", размещения стадии инструкции условного ветвления должны извлекаться из модуля 128 предварительного вызова инструкций. Без конфликта модуль 128 предварительного вызова инструкций должен продолжить предварительно вызывать инструкции, которые начались с адреса ветвления.

По мере того как инструкция условного ветвления проходит через стадии конвейера 112, инструкция условного ветвления достигает стадии, где условие фактически разрешается. Если фактическое разрешение ветви отличается от прогноза схемы 126 модуля прогнозирования ветвлений, все инструкции выше инструкции условного ветвления извлекаются из конвейера 112 и модуля 128 предварительного вызова инструкций. На стадии фактического разрешения ветвления в конвейере фактическое направление условного ветвления отправляется в схему 126 модуля прогнозирования ветвлений по пути 213.

Схема 205 логики прогнозирования и обновления таблицы ветвлений выполнена с возможностью использовать фактическое направление ветвления помимо адреса инструкции ветвления, состояния записи в BHT 207 и необязательно содержимого BHR 203, чтобы обновлять содержимое BHT 207. Дополнительно схема 205 логики прогнозирования и обновления таблицы ветвлений выполнена с возможностью управлять записью в BTAC 141 в зависимости от фактического направления ветвления и состояния BHT 207 либо любого другого состояния в модуле прогнозирования направлений ветвления, преимущественно предоставляя возможность записи в BTAC 141 быть чувствительной к схеме 126 модуля прогнозирования ветвлений и любому методу прогнозирования ветвлений, реализованному посредством других схем модулей прогнозирования ветвления, сохраняющих информацию состояния, используемую для прогнозирования ветвлений.

Фиг. 3 - это функциональная блок-схема первого примерного варианта осуществления схемы 300 управления BTAC. Схемой 300 управления BTAC может быть подходящая схема, включенная в схему 205 логики прогнозирования и обновления таблицы ветвлений, чтобы обновлять BTAC 141 после того, как BHT 207 обновлена. Входом в схему 300 управления BTAC является самый старший бит, после обновления в результате фактического разрешения, из значения двухбитового счетчика, соответствующего инструкции условного ветвления. Выходной сигнал 305 схемы 300 управления BTAC - это инвертированный сигнал входа. BTAC 141 интерпретирует выходной сигнал 305 для того, чтобы определить то, следует ли управлять записью, соответствующей инструкции условного ветвления, как описано ниже.

Например, если обновленный двухбитовый счетчик, соответствующий инструкции условного ветвления, имеет значение 00 (строгое прогнозирование "не осуществлено"), запись для этой инструкции условного ветвления в BTAC 141 должна управляться согласно различным альтернативам, описанным ниже. Аналогично, если обновленный двухбитовый счетчик имеет значение 01 (нестрогое прогнозирование "не осуществлено"), запись для этой инструкции условного ветвления в BTAC 141 должна управляться. Если обновленный двухбитовый счетчик имеет значение 10 (нестрогое прогнозирование "осуществлено") или значение 11 (строгое прогнозирование "осуществлено"), запись BTAC 141 не должна модифицироваться.

Фиг. 4 - это функциональная блок-схема второго примерного варианта осуществления схемы 400 сигналов управления BTAC. Схемой 400 управления BTAC может быть подходящая схема для секции управления BTAC схемы 205 логики прогнозирования и обновления таблицы ветвлений, чтобы управлять BTAC 141 до того, как BHT 207 обновлена. Схема 400 управления BTAC - это логическая схема, включающая в себя И-вентили 405A-405B и ИЛИ-вентиль 415, используемые для того, чтобы формировать сигнал 425 управления, чтобы управлять записью, соответствующей инструкции условного ветвления, которая фактически разрешена. Схема 400 управления BTAC работает в ответ на фактическое направление ветвления и текущее состояние BHT 207 до обновления, возникающего в результате фактического направления. Схема 400 управления BTAC имеет входы A' (фактическое направление ветвления инвертировано), B' (самый старший бит двухбитового счетчика инвертирован) и C' (самый младший бит двухбитового счетчика инвертирован). В этом варианте осуществления BTAC 141 должен интерпретировать выходной сигнал 425, чтобы управлять записью, соответствующей инструкции условного ветвления, как описано ниже. Хотя схемы 300 и 400 управления BTAC описаны как зависимые от реализации BHT 207, они также могут зависеть от выбранной реализации BHR. Более того, следует принимать во внимание, что данное раскрытие допускает другие схемы управления BTAC, которые администрируются посредством различной реализации BHT или реализуются с помощью различных прогнозных реализаций ветвления. Более того, схемы управления BTAC, показанные на фиг. 3 и 4, могут быть интегрированными в схему 205 логики прогнозирования и обновления таблицы ветвлений или отдельными от нее.

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

BTAC 141 использует политику замены "дольше всех не использовался", где записи организуются в порядке, который указывает порядок замены записей в BTAC 141. Известная псевдосхема "дольше всех не использовался" может быть подходящей для того, чтобы сохранять порядок замены записей. По сути выходной сигнал схемы 300 управления BTAC может приводить к модификации позиции записи, соответствующей инструкции условного ветвления, в BTAC 141. Например, запись может быть поднята в порядке замены или опущена в порядке замены. Альтернативно запись может быть сохранена посредством корректировки позиции в BTAC 141 так, чтобы указать то, что она последняя по времени использования, чтобы увеличить срок ее хранения в BTAC 141.

Альтернативно в другом варианте осуществления BTAC 141 может использовать политику модифицированного циклического алгоритма. В традиционной политике регистр указывает на запись, которая должна быть заменена в следующий раз, когда условное ветвление добавляется, и последовательно переходит к следующей последовательной записи после того, как запись заменена, проходя в цикле через записи справедливым способом. Однако в политике модифицированного циклического алгоритма, указатель используется для того, чтобы указывать на запись, соответствующую инструкции условного ветвления, которая фактически разрешена. Например, запись, соответствующая инструкции условного ветвления, может быть маркирована для удаления посредством корректировки указателя так, чтобы теперь указывать на эту запись. При этом данная запись заменяется в следующий раз, когда инструкция условного ветвления и ее соответствующий адрес результата выполнения добавляются в BTAC 141. Соответственно, следующей записью, которая должна быть удалена, будет запись, для которой недавно определено, что она должна быть удалена. Хотя политики замены, используемые посредством BTAC 141, предусмотренного в данном документе, являются примерными, заявленные способы также применимы к другим политикам замены, обычно используемым в BTAC.

Фиг. 5 - это блок-схема 500 последовательности операций, иллюстрирующая способ управления BTAC. На этапе 510 принимается направление ветвления традиционной инструкции ветвления, которое фактически разрешено. Например, путь 213 по фиг. 2 иллюстрирует схему 126 модуля прогнозирования ветвлений как принимающую направление ветвления из конвейера 112. На этапе 520 в ответ на прием фактического направления ветвления оценивается состояние схемы модуля прогнозирования ветвления. На этапе 530 запись в BTAC, связанная с инструкцией условного ветвления, управляется согласно состоянию схемы модуля прогнозирования ветвлений.

Этапы 530A-530D являются альтернативными примерными вариантами осуществления различных типов управления записью в BTAC, как показано на этапе 530. Эти примерные варианты осуществления могут быть использованы по отдельности или в комбинации. На этапе 530A запись в BTAC, которая должна управляться, удаляется, преимущественно удаляя последнюю инструкцию условного ветвления, которая должна быть спрогнозирована как "не осуществлено", из BTAC. На этапе 530B запись в BTAC, которая должна управляться, поддерживается в BTAC в течение большего периода времени, преимущественно продлевая срок хранения последней инструкции условного ветвления, которая должна быть спрогнозирована как "осуществлено", в BTAC.

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

Этап 530D показывает корректировку следующего регистра замены для BTAC, использующего политику замены модифицированного циклического алгоритма. В одном варианте осуществления содержимое следующего регистра замены модифицируется таким образом, чтобы указывать на запись, которая должна управляться в BTAC. Таким образом, когда следующая инструкция условного ветвления должна быть добавлена в BTAC, указатель на запись заменяется на добавленную запись, преимущественно удаляя последнюю инструкцию условного ветвления, которая должна быть спрогнозирована как "не осуществлено", из BTAC. В другом варианте осуществления содержимое следующего регистра замены модифицируется таким образом, чтобы указывать на следующую запись в BTAC после записи, которая должна управляться. Таким образом, когда следующая инструкция условного ветвления должна быть добавлена в BTAC, следующая запись в BTAC после записи, которая должна управляться, заменяется на добавленную запись, преимущественно продлевая срок хранения управляемой записи в BTAC. Следует принимать во внимание, что другие политики управления для управления BTAC могут быть использованы согласно настоящему раскрытию.

Фиг. 6 - это блок-схема 600 последовательности операций, иллюстрирующая способ уменьшения вероятности нескольких циклов очистки конвейера. На этапе 610 неявно прогнозируется первое направление для инструкции условного ветвления. Например, если есть попадание в BTAC для инструкции условного ветвления, соответствующий адрес результата выполнения ветвления в BTAC далее предварительно вызывается. Таким образом, направление ветвления неявно прогнозируется как "осуществлено". На этапе 620 второе направление для инструкции условного ветвления далее прогнозируется на основе информации состояния, такой как информация состояния, сохраненная в схеме 126 прогнозирования ветвлений. Продолжая предыдущий пример, схема модуля прогнозирования ветвлений прогнозирует то, что инструкция условного ветвления должна быть "не осуществлено", тем самым конфликтуя с неявным прогнозом BTAC. На этапе 630 запись BTAC, связанная с инструкцией условного ветвления, управляется с помощью информации состояния, сохраненной, например, в схеме 126 прогнозирования ветвлений. Различные типы управления BTAC описаны выше в связи с пояснением фиг. 5. Альтернативно на этапе 630 запись BTAC, связанная с инструкцией условного ветвления, управляется вследствие конфликта между схемой модуля прогнозирования ветвления и поиском BTAC независимо от любого состояния, сохраненного в модуле схемы прогнозирования ветвлений.

Различные иллюстративные логические блоки, модули, схемы, элементы и/или компоненты, описанные в связи с раскрытыми в данном документе вариантами осуществления, могут быть реализованы или выполнены с помощью процессора общего назначения, процессора цифровых сигналов (DSP), специализированной интегральной схемы (ASIC), программируемой пользователем матричной БИС (FPGA) или другого программируемого логического устройства, дискретного логического элемента или транзисторной логики, дискретных компонентов аппаратных средств либо любой комбинации вышеозначенного, спроектированной так, чтобы выполнять описанные в данном документе функции. Процессором общего назначения может быть микропроцессор, но в альтернативном варианте процессором может быть любой традиционный процессор, контроллер, микроконтроллер или конечный автомат. Процессор также может быть реализован как сочетание вычислительных компонентов, к примеру, сочетание DSP и микропроцессора, множество микропроцессоров, один или более микропроцессоров вместе с ядром DSP либо любая другая подобная конфигурация.

Способы или алгоритмы, описанные в связи с раскрытыми в данном документе вариантами осуществления, могут быть реализованы непосредственно в аппаратных средствах, в программном модуле, приводимом в исполнение процессором, или в их комбинации. Программный модуль может постоянно размещаться в оперативной памяти, флэш-памяти, ПЗУ, памяти типа EPROM, памяти типа EEPROM, регистрах, на жестком диске, сменном диске, компакт-диске или любой другой форме носителя хранения данных, известной в данной области техники. Носитель хранения данных может быть соединен с процессором, так чтобы процессор мог считывать информацию и записывать информацию на носитель хранения данных. В альтернативном варианте носитель хранения может быть встроен в процессор.

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

Похожие патенты RU2421783C2

название год авторы номер документа
СПОСОБЫ И УСТРОЙСТВА ДЛЯ СОКРАЩЕНИЯ ПОИСКОВ В КЭШЕ ЦЕЛЕВЫХ АДРЕСОВ ВЕТВЛЕНИЙ 2007
  • Морроу Майк
RU2419835C2
КЭШИРОВАНИЕ ЦЕЛЕВОГО АДРЕСА ПЕРЕХОДА С УПРЕЖДАЮЩЕЙ ВЫБОРКОЙ 2006
  • Смит Родни Уэйн
  • Стемпел Брайн Майкл
  • Диффендерфер Джеймс Норрис
  • Бриджес Джеффри Тодд
  • Сарториус Томас Эндрю
RU2358310C1
ОТСРОЧКА ОБНОВЛЕНИЙ СОСТОЯНИЙ КЭША В НЕСПЕКУЛЯТИВНОЙ КЭШ-ПАМЯТИ В ПРОЦЕССОРНОЙ СИСТЕМЕ В ОТВЕТ НА СПЕКУЛЯТИВНЫЙ ЗАПРОС ДАННЫХ ДО ТЕХ ПОР, ПОКА СПЕКУЛЯТИВНЫЙ ЗАПРОС ДАННЫХ НЕ СТАНЕТ НЕСПЕКУЛЯТИВНЫМ 2020
  • Котинти Нареш, Вигнян Редди
  • Пераис, Артур
  • Аль Шейх, Рами Мохаммад
  • Приядарши, Шивам
RU2817624C1
ОБРАБОТКА ОШИБОК ПРЕДВАРИТЕЛЬНОГО ДЕКОДИРОВАНИЯ ЧЕРЕЗ КОРРЕКЦИЮ ВЕТВЛЕНИЙ 2005
  • Смит Родни Уэйн
  • Стемпел Брайн Майкл
  • Диффендерфер Джеймс Норрис
  • Бриджес Джеффри Тодд
  • Сарториус Томас Эндрю
RU2367004C2
СПОСОБ И УСТРОЙСТВО ДЛЯ ВЫПОЛНЕНИЯ ИНСТРУКЦИЙ ПРОЦЕССОРА НА ОСНОВЕ ДИНАМИЧЕСКИ ИЗМЕНЯЕМОЙ ЗАДЕРЖКИ 2007
  • Мичалак Джералд Пол
  • Доксер Кеннет Алан
RU2419836C2
ПРЕДСТАВЛЕНИЕ ПЕРЕХОДОВ ЦИКЛА В РЕГИСТРЕ ПРЕДЫСТОРИИ ПЕРЕХОДОВ С ПОМОЩЬЮ МНОЖЕСТВА БИТ 2007
  • Диффендерфер Джеймс Норрис
  • Рихлик Богуслав
RU2447486C2
ВЫБОРКА КОМАНД ПО УКАЗАНИЮ В СРЕДСТВЕ СБОРА СВЕДЕНИЙ О ХОДЕ ВЫЧИСЛЕНИЙ 2013
  • Гейни Джр Чарлз У.
  • Митран Марсель
  • Шум Чунлун Кевин
  • Студли Кевин А.
RU2585982C2
СБОР СВЕДЕНИЙ О ХОДЕ ВЫЧИСЛЕНИЙ 2013
  • Фаррелл Марк С.
  • Гейни Джр. Чарлз У.
  • Митран Марсель М.
  • Шум Чунлун Кевин
  • Смит Брайан Леонард
RU2585968C2
УПРАВЛЕНИЕ В РЕЖИМЕ НИЗКИХ ПРИВИЛЕГИЙ РАБОТОЙ СРЕДСТВА СБОРА СВЕДЕНИЙ О ХОДЕ ВЫЧИСЛЕНИЙ 2013
  • Фаррелл Марк С.
  • Гейни Джр. Чарлз У.
  • Митран Марсель
  • Шум Чунлун Кевин
  • Следжел Тимоти Дж.
  • Смит Брайан Леонард
  • Студли Кевин А.
RU2585969C2
ИНСТРУКЦИЯ И ЛОГИКА ДЛЯ ДОСТУПА К ПАМЯТИ В КЛАСТЕРНОЙ МАШИНЕ ШИРОКОГО ИСПОЛНЕНИЯ 2013
  • Лешенко Антон У.
  • Ефимов Андрей
  • Шишлов Сергей И.
  • Иер Джайеш
  • Бабаян Борис А.
RU2662394C2

Иллюстрации к изобретению RU 2 421 783 C2

Реферат патента 2011 года СПОСОБЫ И УСТРОЙСТВА ДЛЯ ПРОАКТИВНОГО УПРАВЛЕНИЯ КЭШЕМ АДРЕСОВ ВЕТВЛЕНИЙ

Изобретение относится к области процессоров, более конкретно к способу улучшения прогнозирования ветвлений посредством проактивного управления содержимым КЭШа адресов ветвлений. Техническим результатом является увеличение быстродействия за счет уменьшения вероятности возникновения проблемы нескольких циклов очистки. Способ включает: определение в первой стадии системы прогнозирования ветвлений, что запись ВТАС соответствует инструкции условного ветвления; определение в первой стадии направления ветвления на основании упомянутой записи в ВТАС; определение во второй стадии системы прогнозирования ветвлений, что запись соответствует упомянутой инструкции условного ветвления; модификацию информации состояния, соответствующей упомянутой записи, соответствующей упомянутой инструкции условного ветвления, после вызова инструкции условного ветвления и перед разрешением инструкции условного ветвления; и управление записью в ВТАС на основании модифицированной информации состояния. 6 н. и 37 з.п. ф-лы, 6 ил.

Формула изобретения RU 2 421 783 C2

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

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

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

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

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

6. Система по п.1, дополнительно содержащая указатель замены, при этом ВТАС использует политику замены модифицированного циклического алгоритма и при этом логическая схема дополнительно выполнена с возможностью модифицировать указатель замены так, чтобы указывать на запись ВТАС.

7. Система по п.1, в которой ВТАС, первая стадия и вторая стадия размещены в процессоре.

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

9. Система по п.1, в которой записью ВТАС управляют перед разрешением инструкции ветвления.

10. Система по п.9, в которой результат первого прогнозирования первой стадии, соответствующий инструкции ветвления, используют для вызова следующей инструкции из КЭШа инструкций в конвейер, при этом результат второго прогнозирования второй стадии, соответствующий упомянутой инструкции ветвления, вызывает извлечение следующей инструкции из конвейера, когда результат второго прогнозирования не соответствует результату первого прогнозирования.

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

12. Способ по п.11, в котором управление записью в ВТАС содержит этап, на котором удаляют запись ВТАС из ВТАС на основании модифицированной информации состояния второй стадии системы прогнозирования ветвлений.

13. Способ по п.11, в котором управление записью в ВТАС содержит этап, на котором поддерживают запись ВТАС в течение большего периода времени на основании модифицированной информации состояния второй стадии системы прогнозирования ветвлений.

14. Способ по п.11, дополнительно содержащий этап, на котором
поддерживают записи сохраненными в ВТАС в порядке замены, при этом управление записью в ВТАС дополнительно содержит этап, на котором модифицируют позицию записи ВТАС в ВТАС в порядке замены на основании модифицированной информации состояния второй стадии системы прогнозирования ветвлений.

15. Способ по п.14, в котором модификация позиции записи в ВТАС дополнительно содержит этап, на котором модифицируют указатель замены так, чтобы указывать на запись в ВТАС.

16. Способ по п.11, в котором вторая стадия включает в себя таблицу истории ветвлений.

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

18. Способ по п.17, в котором управление записью ВТАС дополнительно содержит удаление записи ВТАС из ВТАС на основании состояния второй стадии системы многостадийного прогнозирования ветвлений.

19. Способ по п.17, в котором управление записью ВТАС дополнительно содержит поддержание записи ВТАС в ВТАС в течение большего периода времени на основании состояния второй стадии системы многостадийного прогнозирования ветвлений.

20. Способ по п.17, дополнительно содержащий этап, на котором
поддерживают одну или более записей сохраненными в ВТАС в порядке замены, при этом управление записью в ВТАС дополнительно содержит модификацию позиции записи в ВТАС в порядке замены на основании состояния второй стадии системы многостадийного прогнозирования ветвлений.

21. Способ по п.20, в котором модификация позиции записи в ВТАС дополнительно содержит модификацию указателя замены так, чтобы указывать на запись ВТАС.

22. Способ по п.17, в котором вторая стадия включает в себя таблицу истории ветвлений, при этом управление записью в ВТАС дополнительно содержит управление записью ВТАС на основании разрешения инструкции условного ветвления.

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

24. Система по п.23, в которой вторая стадия выполнена с возможностью управлять записью ВТАС, когда первое прогнозируемое направление не осуществлено, путем удаления записи ВТАС из ВТАС на основании модифицированной информации состояния второй стадии.

25. Система по п.23, в которой вторая стадия выполнена с возможностью управлять записью ВТАС, когда первое прогнозируемое направление осуществлено, путем поддержания записи ВТАС в ВТАС в течение большего периода времени на основании модифицированной информации состояния второй стадии.

26. Система по п.23, в которой вторая стадия выполнена с возможностью управлять записью ВТАС путем модификации позиции записи ВТАС в порядке замены записей ВТАС на основании модифицированной информации состояния второй стадии.

27. Система по п.26, в которой модификация позиции записи ВТАС в порядке замены записей ВТАС содержит размещение записи ВТАС на более высокой позиции по сравнению с текущей позицией упомянутой записи ВТАС.

28. Система по п.23, дополнительно содержащая указатель замены, причем ВТАС использует политику замены модифицированного циклического алгоритма, при этом вторая стадия дополнительно выполнена с возможностью модификации указателя замены так, чтобы указывать на запись ВТАС.

29. Система по п.23, в которой первая стадия и вторая стадия размещены в процессоре.

30. Система по п.23, в которой модифицированную информацию состояния второй стадии системы многостадийного прогнозирования ветвлений определяют по меньшей мере частично на основании направления ветвления, осуществляемого инструкцией условного ветвления.

31. Система по п.23, в которой вторая стадия включает в себя таблицу истории ветвлений (ВНТ).

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

33. Способ управления КЭШем адресов ветвлений (ВТАС), содержащий этапы, на которых
сохраняют в первой стадии системы прогнозирования ветвлений запись ВТАС, связанную с первым прогнозированием ветвления инструкции условного ветвления;
определяют во второй стадии системы прогнозирования ветвлений направление ветвления, осуществляемое инструкцией условного ветвления на основании информации состояния, соответствующей инструкции условного ветвления;
модифицируют во второй стадии информацию состояния после вызова инструкции условного ветвления и перед разрешением инструкции условного ветвления; и
управляют записью ВТАС на основании модифицированной информации состояния.

34. Способ по п.33, в котором управление записью ВТАС содержит этап, на котором удаляют запись ВТАС из ВТАС на основании модифицированной информации состояния второй стадии системы прогнозирования ветвлений.

35. Способ по п.33, в котором управление записью ВТАС содержит этап, на котором поддерживают запись ВТАС в течение большего периода времени на основании модифицированной информации состояния второй стадии системы прогнозирования ветвлений.

36. Способ по п.33, дополнительно содержащий этап, на котором модифицируют позицию записи ВТАС в порядке замены записей ВТАС, причем позицию записи ВТАС модифицируют на основании модифицированной информации состояния второй стадии системы прогнозирования ветвлений.

37. Способ по п.33, в котором модификация записи ВТАС дополнительно содержит этап, на котором модифицируют указатель замены так, чтобы указывать на запись ВТАС.

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

39. Способ по п.38, в котором управление записью ВТАС дополнительно содержит этап, на котором удаляют запись ВТАС из ВТАС на основании модифицированной информации состояния второй стадии системы многостадийного прогнозирования ветвлений.

40. Способ по п.38, в котором управление записью ВТАС дополнительно содержит этап, на котором поддерживают запись ВТАС в течение большего периода времени на основании модифицированной информации состояния второй стадии системы многостадийного прогнозирования ветвлений.

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

42. Способ по п.41, в котором модификация позиции записи ВТАС дополнительно содержит этап, на котором модифицируют указатель замены так, чтобы указывать на запись ВТАС.

43. Способ по п.38, в котором информацию состояния второй стадии системы многостадийного прогнозирования ветвлений определяют на основании разрешения инструкции условного ветвления.

Документы, цитированные в отчете о поиске Патент 2011 года RU2421783C2

СПОСОБ И УСТРОЙСТВО ДЛЯ БЛОКИРОВКИ СИГНАЛА СИНХРОНИЗАЦИИ В МНОГОПОТОЧНОМ ПРОЦЕССОРЕ 2000
  • Роджерс Дион
  • Толл Брет
  • Вуд Эми
RU2233470C2
Способ приготовления мыла 1923
  • Петров Г.С.
  • Таланцев З.М.
SU2004A1
Топчак-трактор для канатной вспашки 1923
  • Берман С.Л.
SU2002A1
Способ и приспособление для нагревания хлебопекарных камер 1923
  • Иссерлис И.Л.
SU2003A1
Способ и приспособление для нагревания хлебопекарных камер 1923
  • Иссерлис И.Л.
SU2003A1
Способ и приспособление для нагревания хлебопекарных камер 1923
  • Иссерлис И.Л.
SU2003A1

RU 2 421 783 C2

Авторы

Рихлик Богуслав

Даты

2011-06-20Публикация

2007-06-28Подача