Блок предсказания ветвлений это

Архитектура x86

Архитектура x86 — Предсказание ветвлений

Содержание материала

Предварительное ( опережающее ) декодирование
и кэширование

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

На самом деле , алгоритмы , по которым работает блок предсказания ветвлений , вовсе не являются шедеврами искусственного интеллекта . Преимущественно они просты . и тупы . Ибо чаще всего команда условного перехода встречается в циклах : некий счётчик принимает значение X, и после каждого прохождения цикла значение счётчика уменьшается на единицу . Соответственно , до тех пор , пока значение счётчика больше нуля — осуществляется переход на начало цикла , а после того , как он становится равным нулю — исполнение продолжается дальше . Блок предсказания ветвлений просто анализирует результат выполнения команды условного перехода , и считает , что если N раз подряд результатом стал переход на определённый адрес — то и в N+1 случае будет осуществлён переход туда же . Однако , несмотря на весь примитивизм , данная схема работает просто замечательно : например , в случае , если счётчик принимает значение 100, а «порог срабатывания» предсказателя ветвлений (N) равен двум переходам подряд на один и тот же адрес — легко заметить , что 97 переходов из 98 будут предсказаны правильно !

Разумеется , несмотря на достаточно высокую эффективность простых алгоритмов , механизмы предсказания ветвлений в современных CPU всё равно постоянно совершенствуются и усложняются — но тут уже речь идёт о борьбе за единицы процентов : например , за то , чтобы повысить эффективность работы блока предсказания ветвлений с 95 процентов до 97, или даже с 97% до 99.

Блок предвыборки данных (Prefetch) очень похож по принципу своего действия на блок предсказания ветвлений — с той только разницей , что в данном случае речь идёт не о коде , а о данных . Общий принцип действия такой же : если встроенная схема анализа доступа к данным в ОЗУ решает , что к некоему участку памяти , ещё не загруженному в кэш , скоро будет осуществлён доступ — она даёт команду на загрузку данного участка памяти в кэш ещё до того , как он понадобится исполняемой программе . «Умно» ( результативно ) работающий блок предвыборки позволяет существенно сократить время доступа к нужным данным , и , соответственно , повысить скорость исполнения программы . К слову : грамотный Prefetch очень хорошо компенсирует высокую латентность подсистемы памяти , подгружая нужные данные в кэш , и тем самым , нивелируя задержки при доступе к ним , если бы они находились не в кэше , а в основном ОЗУ .

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

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

Я — тот кролик , который не может начать жевать траву до тех пор , пока
не поймёт во всех деталях , как происходит процесс фотосинтеза !
( изложение личной позиции одним из близких знакомых автора )

Вполне возможно , те чувства , которые у вас возникли после прочтения данной статьи , можно описать примерно следующим образом : «Вместо того чтобы на пальцах объяснить , какой процессор лучше — взяли и загрузили мне мозги кучей специфической информации , в которой ещё разбираться и разбираться , и конца — края не видно ! » Вполне нормальная реакция : поверьте , мы вас хорошо понимаем . Скажем даже больше ( и пусть с головы упадёт корона !): если вы думаете , что мы сами можем ответить на этот простецкий вопрос ( «какой процессор лучше ? » ) — то вы очень сильно заблуждаетесь . Не можем . Для одних задач лучше один , для других — другой , а тут ещё цена разная , доступность , симпатии конкретного пользователя к определённым маркам . Не имеет задача однозначного решения . Если бы имела — наверняка кто — то бы его нашёл , и стал бы самым знаменитым обозревателем за всю историю независимых тестовых лабораторий .

Хотелось бы подчеркнуть ещё раз : даже полностью усвоив и осмыслив всю информацию , изложенную в данном материале — вы по — прежнему не сможете предсказать , какой из двух процессоров будет быстрее в ваших задачах , глядя только на их характеристики . Во — первых — потому , что далеко не все характеристики процессоров здесь рассмотрены . Во — вторых — потому , что есть и такие параметры CPU, которые в числовом виде могут быть представлены только с очень большой «натяжкой» . Так для кого же ( и для чего ) всё это написано ? В основном — для тех самых «кроликов» , которые непременно желают знать , что происходит внутри тех устройств , которыми они пользуются ежедневно . Зачем ? Может , они просто лучше себя чувствуют , когда знают , что вокруг них происходит ? 🙂

