Состояния 2-битного предсказателя переходов

Я читал раздел предсказания динамического ветвления в главе 5 книги Computer Organization and Design: The Hardware/Software Interface 5th Edition Паттерсона и Хеннесси, когда наткнулся на следующую диаграмму состояний 2-битного предсказателя:

введите здесь описание изображения

2-битный предсказатель должен изменить свое предсказание после того, как он предсказал дважды неправильно. Но согласно этой диаграмме, когда мы начинаем с нижнего левого состояния, если машина дважды предсказывает «НЕ ВЗЯТ» тогда, когда ветвь должна была быть «ВЗЯТА», тогда достигается верхнее правое состояние ПРОГНОЗ ВЫПОЛНЕН. Однако здесь машина изменит состояние на правый нижний PREDICT NOT TAKEN, даже если она предскажет неправильно, когда ветвь должна была быть «НЕ ВЗЯТА» только один раз.

Разве это не неправильное поведение и означает ли это, что конечный автомат неверен или я что-то упускаю?

В нижнем темном состоянии NOT TAKEN, когда ветвь TAKEN дважды, вы можете видеть, что достигнутое состояние является светлым «неуверенным» состоянием, тогда как, по моему мнению, оно должно было быть темным «уверенным» состоянием, так как ветвь проделал одно и то же действие два раза подряд.


cpu-architecture branch-prediction
person Rijul Ganguly    schedule 11.12.2019    source источник
comment
Какое поведение вы считаете неправильным? Состояния, окрашенные в светлый цвет, представляют ЦП, не уверенный в том, следует ли выполнять переход или нет. В этой ситуации достаточно одного неверного предсказания, чтобы заставить его передумать. Когда он находится в темном состоянии, он более уверен в переходе, поэтому требуется два ошибочных предсказания подряд, чтобы заставить его изменить предсказание. Очевидно, что легко найти патологические примеры (например, вы можете потерпеть неудачу в 100% случаев, если вы начинаете в светлом состоянии и имеете чередующийся паттерн: взято-не взято-взято-не взято-...).   -  person jdehesa    schedule 11.12.2019
comment
В нижнем состоянии NOT TAKEN темного цвета, когда ветвь TAKEN дважды, вы можете видеть, что достигнутое состояние является светлым неуверенным состоянием, тогда как, по моему мнению, оно должно было быть темным уверенным состоянием, поскольку ветвь выполнила то же самое действие два раза подряд.   -  person Rijul Ganguly    schedule 11.12.2019

Ответы (1)


arrow_upward
2
arrow_downward

В нижнем темном состоянии NOT TAKEN, когда ветвь TAKEN дважды, вы можете видеть, что достигнутое состояние является светлым «неуверенным» состоянием, тогда как, по моему мнению, оно должно было быть темным «уверенным» состоянием, так как ветвь проделал одно и то же действие два раза подряд.

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

Это 2-битный счетчик насыщения; требуется 3 шага, чтобы пройти весь путь от 00 до 11, что соответствует 3 шагам на этом графике.

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

Вы можете найти подробный пример такого предиктора в ответе Раффзана на How работает ли предсказатель ветвления 68060? в retrocomputing.SE, включая статическое предсказание (обратное взятие, прямое невыполнение), когда вы получаете промах BPB (нет записи предсказания для этой ветви).

Двухбитный предсказатель очень далек от совершенства; более продвинутые предикторы также учитывают, предсказывает ли глобальная история эту ветвь лучше, чем локальная. https://danluu.com/branch-prediction/

person Peter Cordes    schedule 11.12.2019
comment
Светло-синий цвет означает, что выбрано то, что вы хотите, после двух последовательных переходов. Если ветвь будет взята с этого момента, дальнейших ошибочных прогнозов не будет. - Да, но что произойдет, если ветвь НЕ ВЫБРАНА один раз, когда процессор находится в светло-голубом состоянии? Согласно диаграмме, он сразу переходит в светло-серое состояние и начинает предсказывать NOT TAKEN, что не должно быть тем, что должен делать 2-битный предиктор. - person Rijul Ganguly; 11.12.2019
comment
@RijulGanguly: Да, это то, что будет делать 2-битный предиктор, нравится вам это или нет. Почему вы считаете, что было бы лучше поступить иначе, или какие-либо другие причины для ваших требований? - person Peter Cordes; 11.12.2019
comment
Я понял, где ошибся. Я не учитывал второй неправильный прогноз TAKEN при подсчете неправильного прогноза NOT TAKEN. Мне казалось, что государственная система меняет свой прогноз после всего лишь одного неверного ПРИНЯТОГО прогноза. Спасибо :) - person Rijul Ganguly; 11.12.2019