編程基礎(chǔ)(三)——體系結(jié)構(gòu)之三

? ? ? ? ? ? ? ? ? ?

whenloce ? ? ? ? ? ? ? ? ? ?

? ? ? ? ? ? ? ? ? ? ? ?于?2019-02-15 17:23:19?發(fā)布 ? ? ? ? ? ? ? ? ? ?

? ? ? ? ? ? ? ? ? ?1162 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?收藏 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?7 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

分類專欄： ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?software performance engineeri ? ? ? ? ? ? ? ? ? ?

版權(quán) ? ? ? ? ? ? ? ?

? ? ? ? ? ? ? ? ? ? ? ? ? ?

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?software performance engineeri ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?專欄收錄該內(nèi)容 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

8 篇文章 ? ? ? ? ? ? ? ? ? ? ? ?1 訂閱

訂閱專欄 ? ? ? ? ? ? ? ? ? ?

目錄

一、概述

二、ROB

2.1 ROB結(jié)構(gòu)

2.2 Tomasulo with ROB

2.2.1 issue

2.2.2 dispatch

2.2.3 broadcast

2.2.4 commit

2.2.5 引入rob后對比

三、其他

3.1?Unified Reservation Station

3.2?Terminology Confusion

四、load & store

2.1?tomasulo中l(wèi)oad/store的順序執(zhí)行

2.2 現(xiàn)代計算機上如何實現(xiàn)load/store的亂序執(zhí)行

2.2.1 LSQ結(jié)構(gòu)

2.2.2 LSQ如何工作

2.2.3?LSQ, ROB, RS比較

2.2.4一個問題

一、概述

體系結(jié)構(gòu)之二的延續(xù)，因為二文章太長了，其他的部分在這里描述

二、ROB

在tomasulo的亂序執(zhí)行過程中，我們考慮兩種情況：

• Exceptions in Out-of-Order Execution Tomasulo算法并沒有處理異常情況，這樣位于異常(如除零)之后的指令如果先執(zhí)行會導(dǎo)致錯誤的結(jié)果。

• Branch Mispredictions in OOO Execution?Tomasulo算法并沒有處理Branch Mispredictions情況，這樣如果分支預(yù)測出錯，會導(dǎo)致和上述一樣的錯誤

可以通過ReOrder Buffer解決這個問題：

• Execute OOO

• - Broadcast OOO

• - Deposit values in registers In-Order. This can be achieved with a ReOrder Buffer

ROB可以記錄程序的指令順序并保存執(zhí)行結(jié)果直到可以安全寫入。

2.1 ROB結(jié)構(gòu)

ROB按照program order記錄指令，ROB entry由三個部分組成：

• reg? ? ? 指令對應(yīng)的register

• value? 指令的結(jié)果

• done? ?指令的執(zhí)行標(biāo)記

ROB還有兩個指針commit和issue，如果你了解過intel網(wǎng)絡(luò)控制器，可以知道這兩個指針和隊列頭尾指針類似(RDH,RDT),就是個環(huán)形隊列，issue是頭，指示下一條issue指令在ROB存放的位置，commit是尾，指示下一條需要提交的指令，這樣commit->issue就表示issue但尚未提交，issue->commit表示ROB空閑的entry

2.2 Tomasulo with ROB

引入ROB后，tomasulo執(zhí)行的流程有一些變化，為了對比，下面以列表的形式展現(xiàn),同時給出示意圖，以一條指令執(zhí)行過程說明，執(zhí)行前，如下圖這樣：

2.2.1 issue

TomasuloTomasulo with ROB1. 從IQ中取指從IQ中取指

2. Lookup RAT

? ??如果RAT中對應(yīng)的寄存器有值存在，使用RAT記錄的值

? ? 如果RAT中對應(yīng)的寄存器沒有值，使用register file中的寄存器值

Lookup RAT

3. 獲取空閑的RS entry

? ? 如果RS中空閑的entry，將指令放入RS中

? ? 如果RS中沒有空閑entry，要等待RS空閑

獲取空閑的RS entry

獲取commit指向的ROB entry

如果資源busy等待

4. 標(biāo)記(tag) 目的寄存器

? ? ? ?在RAT中將destination register指向RS entry

標(biāo)記(tag) 目的寄存器

?

在RAT中將destination register指向ROB?entry

和之前相比，用rob entry來代替rs entry 存儲結(jié)果：

2.2.2 dispatch

dispatch執(zhí)行步驟與之前基本類似，區(qū)別在于這個階段會free RS entry，這是因為RS記錄register name的用途被ROB代替了，RS只負責(zé)在操作數(shù)準(zhǔn)備好了dispatch到執(zhí)行單元去執(zhí)行，在這之后這個RS entry就沒有用了，這樣可以更快的為issue提供資源。

2.2.3 broadcast

?

TomasuloTomasulo with ROB

1）將 rs tag和result放在總線上

將 rob tag和result放在總線上

2）結(jié)果寫入RF

無，結(jié)果不寫入RF，而寫入rob entry

3) 更新RAT,如果RAT沒有對應(yīng)的entry說明結(jié)果已經(jīng)寫入RF了

無，不更新RAT,因為RAT指向rob entry4）釋放對應(yīng)的RS entry——修改invalid bit無

?

簡單來說，最后的寫入工作由ROB負責(zé)了，所以broadcast功能減少了，馬上就可以看到，增加了commit步驟寫入。broadcast執(zhí)行結(jié)果示意如下：

2.2.4 commit

commit的步驟是：

1）等待commit指向的指令完成，done置位

2）結(jié)果由ROB entry寫入RF

3）?更新RAT

4)?釋放對應(yīng)的ROB?entry

很明顯，將原來broadcast的工作轉(zhuǎn)移到commit來做