Добавить комментарий

Не использовать не нормативную лексику.

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

ВСЕ КОММЕНТАРИИ МОДЕРИРУЮТСЯ ВРУЧНУЮ, ТАК ЧТО СПАМИТЬ БЕСПОЛЕЗНО!

Источник

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

Модуль предсказания условных переходов (англ. Branch Prediction Unit ) — устройство, входящее в состав микропроцессоров, имеющих конвейерную архитектуру, определяющее направление ветвлений (предсказывающее, будет ли выполнен условный переход, или нет) в исполняемой программе. Предсказание ветвлений позволяет осуществлять предварительную выборку инструкций и данных из памяти, а также выполнять инструкции, находящиеся после условного перехода, до того, как будет определено его направление. Предсказатель переходов является неотъемлемой частью всех современных суперскалярных микропроцессоров, так как в большинстве случаев (точность предсказания переходов в современных процессорах превышает 90 %) позволяет оптимально использовать вычислительные ресурсы процессора. [1]

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

Статическое предсказание

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

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

Динамическое предсказание

Динамические методы, широко используемые в современных процессорах, подразумевают анализ истории ветвлений. Примером динамического предсказания может служить двухуровневый адаптивный исторический алгоритм (англ. Bimodal branch prediction ), использовавшийся процессорами архитектуры P6 (анализируется таблица истории переходов, содержащая младшие значимые биты адреса инструкции и соответствующую им вероятность условного перехода: «скорее всего, будет выполнен», «возможно, будет выполнен», «возможно, не будет выполнен», «скорее всего, не будет выполнен» и обновляемая после каждого перехода).

Примечания

Wikimedia Foundation . 2010 .

Смотреть что такое «Предсказание ветвлений» в других словарях:

