ЭНЕРГОЭФФЕКТИВНЫЙ МЕХАНИЗМ УПРЕЖДАЮЩЕЙ ВЫБОРКИ ИНСТРУКЦИЙ

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

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

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

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

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

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

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

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

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

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

11 - Сильно предсказанный как «совершенный»

10 - Слабо предсказанный как «совершенный»

01 - Слабо предсказанный как «несовершенный»

00 - Сильно предсказанный как «несовершенный»

Значение счетчика увеличивается каждый раз, когда соответствующая инструкция перехода оценивается как «совершенная», и уменьшается каждый раз, когда инструкция перехода оценивается как «несовершенная». Это увеличение/уменьшение «насыщается», поскольку увеличение останавливается при 0b11, и уменьшение останавливается при 0b00. Таким образом, предсказание переходов включает в себя не только результат (совершенный или несовершенный), но также весовой коэффициент, указывающий силу или уверенность предсказания.

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

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

111 - Очень сильно предсказанный как «совершенный»

110 - Сильно предсказанный как «совершенный»

101 - Предсказанный как «совершенный»

100 - Незначительно предсказанный как «совершенный»

011 - Незначительно предсказанный как «несовершенный»

010 - Предсказанный как «несовершенный»

001 - Сильно предсказанный как «несовершенный»

000 - Очень сильно предсказанный как «несовершенный»

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

В данной области техники известно, что счетчики с насыщением могут отслеживать точность предсказаний, а также оценку перехода. Выводом счетчика с насыщением может быть взвешенное значение в виде «согласовано» или «не согласовано», и этот вывод в сочетании со статическим предсказанием может привести к взвешенному предсказанию. В общем, в данной области техники известен широкий спектр способов предсказания переходов, включая такие способы, где предсказатель используется не для предсказания перехода, а для выбора предсказаний от двух или более других независимых предсказателей. Например, документ Скотта МакФарлинга от 1993г. "Combining Branch Predictors", Digital Western Research Laboratory Technical Note TN-36, который включен в данный документ в полном объеме посредством ссылки.

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

Сущность изобретения

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

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

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

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

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

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

Фиг.2 - блок-схема алгоритма энергоэффективного способа упреждающей выборки инструкций.

Фиг.3 - блок-схема алгоритма энергоэффективного способа управления кэшем.

Осуществление изобретения

Фиг.1 представляет собой функциональную структурную схему процессора 10. Процессор 10 выполняет инструкции в конвейере 12 выполнения инструкций согласно управляющей логике 14. В некоторых вариантах осуществления конвейер 12 может быть суперскалярной архитектуры с несколькими параллельными конвейерами. Конвейер 12 включает в себя различные регистры или защелки 16, устроенные на ступенях конвейера, и одно или более арифметико-логических устройств (АЛУ) 18. Регистр Общего Назначения (РОН) 20 предоставляет регистры, образующие вершину иерархии памяти.

Конвейер 12 выполняет выборку инструкций из кэша инструкций (I-кэша) 22, при этом управление трансляцией адресов памяти и разрешениями выполняется Буфером Трансляций Адресов для Инструкций (Instruction-side Translation Lookaside Buffer, ITLB) 24. Когда инструкции условного перехода декодируются на ранней стадии в конвейере 12, механизм 23 предсказания переходов предсказывает поведение перехода и предоставляет предсказание в узел 25 упреждающей выборки инструкций. Узел 25 упреждающей выборки инструкций спекулятивно выбирает инструкции из кэша 22 инструкций из целевого адреса перехода, вычисленного в конвейере 12 для предсказаний перехода типа «совершенный», или из непосредственно следующего адреса для переходов, предсказанных как «несовершенные». В любом случае инструкции, выбранные с упреждением, загружаются в конвейер 12 для спекулятивного выполнения.

Данные вызываются из кэша данных (D-кэша) 26, при этом трансляцией адресов памяти и разрешениями управляет главный Буфер Трансляции Адресов (Translation Lookaside Buffer, TLB) 28. В различных вариантах осуществления ITLB может содержать копию части TLB. Альтернативно, ITLB и TLB могут быть интегрированы. Аналогично, в различных вариантах осуществления процессор 10, I-кэш 22 и D-кэш 26 могут быть интегрированы или объединены. Неуспешные обращения в I-кэш 22 и/или D-кэш 26 приводят к выполнению доступа к основной (находящейся вне кристалла) памяти 32 под управлением интерфейса 30 памяти.

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

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

