Re: [理工] [計組] branch predictor
※ 引述《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
→
12/25 01:42, , 1F
12/25 01:42, 1F
→
12/25 12:51, , 2F
12/25 12:51, 2F
→
12/25 13:13, , 3F
12/25 13:13, 3F
→
12/25 13:14, , 4F
12/25 13:14, 4F
→
12/25 13:15, , 5F
12/25 13:15, 5F
→
12/25 22:26, , 6F
12/25 22:26, 6F
推
12/25 22:28, , 7F
12/25 22:28, 7F
→
12/25 22:28, , 8F
12/25 22:28, 8F
其實我覺得應該是接近第一種啦...
但是那個敘述還是有點問題，
若按照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)