Число пропущенных динамических предсказаний ветвлений - неверно

Question

Я искал в интернете несколько примеров о dbp и нашел это.Источник: http://faculty.cse.tamu.edu/djimenez/614-spring14/bpexample.html (включая решение)

Код:

main:
        leal    4(%esp), %ecx       ; function overhead
        andl    $-16, %esp
        pushl   -4(%ecx)
        pushl   %ecx         ; gcc stack alignment at the top of main

        xorl    %ecx, %ecx      ; i = 0 (%ecx)
.L2:                                       ; top of outer loop
        xorl    %edx, %edx      ; j = 0 (%edx)
.L3:                                             ; top of inner loop
        movl    c, %eax             ; %eax = c
        addl    $1, %edx            ; j++
        addl    $1, %eax            ; %eax++
        movl    %eax, c             ; c = %eax
        cmpl    $4, %edx            ; if j < 4 then goto L3
        jne     .L3                 ; INNER LOOP BRANCH

        addl    $1, %ecx         ; i++
        cmpl    $1000, %ecx      ; if i < 1000 then goto L2
        jne     .L2              ; OUTER LOOP BRANCH

        movl    c, %eax          ; return c

        popl    %ecx             ; function overhead
        leal    -4(%ecx), %esp
        ret

Для 1-битного предиктора, начинающегося с нуля, результат должен быть 2002. В моей логикебудет 1 промах во внутреннем цикле (как он возвращается из внешнего цикла с предсказанием T), в общей сложности 1000x, и 1 промах во внешнем цикле 999x (потому что цикл будет предсказываться как NT от конца внутреннего цикла).Это делает 1999, + 1 промах в начале.Это составляет 2000 в общей сложности.Я заметил, почти каждый раз, когда я примерно в 1 цикле отрываюсь от реального решения (в других примерах тоже).Я также пытался разработать счетчик пропусков, который проверяет каждое условие в каждом цикле, но он только подтвердил мой результат (2000 или 1999, если предиктор установлен в T), поэтому либо я не понимаю его правильно, либо что-то не так с моей логикой подсчета.

Не могли бы вы объяснить мне, что я делаю неправильно?

---

Asm был скомпилирован из этого C.

int c;
int main ()
{
  int i, j;
  for (i=0; i<1000; i++) {
     for (j=0; j<4; j++) {
       c++;
     } 
  } 
  return c; 
}

Answer 1

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

Вы 'мы говорим о предсказании для внутреннего цикла в зависимости от того, что сделала ветвь внешнего цикла.1-битный предиктор использует 1 бит на запись , а не глобально!Это было бы слишком тривиально.https://danluu.com/branch-prediction/

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

---

Ваш анализ, к сожалению, содержит ошибки даже в принятом вами 1-битном глобальном состоянии.

На первой итерации ветвь внутреннего цикла является первойветвь в функции, потому что C скомпилирован в do{}while(--i) цикл asm (с некоторым уровнем оптимизации gcc, но явно недостаточно для превращения его в add $4000, c).

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

Будет 1 промах во внутреннем цикле (поскольку он возвращается из внешнего циклас прогнозом T),

Первые 3 раза, когда выполняется внутренняя ветвь цикла, принимается , поэтому прогноз T верен.Возможно, ваш анализ смотрел на абстрактную машину C, где перед первой итерацией есть условная ветвь if (!i<1000) goto loop_bottom в верхней части цикла?Как вы могли бы получить в неоптимизированных выходных данных компилятора?

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

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

---

Для независимых 1-битных предикторов для каждой ветви

2000 неверно предсказывает внутреннюю ветвь цикла (1 каждая на первой и последней итерации каждого внутреннего цикла = тело внешнего цикла).

2 неверно предсказывает ветвь внешнего цикла (по 1 на первой и последней итерациях внешнего цикла).

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