Эта разность в точности между сильно и слабо взвешенными предсказаниями переходов может быть использована, чтобы сберегать энергию в конвейерных процессорах 10 путем выполнения упреждающей выборки инструкций только для сильно предсказанных инструкций перехода. Пример способа предсказания переходов описан со ссылкой на Фиг.2. Инструкция условного перехода обнаруживается в конвейере 12 (блок 40). Это обычно происходит на этапе декодирования в конвейере, но в некоторых вариантах осуществления инструкции могут быть предварительно декодированы до их загрузки в I-кэш 22, и управляющая логика 14 конвейера может распознать инструкцию условного перехода сразу при выборке этой инструкции. Как только определяется, что инструкция является инструкцией условного перехода, ее оценка (например, «совершенный» или «несовершенный») предсказывается (блок 42), и предсказание имеет взвешенное значение. Это взвешенное предсказание предоставляется, например, посредством механизма 23 предсказания переходов. Вес предсказания перехода оценивается (блок 44), и в случае сильно взвешенного предсказания выполняется упреждающая выборка инструкций из I-кэша 22, и они спекулятивно выполняются в конвейере 12 (блок 46). В случае слабо взвешенных предсказаний, узел 25 упреждающей выборки инструкций не выполняет упреждающей выборки каких-либо инструкций (блок 48). Вместо этого узел 25 упреждающей выборки останавливает упреждающую выборку до тех пор, пока соответствующая инструкция условного перехода не оценивается в конвейере 12, и ее фактическое поведение перехода не становится известным. С этой точки выборка инструкций продолжается с известного правильного следующего адреса. По существу, эта методология трансформирует бимодальное предсказание перехода по предшествующему уровню техники (например, «совершенный» или «несовершенный») путем добавления к предсказанию третьего состояния или указателя: предсказать переход как «совершенный» и выполнить упреждающую выборку, предсказать переход как «несовершенный» и выполнить упреждающую выборку или ожидать фактической оценки условия перехода. Путем невыполнения упреждающей выборки инструкций из целевого адреса слабо предсказанного перехода процессор 10 не растрачивает энергию, необходимую для упреждающей выборки и запуска их спекулятивного выполнения, когда существует высокая вероятность (относительно сильно предсказанных выводов переходов), что предсказание будет ошибочным и возникнет необходимость сброса выбранных с упреждением инструкций.

В случае сильно предсказанных переходов методология настоящего изобретения не имеет какого-либо влияния на производительность процессора: происходит упреждающая выборка и точность перехода будет воздействовать на производительность, как хорошо известно в данной области техники. В случае слабо предсказанных переходов, где упреждающая выборка останавливается, влияние на производительность процессора зависит от точности предсказания и от того, находится ли соответствующий потенциальный следующий адрес (то есть целевой адрес перехода или непосредственно следующий адрес) в I-кэше 22. Влияние на производительность приведено в Таблице 1.

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

Однако, если слабо взвешенное предсказание перехода является ошибочным, то методология настоящего изобретения не только сберегает энергию, но и может повысить производительность процессора. Если предсказанный адрес находится в I-кэше 22, то процессор 10 подвергается такому же останову, что и в случае точного слабо взвешенного предсказания перехода. Однако, контроллеру 14 не требуется сбрасывать конвейер 12 и вовлекаться в другие операции восстановления неправильного предсказания. В тех случаях, когда неправильно предсказанный переход требует исключения для восстановления, остановка упреждающей выборки инструкций представляет значительное улучшение в производительности процессора по сравнению с выполнением упреждающей выборки.

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

В одном варианте осуществления настоящего изобретения упреждающая выборка инструкций полностью не останавливается под действием слабо взвешенных предсказаний переходов. Вместо этого она останавливается только, если упреждающая выборка приводит к неуспешному обращению в I-кэш 22, как описано со ссылкой на Фиг.3. Как описано выше, инструкция условного перехода обнаруживается (блок 40), и ее оценка предсказывается (блок 42). Если предсказание является сильно взвешенным, то выполняется упреждающая выборка инструкций из предсказанного следующего адреса (блок 46). Если предсказание является слабо взвешенным, то узел 25 упреждающей выборки инструкций выполняет доступ в I-кэш 22, чтобы определить, находится ли в нем предсказанный следующий адрес (блок 50). Если предсказанный адрес находится в I-кэше 22, то упреждающая выборка продолжается (блок 52). Если операция упреждающей выборки приводит к неуспешному обращению в I-кэш 22, то операция упреждающей выборки завершается, и упреждающая выборка останавливается до тех пор, пока условие перехода не будет оценено в конвейере 12 (блок 54). В этом варианте осуществления останов в случае точного слабо взвешенного предсказания перехода исключается, между тем предохраняя от значительной деградации производительности, вызываемой замещением строки кэша для ошибочного слабо взвешенного предсказания перехода.

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

В тех случаях, когда сбережения энергии менее критичны и/или более важна производительность, более гибкий подход может включать в себя применение значений счетчика, которые близки, также как и равны, уровню насыщения в определении сильно взвешенного. В одном примере, который не является ограничивающим, верхние и нижние 25% значений счетчика могут рассматриваться как сильно взвешенные, а средние 50% - как слабо взвешенные. Для бинарных счетчиков подход аппаратного обеспечения этого распределения заключается в том, что если два самых старших бита находятся в соответствии, то значение предсказания взвешивается сильно. Альтернативно, верхняя и нижняя трети могут рассматриваться как сильно взвешенные, а средняя треть - как слабо взвешенная. Специалистам в данной области техники будет очевидно, что разница между сильно и слабо взвешенными предсказаниями может быть определена различными путями в соответствии с конкретным приложением.

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

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