Re: [理工] [計組] branch predictor

[yraid (yraid)]

※ 引述《wsx02 ()》之銘言：
: http://ppt.cc/X4MB
: 請問這邊的意思指的是 1 還是 2 ?
: 1.                              2.
: for(i=1~10)                     for(i=1~10)
: {                               {
:         for(j=1~20)                     for(j=1~20)
:         {                               {
:                 beq                             beq
:         }                               }
:         beq
: }                               }

根據原文 ...a single branch instr. at the end of "each loop"..
比較接近第一種，但是不是你寫的這個意思，
他是因為有branch instruction才會有loop的，不用額外弄for loop出來...

舉例來說，一層loop像是這樣：

Loop:
        ...
        ...
        ...
        beq Loop


: 又請問這3種方法的正確率是多少呢?
: 謝謝

(1)總是猜跳
總共猜了200(內)+10(外)= 210次
每次都猜對，除了loop裡的最後一次，
因為最後一次是要離開loop，所以不跳(循序執行)
因此總共猜錯10+1=11次

準確率:(210-11)/210

(2)1-bit

"原則上"
每一輪(21次)的準確率為(21-2)/21
實際上第一輪的第一次是猜錯的(一開始猜不跳，但他第一次就跳了)
以及最後一輪的最後一次是猜對的(因為外層迴圈每次都跳除了最後一次)
因此"實際上"第一輪和最後一輪會"多"猜錯一次和"少"猜錯一次，
當成抵銷的話來看，準確率就是(210-20)/210

恩..看起來很繞口，畫個粗略的示意圖：
(T:跳 N:不跳 0:猜不跳 1:猜跳 V:猜對 X:猜錯)

T.....TN T  T.....TN T .......... T.....TN N
01....11 0  1.....11 O .......... 1.....11 0
XV....VX X  V.....VX X .......... V.....VX V


(3)2-bit

用同樣的方法去推敲，
算出來的答案是(210-13)/210



自己算的，有錯請指證QQ
謝謝


--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 111.240.168.147
→ BaaaSwin:請問1bit和2bit的初始狀態怎麼設定??
→ yraid:這裡1-bit和2-bit都是假設從0開始
→ BaaaSwin:1bit每一輪結束(除了最後一輪),不是都是猜跳嗎??
→ BaaaSwin:!!!我懂了
→ BaaaSwin:謝謝
→ wsx02:感謝y大的回文 原文中d大好像用2.的方式 共200次beq的方法
推 wsx02:這樣關鍵應該是在題目指的是1的210次beq
→ wsx02:還是2的200次beq
其實我覺得應該是接近第一種啦...
但是那個敘述還是有點問題，

若按照for loop來說，就是

for(i = 0; i<10; i++)
   for(j = 0; j<20; j++)

這裡不用額外再補beq進去...
可以想像成把c裡的for loop翻成組語，自然就會加上branch指令。

因為每次for loop最後都會有跳躍發生(有跳躍才會形成loop)
除了最後一次，因為不滿足該層loop的條件就會不跳，離開loop。

而題目的敘述就是在說這個意思，沒有跳躍指令就不會形成loop，
因此當然兩層loop最後都有跳躍指令囉...

in 組語的話，它的雙層迴圈意思應該是這樣


        addi $t1, 10            //i initialize to 10
Ounter:

        /* statement */

        addi $t2, 20            //j initialize to 20
Inner:
        /* statement */

        addi $t2, -1            //j--;
        bne $t1, $zero Inner    //when j is 0, exits inner loop

        /* statement */

        addi $t1, -1            //i--;
        bne $t2 $zero Outer     //when i is 0, exits outer loop

※ 編輯: yraid           來自: 111.240.173.66       (12/25 23:40)