作者wheels ()
看板Grad-ProbAsk
標題Re: [理工] [計組] 2-bit predictor
時間Mon Aug 22 13:12:54 2011
※ 引述《blackZ2 (ＢＢ)》之銘言：
: ※ 引述《mqazz1 (無法顯示)》之銘言：
: assume that the breakdown of dynamic instructions into various instruction
: categories is as follows:
: R-type 50%, beq 15%, jump 10%, lw 15%, sw 10%
: branch predictor accuracies: always-taken 40%, always not-taken 60%, 2-bit 80%
: (1) with the 2-bit prdictor, what speed-up would be achieved if we could
: convert half of the branch instructions in a way that replaces a branch
: instruction with an ALU instruction?
: assume that correctly and incorrectly predicted instructions have the same
: chance of being replaced
: 1 + 3*(1-0.8)*0.15
: --------------------------------
: 1 + 3*(1-0.8)*0.15*0.5
: 請問這題為什麼要加1?
: 因為理想CPI為1，然後加上branches penalty 就是實際CPI
: (2)同上，把黃字改成two ALU
: 1 + 3*(1-0.8))*0.15
: --------------------------------
: 1 + (1 + 3*(1-0.8))*0.15*0.5
: 請問為什麼還要再加1?
: 因為這各式子化簡了，所以看起來很怪
: 請想成 1 + 0.15*0.5*0.2*3 + 0.15*0.5*1
: 理想CPI 沒有轉換的一半branch 一半branch轉成兩個ALU,指令會變多
: 化簡之後就是 1+(1+0.2*3)*0.15*0.5
: 這是我自己的想法，希望是對的
這樣說好精簡，我來幫你多做補充。
1 + 0.15*0.5*0.2*3 + 0.15*0.5*1
理想CPI， 猜錯的branch中 猜對和猜錯的branch轉成兩個ALU
已經包含猜對的branch 未轉換的一半branch 的部分，若把它拆成
中未轉換成ALU的部分。 0.15*0.5*0.8*1+
0.15*0.5*0.2*1將會更清楚。
對於猜對的部分，原本只需花一次
執行，但轉成ALU後要花兩次執行
這一項就是指多做的那一次。
原本花的那一次已經包含在理想
的CPI裡面。
對於猜錯的部分，原本要有3的
penalty，但是轉成ALU後可以想為
執行兩次ALU即可取代penalty，
而原本就需要做一次了，剩下的那
次是多做的，整體來看就跟上面那
段是一樣的。
其實這題答案有問題，因為一個branch轉換成兩個ALU，
勢必會造成指令的比例改變，所以真正的答案應該是：
1 + 1*(0.15/1.075)*0.5 + 3*0.2*(0.15/1.075)*0.5
因為現在所有指令加起來是107.5%，所以原本比例要除掉1.075做修正，
我有把上面這個想法寄信跟張凡說過，張凡也拿去問同事後最後的結論還是，
＂照課本吧XD＂
所以就當我沒說過這段吧XD
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 111.249.12.39
※ 編輯: wheels 來自: 111.249.12.39 (08/22 13:34)
→ blackZ2:＂照課本吧XD＂ 張凡每次都很無奈的講這一句 08/23 00:48
→ wheels:白算盤的錯誤率真的還滿高的感覺@_@ 08/23 01:11
推 flygey:這題可改成3個ALU嗎 如果可以的話那公式是怎麼算? 08/24 01:08
→ wheels:如果改成3個ALU取代的話就是多做兩次，所以最後那邊改成 08/25 00:38
→ wheels:0.15*0.5*2就可以了 08/25 00:39
→ wheels:當然也是忽略掉比例有變的情況下啦！ 08/25 00:57
推 flygey:有個地方想再請問 為何一個alu取代時 只把原式*0.5 08/25 22:47
→ flygey:然後 兩個ALU才多加一個 0.15*0.5*1 ? 08/25 22:48
→ wheels:不是不是，原式是0.15*0.5*1，是把最後乘1改成乘2，因為變 08/25 22:53
→ wheels:成多作兩次了！ 08/25 22:53
→ wheels:唉呀我看錯你的問題了，我以為你問的是是3個ALU 08/25 22:59
→ wheels:用一個alu取代時，因為原本就需要作一次啦，已經算在理想 08/25 22:59
→ wheels:CPI裡面了，後面有加的都是額外的 08/25 23:00
推 flygey:原本ALU需要做一次? 是指跑過5個stage? 還是在哪裡的ALU? 08/26 00:08
→ wheels:在0.15*0.5*0.2*3裡面最後乘上的那個3是因為如果wrong的時 08/26 01:14
→ wheels:候將造成管線空了三個clock cycle time，而在0.15*0.5*1裡 08/26 01:15
→ wheels:最後乘上那個1是因為管線裡原本預測對的話一個clock cycle 08/26 01:16
→ wheels:time將完成一個指令，但是branch因為置換的關係會讓這個指 08/26 01:17
→ wheels:令實際上要兩個clock cycle time才能跑完，所以多一次。 08/26 01:17
→ wheels:因為pipeline裡面在指令數很多的時候每一個clock cycle 08/26 01:18
→ wheels:time都會有一個指令完成才能這樣看的。 08/26 01:19
推 flygey:第三部份 0.15*0.5* 1(=0.8*1+.02*1) 是說換成ALU 所以沒有 08/26 01:35
→ flygey:pently 這樣嗎? 08/26 01:36
→ flygey:只是單純把 猜對和猜錯的 加起來 08/26 01:37
→ wheels:因為已經整個用兩個ALU取代了，你可以想成已經沒有penalty 08/26 20:21
→ wheels:這個概念在裡面，只有多做一次所以才造成要多加的部分。 08/26 20:22
→ wheels:我發現你可能卡在為啥換過去就沒有penalty了這個想法裡， 08/26 20:22
→ wheels:想乘換過去就只有多做一次，管線內沒有需要停的時候，這樣 08/26 20:23
→ wheels:可能會比較清楚，而0.15*0.5*0.2*3後面乘上3是因為wrong將 08/26 20:24
→ wheels:造成管線要清空後面三個指令，才會有所謂的penalty的概念！ 08/26 20:24
→ wheels:希望有幫助到你。 08/26 20:25
推 bahamut5461:看完推!!! 01/01 20:47