2 бита ветвь предсказатель с двумя для петель

Question

я получил 2 битную ветку предсказатель, мое начальное состояние слабо принят, и мне нужно рассчитать точность предсказания:

for (int i=0; i < 100; i++) 
{ 
    for (int j=0; j < 50; j++) 
    { 
    ... 
    } 
} 

Так что с I = 0 мы берем ветку , поэтому мы находимся в i = 0 и j = 0 и ставим наш предиктор в строго взятый, не так ли? Итак, если мы итерации j теперь, значит ли это, что мы не берем новую ветку? Поскольку мы все еще находимся в ветке i = 0 или каждая итерация считается новой ветвью?

Answer 1

Давайте вручную скомпилировать его в сборку x86 первых для лучшего понимания (любой другой сделал бы):

mov ebx, 0  // this is our var i 
.L0: 
# /------------ inner loop start -----------\ 
    mov eax, 0  // this is our var j 
.L1: 
    // ... 
    add  eax, 1 
    cmp  eax, 50 
    jl  .L1  // jump one 
# \------------ inner loop end -------------/ 
    add  ebx, 1 
    cmp  ebx, 100 
    jl  .L0  // jump two 

Я думаю, что этот код довольно прямо вперед, даже если вы не знакомы со сборкой:

• Set EBX в 0
• прыжок два получает назад здесь
  • Set е в 0
  • прыжок один возвращается сюда
    • Выполнить наш код цикла // ...
    • добавить 1 к е
    • сравнить е в 50 (это устанавливает некоторые бит в флагом регистр)
    • прыжок маркировать .L1:, если EAX не 50
  • добавить к 1EBX
  • сравнить EBX к 50 (это устанавливает некоторые биты в регистре флага)
  • прыжок на этикетке .L0:, если ebx не был 100
• Конец слова опс

Итак, на первой итерации мы приходим к прыжком один и предсказать, будет принято. Начиная с eax < 50 мы берем его и обновляем до решительно взятых. Теперь мы делаем это еще 48 раз. На 50-й итерации мы не прыгаем, потому что eax == 50. Это одно неверное предсказание, и мы обновляемся до слабо взятого.

Теперь мы приходим к прыгать два в первый раз. с ebx < 100 берем его и обновляем до решительно взято. Теперь мы начинаем все с этого внутреннего цикла, перепрыгивая на L0. Мы делаем это еще 98 раз.На 100-й итерации внутреннего цикла мы не прыгаем, потому что ebx == 100. Это одно неверное предсказание, и мы обновляемся до слабо взятого.

Так мы выполняем innerloop 100 раз с одной misprediction каждый в общей сложности 100 mispredictions для скачка один и 100 * 49 = 4900 правильные предсказания. Внешний цикл выполняется только один раз и имеет только 1 неверное предсказание и 99 правильные прогнозы.