Предсказатель переходов — Модуль предсказания условных переходов (англ. Branch Prediction Unit) устройство, входящее в состав микропроцессоров, имеющих конвейерную архитектуру, определяющее направление ветвлений (предсказывающее, будет ли выполнен условный… … Википедия

NetBurst — (рабочее название P68) суперскалярная гиперконвейерная микроархитектура, разработанная компанией Intel и лежавшая в основе микропроцессоров Pentium 4, Pentium D, Celeron и Xeon. Содержание 1 История 2 … Википедия

Intel P6 — P6 суперскалярная суперконвейерная архитектура, разработанная компанией Intel и лежащая в основе микропроцессоров Pentium Pro, Pentium II, Pentium III, Celeron и Xeon. В отличие от x86 совместимых процессоров предыдущих поколений с CISC… … Википедия

Pentium III — > Центральный процессор Производство … Википедия

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

X86 — 80486 DX2 x86 (Intel 80×86) аппаратная платформа: архитектура микропроцессора и соответствующий набор инструкций, как разработанных и выпускаемых компанией Intel, так и совместимых с ними процессоров других производителей (AMD, VIA … Википедия

IDT WinChip — Центральный процессор Производство: с 1997 по 1999 год Производитель: IDT … Википедия

WinChip — IDT WinChip Центральный процессор Производство: с 1997 по 1999 год … Википедия

x86 — 80486 DX2 x86 (англ. Intel 80×86) архитектура процессора c одноимённым наборо … Википедия

EPIC (архитектура микропроцессора) — У этого термина существуют и другие значения, см. EPIC. EPIC (англ. explicitly parallel instruction computing) микропроцессорная архитектура с явным параллелизмом команд. Термин введён в 1997 году альянсом HP и Intel[1] для… … Википедия

Источник

Предиктор ветвления — Branch predictor

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

Двустороннее ветвление обычно реализуется с помощью инструкции условного перехода . Условный переход может быть либо «не выполнен» и продолжить выполнение с первой ветвью кода, которая следует сразу после условного перехода, либо он может быть «взят» и перейти в другое место в программной памяти, где находится вторая ветвь кода. хранится. Точно неизвестно, будет ли выполнен условный переход или нет, пока условие не будет вычислено и условный переход не пройдет стадию выполнения в конвейере команд (см. Рис. 1).

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

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

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

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

СОДЕРЖАНИЕ

Выполнение

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

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

Ранние реализации SPARC и MIPS (две из первых коммерческих архитектур RISC ) использовали однонаправленное статическое предсказание ветвления: они всегда предсказывают, что условный переход не будет выполнен, поэтому они всегда выбирают следующую последовательную инструкцию. Указатель инструкции устанавливается на непоследовательный адрес только тогда, когда оценивается переход или переход.

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

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

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

Статическое предсказание используется в качестве метода отката в некоторых процессорах с динамическим предсказанием ветвления, когда у динамических предсказателей нет достаточной информации для использования. И Motorola MPC7450 (G4e), и Intel Pentium 4 используют эту технику как запасной вариант .

При статическом прогнозировании все решения принимаются во время компиляции перед выполнением программы.

Динамическое предсказание ветвления

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

Предсказание случайного ветвления

Использование случайного или псевдослучайного бита (чистое предположение) гарантировало бы для каждой ветви 50% правильного прогноза, который не может быть улучшен (или ухудшен) переупорядочиванием инструкций. (С помощью простейшего статического предсказания типа «предположить дубль» компиляторы могут переупорядочить инструкции, чтобы добиться более точного предсказания, чем 50%.) Кроме того, это сделало бы время [гораздо более] недетерминированным.

Предсказание следующей строки

Некоторые суперскалярные процессоры (MIPS R8000 , Alpha 21264 и Alpha 21464 ( EV8 )) получают каждую строку инструкций с указателем на следующую строку. Этот предсказатель следующей строки обрабатывает предсказание цели ветвления, а также предсказание направления ветвления.

Когда предсказатель следующей строки указывает на выровненные группы из 2, 4 или 8 инструкций, целью ветвления обычно не будет первая извлеченная команда, и поэтому исходные извлеченные команды теряются. Предположим для простоты, что при равномерном распределении целевых объектов ветвления отбрасываются команды 0,5, 1,5 и 3,5 соответственно.

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

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

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

Счетчик насыщения

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

2-битный счетчик насыщения — это конечный автомат с четырьмя состояниями:

• Сильно не принято
• Слабо не берется
• Слабо взят
• Сильно взят

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

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

В тестах SPEC ’89 очень большие бимодальные предикторы насыщаются на 93,5% правильных, когда каждая ветвь отображается на уникальный счетчик.

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

Двухуровневый предсказатель

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

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

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

Рассмотрим пример n = 2. Это означает, что два последних вхождения ветви хранятся в двухбитовом регистре сдвига . Этот регистр истории переходов может иметь четыре различных двоичных значения: 00, 01, 10 и 11, где ноль означает «не принят», а один означает «принято». Таблица истории паттернов содержит четыре записи на каждую ветвь, по одной для каждой из 2 2 = 4 возможных историй ветвей, и каждая запись в таблице содержит двухбитовый счетчик насыщения того же типа, что и на рисунке 2 для каждой ветви. Регистр истории ветвей используется для выбора того, какой из четырех счетчиков насыщения использовать. Если история 00, то используется первый счетчик; если в истории 11, то используется последний из четырех счетчиков.

Предположим, например, что условный переход выполняется каждый третий раз. Последовательность ветвления — 001001001 . В этом случае запись с номером 00 в таблице истории паттернов перейдет в состояние «сильно занято», что указывает на то, что после двух нулей следует единица. Запись с номером 01 перейдет в состояние «категорически не принимается», что означает, что после 01 идет ноль. То же самое и с записью номер 10, в то время как запись с номером 11 никогда не используется, потому что никогда не бывает двух последовательных записей.

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

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

Двухуровневый нейронный предсказатель

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

Прогноз местного отделения

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

Intel Pentium MMX , Pentium II и Pentium III имеют локальные прогностические ветви с местной историей 4-битном и краеведческой шаблон таблицы с 16 записей для каждого условного перехода.

В тестах SPEC ’89 очень большие локальные предикторы дают 97,1% правильных значений.

Прогнозирование глобального ветвления

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

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

Двухуровневый адаптивный предсказатель с глобальным общим буфером истории и таблицей истории шаблонов называется предсказателем «gshare», если он xors глобальной истории и ПК ветви, и «gselect», если он объединяет их. Глобальное предсказание ветвлений используется в процессорах AMD , а также в процессорах Intel Pentium M , Core , Core 2 и Atom на базе Silvermont .

Прогнозирование легированных ветвей

Средство предсказания переходов объединяет в себе принципы локального и глобального прогнозирования, объединяя локальные и глобальные истории переходов, возможно, с некоторыми битами из счетчика программ . Тесты показывают, что процессор VIA Nano может использовать эту технику.

Согласен с предсказателем

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

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

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

Скотт Макфарлинг предложил комбинированное предсказание ветвлений в своей статье 1993 года.

В тестах SPEC’89 такой предсказатель примерно так же хорош, как и локальный предсказатель.

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

Предиктор цикла

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

Косвенный предсказатель ветвления

Команда непрямого перехода может выбирать из более чем двух ветвей. Некоторые процессоры имеют специализированные косвенные предикторы ветвлений. Новые процессоры Intel и AMD могут предсказывать непрямые переходы с помощью двухуровневого адаптивного предсказателя. Этот вид инструкций вносит более одного бита в буфер истории. Процессоры zEC12 и более поздние версии z / Architecture от IBM поддерживают инструкцию BRANCH PREDICTION PRELOAD, которая может предварительно загрузить запись предиктора ветвления для данной инструкции с целевым адресом ветвления, созданным путем добавления содержимого регистра общего назначения к значению немедленного смещения.

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

Прогнозирование возврата функции

Функция , как правило , вернуться туда , где он вызывается. Команда возврата — это косвенный переход, который считывает свой целевой адрес из стека вызовов . Многие микропроцессоры имеют отдельный механизм прогнозирования для команд возврата. Этот механизм основан на так называемом буфере стека возврата , который является локальным зеркалом стека вызовов. Размер буфера стека возврата обычно составляет 4–16 записей.

Прогнозирование переходов с приоритетом

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

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

Intel Core i7 имеет две целевые ветви буферов и , возможно , два или более предсказатель переходов.

Прогнозирование нейронных ветвей

Машинное обучение для предсказания ветвей с использованием LVQ и многослойных перцептронов , называемое « предсказанием нейронных ветвей», было предложено Лучианом Винтаном ( Университет Лучиана Блага в Сибиу ). Год спустя он разработал предсказатель ветвления персептрона. Даниэль Хименес значительно развил исследования в области прогнозирования нейронных ветвей. В 2001 году был представлен первый предсказатель персептронов, который можно было реализовать аппаратно. Первая коммерческая реализация предсказателя ветвления персептрона была в микроархитектуре AMD Piledriver .

Основным преимуществом нейронного предсказателя является его способность использовать длинные истории, требуя только линейного роста ресурсов. Классические предикторы требуют экспоненциального роста ресурсов. Хименес сообщает о глобальном улучшении на 5,7% по сравнению с гибридным предсказателем в стиле Макфарлинга. Он также использовал гибридные предикторы, перекрывающие gshare / персептрон.

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

Большинство современных предсказателей ветвей используют предсказатели персептронов (см. Intel «Соревнование по предсказанию ветвей чемпионата»). Intel уже реализует эту идею в одном из симуляторов IA-64 (2003 г.).

AMD Ryzen многоядерный процессор с Бесконечность Fabric и Samsung Exynos процессор включает персептрона на основе нейронной ветви предсказатель.

История

IBM 7030 Stretch , разработанный в конце 1950 — х годов, предварительно выполняет все безусловные ветви и любые условные переходы , которые зависели от индексных регистров. Для других условных ветвей первые две реализованные производственные модели прогнозируют невыполненное; последующие модели были изменены для реализации прогнозов на основе текущих значений бит индикатора (соответствующих сегодняшним кодам состояния). Дизайнеры Stretch учли статические подсказки в инструкциях ветвления на раннем этапе проекта, но отказались от них. Восстановление ошибочного прогноза было обеспечено модулем прогнозирования на Stretch, и часть репутации Stretch в отношении невысокой производительности объяснялась временем, необходимым для восстановления ошибочного прогноза. Последующие разработки больших компьютеров IBM не использовали предсказание ветвлений со спекулятивным исполнением до IBM 3090 в 1985 году.

Двухбитовые предикторы были введены Томом МакВильямсом и Куртом Виддоусом в 1977 году для суперкомпьютера S-1 Национальной лаборатории Лоуренса Ливермора и независимо Джимом Смитом в 1979 году в CDC.

Микропрограммные процессоры, популярные с 1960-х по 1980-е годы и позже, выполняли несколько циклов на инструкцию и, как правило, не требовали предсказания переходов. Однако, помимо IBM 3090, есть несколько других примеров микропрограммных проектов, которые включают предсказание ветвлений.

Burroughs B4900 , микропрограммная COBOL машина выпустила около 1982 года, был конвейерная и б предсказания ветвлений. Состояние предыстории предсказания ветвления B4900 сохраняется обратно в инструкции в памяти во время выполнения программы. B4900 реализует предсказание ветвления с 4 состояниями с использованием 4 семантически эквивалентных кодов операций ветвления для представления каждого типа оператора ветвления. Используемый код операции указывает историю этой конкретной инструкции перехода. Если оборудование определяет, что состояние прогнозирования ветвления конкретной ветви необходимо обновить, оно перезаписывает код операции семантически эквивалентным кодом операции, который указывает на правильную историю. Эта схема имеет процент совпадений 93%. Патент США 4 435 756 и другие были выданы по этой схеме.

VAX 9000 , объявленный в 1989 году, как микропрограммный и конвейерное и прогнозирование выполняет филиал.

Первые коммерческие процессоры RISC, MIPS R2000 и R3000, а также более ранние процессоры SPARC , делают только тривиальное предсказание ветвлений «не выполнено». Поскольку они используют слоты задержки перехода, выбирают только одну инструкцию за цикл и выполняются по порядку, потери производительности нет. Более поздний R4000 использует такое же тривиальное предсказание «невыполненного» ветвления и теряет два цикла для каждого взятого ветвления, потому что повторение разрешения ветвлений длится четыре цикла.

Прогнозирование ветвлений стало более важным с появлением конвейерных суперскалярных процессоров, таких как Intel Pentium , DEC Alpha 21064 , MIPS R8000 и серия IBM POWER . Все эти процессоры полагаются на однобитовые или простые бимодальные предикторы.

DEC Alpha 21264 (EV6) использует предиктор следующей строки, замещенный комбинированным локальным предиктором и глобальным предиктором, где выбор комбинирования выполняется бимодальным предиктором.

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

Альфа 21464 (EV8, отменен в конце конструкции) имел минимальную ветвь misprediction штрафа в размере 14 циклов. Он должен был использовать сложный, но быстрый предсказатель следующей строки, замененный комбинированным бимодальным предсказателем и предсказателем с большинством голосов. Большинство голосов было между двухрежимным и двумя предикторами gskew.

В 2018 году проект Zero компании Google и другие исследователи обнародовали катастрофическую уязвимость системы безопасности под названием Spectre . Эта уязвимость затрагивает практически все современные процессоры и заключается в извлечении частных данных из оставшихся кешей данных неверных предсказаний ветвлений.

Источник