Есть ли случай, когда бимодал будет лучше, чем не брать?

Question

Учитывая эти два метода:

• Динамический бимодальный:
  • Там, где у нас есть 4 этапа, по 2 этапа для каждого (взятый или не взятый) и чередующийся каждый раз, когда алгоритм предсказывает неверное, переходя от принятого<->не принятого после 2 последовательных неправильных предсказаний
• Статическое не принято:
  • Здесь алгоритм всегда будет предсказывать, что принято или не принято. Переключение между двумя этапами после каждого неверного прогноза.

Я протестировал оба алгоритма с помощью следующего кода на C:

for(i=0; i<4; i++) {

}

и анализируя if условна.

for(i=0; i<4; i++) {
   if( i%2 ) {

   }
   else {
   }
}

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

Answer 1

Предсказатель Static Not Taken (SNT) почти всегда (намного) хуже любого другого предиктора. Основными причинами этого является то, что это плохо с предсказанием потока управления циклами, потому что он будет предсказывать, что он не будет принят на каждой итерации.

Давайте предположим, что первый цикл C будет скомпилирован примерно так:

loop body
compute loop condition
branch to the loop body if condition met

Таким образом, есть только одна ветвь в конце. Предиктор SNT будет прогнозироваться не 4 раза, а ветвь 3 раза. Таким образом, точность составляет 25%. С другой стороны, бимодальный предиктор с начальным состоянием 10 или 11¹ достигнет точности 75%. Начальные состояния 01 и 00 обеспечат точность в 50% и 25% соответственно. 10 или 11 считаются хорошими начальными состояниями.

Давайте предположим, что второй цикл C будет скомпилирован примерно так:

compute the if condition
branch to the else body if condition met
the if body
non-conditional branch to the end of the loop
the else body
compute loop condition
branch to the loop body if condition met

Итак, есть две условные ветви. Предиктор SNT будет прогнозировать не взятые 8 раз, но 5 из них являются ошибочными (есть 5 тактов и 3 не взятых²). Так что точность составляет 37%. Для бимодального предиктора давайте предположим, что каждая ветвь использует один и тот же счетчик. Бимодальный предиктор с начальными состояниями 10 или 11 достигнет точности 63%. Бимодальный предиктор с начальными состояниями 00 или 01 достигнет точности 25% и 50% соответственно. Если каждая ветвь использует свой счетчик с одинаковым начальным состоянием, расчеты аналогичны.

---

[1] Где 00 и 01 означают, что они не приняты, а 10 и 11 означают, что они заняты.

[2] T, T, NT, T, T, T, NT, NT.