[理工] 103交大資工 計組

[HiltonCool (野獸瘋)]

12. We know that ... the original MIPS design determines branches in the MEM
    stage. Assume that originally 40% of the total instructions are beq, where
    75% of them compare one register with zero. Other 25% original "beq" has
    to be changed：
                  beq r3,r5,1000 → sub r1,r3,r5
                                    bez r1,1000
想問的是(c)和(d)小題
(c) Assume no dynamic prediction and no assume-branch-not-taken prediction
    are provided, the CPI of your new design will be 1.9.

(d) The overall speedup over the original design will be no more than 1.16.

(c)小題張凡的算法是 1 + 0.4x0.25 + 0.4x2 = 1.9
他的說法是：0.4x0.25 是多出來的 sub 指令所增加的 CPI
而 0.4x2 是因為 beq 指令造成的 pipeline stall
當初聽的時候感覺很合理，所以就覺得沒什麼問題
但最近考古題寫到這題的時候，想法完全不同
我的答案是：1 + 0.4x3 = 2.2

[疑問一] 題目說 branch 在 MEM 階段決定要不要跳，所以如果是因為 beq 猜錯
         而造成的 penalty 不是應該是 3 個 clock 嗎？
         張凡的算法只停了 2 個 clock，是因為 new design 是指課本在把 beq
         決定跳或不跳的時間點搬到 ID 之前，原本是在 EX 算出兩個暫存器是否相等
         即可決定決定跳或不跳的這個 design 嗎？

[疑問二] 原本想說 beq 指令前面跟的是 R-type 指令，而這兩個指令有 data hazard
         那必須在這兩個指令中間插一個 NOP，這樣的話算法會變成是
         1 + 0.4x3(beq stall) + 0.4x0.25x1(stall between R-type & beq) = 2.3
         這個算法的前提是 beq 在 ID 階段決定要不要跳的做法，但現在題目說
         beq 在 MEM 階段決定要不要跳，那前面的 R-type 指令即使把正確的資料
         forward 給 beq 指令也沒用，因為他在 ID 的時候也沒決定跳或不跳，
         還是要等到 MEM 才決定，如此一來，就算剛剛花了一個 clock forward
         後面兩個指令還是錯的，整個程式的執行也是錯的，所以根本也不用 forward
         這樣的算法就會是 1 + 0.4x3 = 2.2

[疑問三] 對於增加的 sub 指令可以直接加在 CPI 裡面我覺得有點怪怪的
         之前張凡好像是說可以把它看成類似 stall 一個 clock 的感覺
         但就是有種說不上來很奇怪的感覺，這樣不就變成 IC 跟 CPI 成正比？！
         這樣的話算法又會變成是 1 + 0.4x3 + 0.4x0.25x1(增加的sub) = 2.3

(d)小題姑且不論(c)小題算出來的 CPI 是多少
speedup 不是應該等於
 IC_old x CPI_old x Cycle time      1 x (1 + 0.4x3)      2.2
──────────────── = ───────── = ─── = 1.0526
 IC_new x CPI_new x Cycle time        1.1 x 1.9          2.09

題目說 no more than 1.16，所以我覺得是錯的
不知道是我觀念哪邊出錯了，最近有空閒的時間一直在想這題
跪求大家幫忙解惑

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.42.169.91
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1422376747.A.8AC.html
→ GuardmanMart: (c)沒有猜測branch-not-taken，所以只要有一個指令
→ GuardmanMart: 到ID階段確定為branch指令後，之後的新指令都要stal
→ GuardmanMart: l，直到那個branch指令到MEM階段確認完跳或不跳後，
→ GuardmanMart: 後面的指令才能繼續，所以有2個cycle的stall
→ GuardmanMart: 可是解答上c選項是incorrect 所以算出來應該不是1.9
→ GuardmanMart:  !? 感覺怪怪的
但是當 beq 到 MEM 的時候，IF、ID、EX 不是早就已經跟了三個指令進 pipeline 了嗎？
這樣的話不是應該要 flush 掉三個指令嗎(相當於 stall 3 clock)？
張凡給的解答算出來是 1.9，所以他的答案(c)是選對的，所以交大是公布(c)是錯的嗎？
※ 編輯: HiltonCool (114.42.169.91), 01/28/2015 01:48:29
→ zero0o0o8279: 我想法也一樣欸
是跟我一樣嗎？還是跟張凡一樣@@?
※ 編輯: HiltonCool (114.42.170.15), 01/28/2015 21:56:05
推 galapous: 我覺得沒錯捏,這題不是說呈上題,上題說這指令是在EX決定
→ galapous: 要不要跳,所以就是清ID跟IF的指令,所以stall 2 cycle
→ galapous: 因為他在EX決定要不要跳,所以有data hazard的話用forwar
→ galapous: ding就可以解決了
推 galapous: 不過我也覺得C是錯的,CPI應該是1.9/1.1然後D是對的這樣
→ galapous: 還有想問為啥這選項沒給branch跳的機率就可以算,假如都
→ galapous: 跳得話不就都不用stall?
靠邀...我眼殘...瞬間突破盲點XD
(c)小題你的算法應該是對的，應該要再除以 1.1 沒錯，不然直接把多出來的指令加在
CPI 上真的很怪，其實題目沒有給跳的機率也是很怪，因為這樣的算法是假設 beq 永遠
猜錯的算法，不過這種東西也沒辦法自己假設，好像也只能這樣算了
※ 編輯: HiltonCool (114.42.170.15), 01/29/2015 00:03:35
推 galapous: 哈哈,沒寫這年,想說看一下原題目才發現有呈上題,恭喜啦!
他還用底線畫起來，考試如果因為這樣算錯真的會幹死，感謝樓上大家的回覆
※ 編輯: HiltonCool (114.42.170.15), 01/29/2015 00:44:31
推 acicularman: D是對的 舊的time是1+0.4*3 所以2.2/1.9=1.15x<1.16