近期因相關課程需要完成一個關于指令級并行(ILP)的彙報，我的主題為“以動态排程、多發射和推測來開發ILP”，是教材《計算機體系結構——量化研究方法》的第三章第九節内容，這裡記錄下來，用于以後回顧。
筆記分為以下幾個部分：
- 複習
- 流水線
- 流水線冒險
- 動态排程
- 推測
- 多發射
- 将它們結合起來
首先來介紹一下什麼是流水線以及使用流水線所産生的一些問題
流水線是一種用來将多個指令重疊執行的技術。
上圖是一個簡單的例子，不使用流水線技術時，處理器每800ps完成一條指令，為了提高執行指令的吞吐量，将指令的執行劃分為五個階段(取指、譯碼、執行、訪存、寫回)并添加相應的運算單元後，處理器就可以重疊執行指令了，如上圖中的第二張圖所示，修改後的流水線每200ps就可以執行完一條指令，提高了吞吐量，可以看到流水線隻是提高了處理器執行指令的吞吐量，并沒有減小每天指令的執行周期，第二張圖中執行每條指令還是需要800ps。
這裡插入簡單介紹一些經典五級流水線每個階段：
- 取指(IF)，從指令存儲器中讀取指令
- 譯碼(ID)，對指令進行解析，同時讀取寄存器
- 執行(EX)，執行操作或者計算位址(對于載入/存儲指令)
- 訪存(MEM)，從資料寄存器中讀取操作數(對于載入/存儲指令)
- 寫回(WB)，将結果寫回寄存器
但是指令之間會存在一些資料相關等問題，是以流水線技術也會有一些局限性，接下來介紹三種常見的流水線冒險
- 結構冒險，即硬體不支援多條指令在同一個時鐘周期中執行。
- 資料冒險，發生在由于一條指令必須等待另一條指令的完成而造成的流水線停頓的情況下。具體有兩個原因：
- 資料依賴，也叫做真資料相關。就是兩條指令間存在一個寫後讀(RAW)問題，也就是第一條指令要寫的資料，剛好要被第二條指令使用，而又因為第一條指令需要在流水線的第5個階段(寫回)才會真正将資料寫入寄存器中，而第二條指令在流水線第3個階段(執行)就需要這個資料了，是以産生了這種真資料相關，可以通過旁路(bypassing)技術和停頓(也稱為氣泡)方法來解決。
- 名稱依賴，也就是兩條指令對同一個寄存器進行讀後寫(WAR)或者寫後寫(WAW)，和上面的寫後讀不一樣，讀後寫和寫後寫不會産生資料流動，也就是兩條指令之間其實不是真正的資料相關，隻是因為要操作同一個寄存器而産生的依賴關系，可以通過寄存器重命名(register renaming)方法來解決。
上圖是一個通過旁路技術來解決寫後讀問題的例子，第一條指令修改了寄存器s0的資料，第二條指令需要讀取s0的資料，旁路技術通過在得到s0資料的那個周期，直接将資料通過一個旁路送到需要這個資料的地方，可以看那條藍色的線路，正常情況下第一條指令需要在WB階段才能修改s0的值，但通過旁路，可以在EX階段獲得資料後直接送到第二條指令的譯碼(ID)階段，避免産生停頓。
上圖是另外一個例子，由于這個例子中第一條指令是一個載入指令，必須要等到MEM階段才能得到資料，但是第二條指令在EX階段就要使用資料了，我們無法将未來的資料送給現在，是以這種情況下無法使用旁路技術，是以可以看見兩條指令間有一個停頓，即藍色的氣泡(bubble)。
- 控制冒險，因為決策依賴于一條指令的結果，而這條指令正在執行中而發生。簡單來說就是因為條件判斷語句，在分支被解析前不能得知指令是否需要執行，會影響流水線的吞吐量。解決方法有停頓、分支預測(branch prediction)和延遲分支(delayed branch)。
上圖是使用分支預測來解決分支冒險的例子，第二條指令需要一個判斷，而判斷的結果不能很快得到，為了不産生停頓，是以處理器預測這條指令不會跳轉，是以處理器繼續執行第三條指令而不是停頓等待結果，分支預測簡單的說就是為了不停頓，是以就預測一個結果，讓處理器先去執行那條預測的指令，分支預測技術還有其他的細節，如果感興趣可以去閱讀教材，這裡不是重點。
上圖中分支預測失敗，是以對停止執行之前預測得到的指令，即簡單的插入氣泡，然後去執行正确的指令。
關于延遲分支技術，簡單來說就是在分支解析的時候，去執行一條與分支無關的指令來避免流水線停頓。
這裡不會過多介紹動态排程，我的重點在推測和多發射，這裡主要列舉動态排程的特點：
- 亂序執行
- 亂序完成
- 非精确異常，一種因為亂序完成而導緻的問題，即在發生異常時，有一些本不應該被執行的指令已經被執行了，或一些本應該被執行的指令卻還未被執行。
- Tomasulo算法，一種動态排程使用的算法
動态排程的執行指令過程分為發射、執行、寫結果三個部分。
推測技術主要是為了克服控制相關的限制，去開發更多的ILP。
思想：
- 同動态分支預測選擇要執行哪些指令
- 利用推測，可以在解決控制相關問題之前執行指令(能夠撤銷錯誤推測序列的影響)
- 進行動态排程，以應對基本子產品不同組合方式的排程
特點：
- 額外的指令送出
- 重排序緩沖區
- 順序送出
我們來看一下基于硬體推測的基本結構圖：
其中紅色框是在動态排程結構的基礎上進行改變的部分，黃色框是動态排程結構的重點部分，接下來進行解釋。
重排序緩沖區(reorder buffer，簡稱ROB)：這是推測新加入的一個硬體，因為有了ROB，在推測的指令執行過程中的寫結果後又多加了一個指令送出，是以推測下的指令執行有四部分，分别是發射、執行、寫結果和送出。ROB中擴充了寄存器集，會在一定時間内儲存指令的結果，這段時間從完成該指令的相關運算算起，到該指令送出完畢為止，寄存器和存儲器隻有在指令送出之後才會被更新(即我們非常确定該指令會被執行)，是以ROB是在指令執行完畢到指令送出這段時間内提供操作數。ROB類似于Tomasulo算法中的存儲器緩沖區，是以将載入緩沖區(load buffers，第二個紅色框)旁邊的存儲器緩沖區內建到ROB中了。
保留站(reservation stations，簡稱RS)：保留站提供了寄存器重命名功能，解決了WAR和WAW問題，它為等待發射的指令緩沖操作數，基本思想是：保留站在一個操作數可用時馬上提取并緩沖它，這樣就不再需要從寄存器中擷取該操作數。此外，等待執行的指令會指定保留站，為自己提供輸入。最後，在對寄存器連續進行寫入操作并且重疊執行時，隻會實際使用最後一個操作更新寄存器。在發射指令時，會将待用操作數的寄存器說明符更名，改為保留站的名字，這就實作了寄存器重命名功能。
公共資料總線(common data bus，簡稱CDB)：CDB将操作數從保留站中傳遞給所有需要它的功能單元，而不需要經過寄存器，加快了指令的執行。
上圖是一些指令在執行過程中的某一個時刻的情況，其中最上面的兩條指令是在動态排程情況下的執行情況，它們分别指向在推測情況下的執行情況，可以看出，在動态排程下，因為亂序執行，這兩個指令已經執行結束并寫入寄存器了。而在推測下同樣的指令已經完成了執行，但由于這兩條指令之前的MUL.D指令還未完成指令送出，是以這兩條指令也不允許完成指令送出。
這一差別意味着具有ROB的處理器可以在維持精确異常的同時動态執行代碼。
多發射處理器的目标就是允許在一個時鐘周期中發射多條指令，分為以下三類：
- 靜态排程超标量處理器
- 動态排程超标量處理器
- VLIW(超長指令字)處理器
它們的差別在于，靜态排程采用循序(也就是順序)執行，動态排程采用亂序執行，它們在每個周期發射的指令數是可變的，而VLIW處理器每個時鐘周期發射固定數目的指令。
上圖是一個簡單的循環例子，在不使用任何技術的情況下，執行一次循環并得到一個結果需要9個周期。
上圖代碼使用了循環展開和靜态排程技術，得到一個結果需要3.5個周期。
上圖代碼使用了循環展開、靜态排程和VLIW技術，得到一個結果需要1.29個周期。
上圖對幾種不同處理器所使用的技術和各自的應用進行了總結。