2.2.5 引入rob后對比

->

2.26?

三、其他

3.1?Unified Reservation Station

• Unified reservation stations: combine the reservation stations for the Adder and the Multiplier. All of the reservation stations are in one large array, so the reservation stations can be used when necessary, they do not have to wait for a specific set of RS.

• The down side of the unified RS is the increased complexity in hardware. The hardware must be able to determine the correct arithmetic unit for each entry.

3.2?Terminology Confusion

在paper中經(jīng)常使用術(shù)語：?Issue, Dispatch, Commit，處理器設(shè)計人員經(jīng)常有不同的稱呼：

• issue：allocate(因為分配rs entry，rob entry)，dispatch

• dispatch：execution，issue

• commit： complete，retire， graduate

四、load & store

目前為止，對不同的相關(guān)，我們的解決方法如下：

• Control dependencies? ? ? ? ? ? ?Branch Prediction

• -False dependencies? ? ? ? ? ? ? ?Register Renaming

• Register dependencies? ? ? ? ??Tomasulo-like scheduling

tomasulo算法的load/store操作，都是in-order的，我們知道load/store也有類似RAW,WAW,WAR的數(shù)據(jù)相關(guān)，那么load/store必須按照program order執(zhí)行嗎，是否可以用類似我們解決Register dependencies 的方法讓load/store也進行亂序執(zhí)行從而提高流水線執(zhí)行效率呢。

2.1?tomasulo中l(wèi)oad/store的順序執(zhí)行

2.2 現(xiàn)代計算機上如何實現(xiàn)load/store的亂序執(zhí)行

memory write在commit階段發(fā)生，因為一旦memory寫回就無法挽回了，假如因為預(yù)測錯誤導(dǎo)致store指令先執(zhí)行，這是無法恢復(fù)的。所以將store操作delay到commit階段。而load指令本身需要盡快讀取，因為由于cache miss，load操作經(jīng)常會耗費大量的時間，需要盡快獲取。而load指令沒有store指令那么多限制，即使讀錯了，再讀一遍就好了。

另一方面，很多l(xiāng)oad結(jié)果操作依賴store操作，既然store操作在commit階段才寫入，那么又如何讓load盡快讀取到數(shù)據(jù)呢？cpu設(shè)計者引入了一個稱為LSQ(load store queue)的結(jié)構(gòu)，使load能盡快獲取store的結(jié)果。

2.2.1 LSQ結(jié)構(gòu)

• L/S? load or store

• addr 地址

• value 地址對應(yīng)的值

• C complete

LSQ和ROB類似之處在于，二者指令都是按照program order存儲，在commit完成

2.2.2 LSQ如何工作

load和store指令按照順序進入LSQ，當(dāng)load指令進入LSQ時，使用load的地址和該指令之前的store指令的地址比較，如果匹配上了，就無需再從memory中取值了，稱為Store-to-Load Forwarding。當(dāng)然，一種可能的情況是之前相關(guān)的store指令還沒有addr，那么這個時候load指令該怎么做呢？

• 等待store完成再讀入——本質(zhì)上還是順序執(zhí)行

• 等待前面所有的store完成后，匹配就使用forward，沒有匹配就從memory中獲取

• load speculation，不管前面有沒有相關(guān)的store，直接去內(nèi)存取值，如果前面store addr能確定后證明是錯誤的，recover。現(xiàn)代cpu通常使用這個方法，其性能最高

OOO Load/Store Execution

OOO Load/Store execution occurs when loads go to memory as soon as the address is available. Sometimes this results in stale data being used and then it needs to be recovered.

2.2.3?LSQ, ROB, RS比較

issue

• ?ROB entry available

• ?LSQ entry available?

非load/store指令：

• ROB entry available

• RS available

executing

• Compute the address?

• Produce the value

load操作還要將結(jié)果進行廣播Commit

• -Free the ROB entry

• -Free the LSQ entry

store操作還需要將結(jié)果寫入內(nèi)存

?

2.2.4一個問題

困惑已久，既然指令時順序發(fā)射，亂序執(zhí)行，順序提交，對memory操作來說為什么還會有所謂memory barrier保證memory order呢？在wangqi的大作Cache Memory中：

現(xiàn)代處理器在 Commit 最后的執(zhí)行結(jié)果時大多都采用 In-order 方式，這也保證了指令在
經(jīng)過 Out-of-Oder 的流水線后，程序員看到的最終結(jié)果與程序應(yīng)有的順序一致。多數(shù)程序員
被這一假象迷惑，認為 CPU 的亂序執(zhí)行僅與硬件流水線相關(guān)，并不會影響軟件程序。
事實并非如此。 微架構(gòu)為了實現(xiàn)亂序執(zhí)行，有些指令，比如存儲器讀指令， 可能會提前
執(zhí)行，而后因為種種原因，如分支預(yù)測失敗， 可能會被迫重新執(zhí)行。雖然亂序流水線可以保
證最后的結(jié)果與程序期待的結(jié)果一致，但是無法完全抹去這條本不該執(zhí)行的指令在流水線中，
在存儲器子系統(tǒng)中留下的執(zhí)行痕跡

他在文中舉的例子我也一并列舉：

產(chǎn)生的根源是由于load speculation，

TimeC1C2t0?read A1 (得到舊值)t1write A1?t2increase A2?t3?check A2

假設(shè)t0時刻，C2 check A2指令 cache miss, read A1 進行l(wèi)oad speculation, 此時得到的是A1的舊值

在t1時刻C1更新A1，并在t2更新A2

在t2時刻C2讀取A2，發(fā)現(xiàn)其更新了，該條件下應(yīng)該去執(zhí)行read A1，誤認為此次load speculation是成功的，但是A1的值是舊值！

所以在這種情況下要使用memory barrier

?