一、CPU指令的執(zhí)行過程

幾乎所有的馮·諾伊曼型計算機的 CPU，其工作都可以分為 5 個階段：取指令、指令譯碼、執(zhí)行指令、訪存取數(shù)、結果寫回。

?

1．取指令階段

取指令（Instruction Fetch，IF）階段是將一條指令從主存中取到指令寄存器的過程。 程序計數(shù)器 PC 中的數(shù)值，用來指示當前指令在主存中的位置。當一條指令被取出后，PC 中的數(shù)值將根據(jù)指令字長度而自動遞增：若為單字長指令，則(PC)+1->PC；若為雙字長指令，則(PC)+2->PC，依此類推。

2．指令譯碼階段

取出指令后，計算機立即進入指令譯碼（Instruction Decode，ID）階段。 在指令譯碼階段，指令譯碼器按照預定的指令格式，對取回的指令進行拆分和解釋，識別區(qū)分出不同的指令類別以及各種獲取操作數(shù)的方法。在組合邏輯控制的計算機中，指令譯碼器對不同的指令操作碼產生不同的控制電位，以形成不同的微操作序列；在微程序控制的計算機中，指令譯碼器用指令操作碼來找到執(zhí)行該指令的微程序的入口，并從此入口開始執(zhí)行。 在傳統(tǒng)的設計里，CPU中負責指令譯碼的部分是無法改變的。不過，在眾多運用微程序控制技術的新型 CPU 中，微程序有時是可重寫的。

3．執(zhí)行指令階段

在取指令和指令譯碼階段之后，接著進入執(zhí)行指令（Execute，EX）階段。 此階段的任務是完成指令所規(guī)定的各種操作，具體實現(xiàn)指令的功能。為此，CPU 的不同部分被連接起來，以執(zhí)行所需的操作。 例如，如果要求完成一個加法運算，算術邏輯單元 ALU 將被連接到一組輸入和一組輸出，輸入端提供需要相加的數(shù)值，輸出端將含有最后的運算結果。

4．訪存取數(shù)階段

根據(jù)指令需要，有可能要訪問主存，讀取操作數(shù)，這樣就進入了訪存取數(shù)（Memory，MEM）階段。 此階段的任務是：根據(jù)指令地址碼，得到操作數(shù)在主存中的地址，并從主存中讀取該操作數(shù)用于運算。

5．結果寫回階段

作為最后一個階段，結果寫回（Writeback，WB）階段把執(zhí)行指令階段的運行結果數(shù)據(jù)“寫回”到某種存儲形式：結果數(shù)據(jù)經常被寫到 CPU 的內部寄存器中，以便被后續(xù)的指令快速地存??；在有些情況下， 結果數(shù)據(jù)也可被寫入相對較慢、但較廉價且容量較大的主存。許多指令還會改變程序狀態(tài)字寄存器中標志位 的狀態(tài)，這些標志位標識著不同的操作結果，可被用來影響程序的動作。

在指令執(zhí)行完畢、結果數(shù)據(jù)寫回之后，若無意外事件（如結果溢出等）發(fā)生，計算機就接著從程序計數(shù)器 PC 中取得下一條指令地址，開始新一輪的循環(huán)，下一個指令周期將順序取出下一條指令。許多新型 CPU 可以同時取出、譯碼和執(zhí)行多條指令，體現(xiàn)并行處理的特性。

二、CPU指令流水線

在任一條指令的執(zhí)行過程中，各個功能部件都會隨著指令執(zhí)行的進程而呈現(xiàn)出時忙時閑的現(xiàn)象。要加快計算機的工作速度，就應使各個功能部件并行工作，即以各自可能的高速度同時、不停地工作，使得各部件的操作在時間上重疊進行，實現(xiàn)流水式作業(yè)。 從原理上說，計算機的流水線（Pipeline）工作方式就是將一個計算任務細分成若干個子任務，每個子任務都由專門的功能部件進行處理，一個計算任務的各個子任務由流水線上各個功能部件輪流進行處理 （即各子任務在流水線的各個功能階段并發(fā)執(zhí)行），最終完成工作。這樣，不必等到上一個計算任務完成， 就可以開始下一個計算任務的執(zhí)行。 流水線的硬件基本結構如圖2所示。流水線由一系列串聯(lián)的功能部件（Si）組成，各個功能部件之間設有高速緩沖寄存器（L），以暫時保存上一功能部件對子任務處理的結果，同時又能夠接受新的處理任務。在一個統(tǒng)一的時鐘（C）控制下，計算任務從功能部件的一個功能段流向下一個功能段。在流水線中， 所有功能段同時對不同的數(shù)據(jù)進行不同的處理，各個處理步驟并行地操作。

圖2 流水線的硬件基本結構?

?

當任務連續(xù)不斷地輸入流水線時，在流水線的輸出端便連續(xù)不斷地輸出執(zhí)行結果，流水線達到不間斷流水的穩(wěn)定狀態(tài)，從而實現(xiàn)了子任務級的并行。

當指令流不能順序執(zhí)行時，流水過程會中斷（即斷流）。為了保證流水過程的工作效率，流水過程不應經常斷流。在一個流水過程中，實現(xiàn)各個子過程的各個功能段所需要的時間應該盡可能保持相等，以避免產生瓶頸，導致流水線斷流。

流水線技術本質上是將一個重復的時序過程分解成若干個子過程，而每一個子過程都可有效地在其專用功能段上與其他子過程同時執(zhí)行。采用流水線技術通過硬件實現(xiàn)并行操作后，就某一條指令而言，其執(zhí)行速度并沒有加快，但就程序執(zhí)行過程的整體而言，程序執(zhí)行速度大大加快。

流水線技術適合于大量的重復性的處理。

前面我提到過CPU 中一個指令周期的任務分解。假設指令周期包含取指令（IF）、指令譯碼（ID）、 指令執(zhí)行（EX）、訪存取數(shù)（MEM）、結果寫回（WB）5 個子過程（過程段），流水線由這 5個串聯(lián)的過程段 組成，各個過程段之間設有高速緩沖寄存器，以暫時保存上一過程段子任務處理的結果，在統(tǒng)一的時鐘信號控制下，數(shù)據(jù)從一個過程段流向相鄰的過程段。

非流水計算機的時空圖如下:

?圖3 非流水計算機時空圖

?

對于非流水計算機而言，上一條指令的 5 個子過程全部執(zhí)行完畢后才能開始下一條指令，每隔 5 個時 鐘周期才有一個輸出結果。因此，圖3中用了 15 個時鐘周期才完成 3 條指令，每條指令平均用時 5 個時鐘周期。 非流水線工作方式的控制比較簡單，但部件的利用率較低，系統(tǒng)工作速度較慢。

標量流水計算機工作方式

標量（Scalar）流水計算機是只有一條指令流水線的計算機。圖 4表示標量流水計算機的時空圖。

?圖4 標量流水計算機時空圖

?

對標量流水計算機而言，上一條指令與下一條指令的 5 個子過程在時間上可以重疊執(zhí)行，當流水線滿 載時，每一個時鐘周期就可以輸出一個結果。因此，圖4中僅用了 9 個時鐘周期就完成了 5 條指令，每條指令平均用時 1.8 個時鐘周期。

采用標量流水線工作方式，雖然每條指令的執(zhí)行時間并未縮短，但 CPU 運行指令的總體速度卻能成倍 提高。當然，作為速度提高的代價，需要增加部分硬件才能實現(xiàn)標量流水。

超標量流水計算機工作方式

一般的流水計算機因只有一條指令流水線，所以稱為標量流水計算機。所謂超標量（Superscalar）流 水計算機，是指它具有兩條以上的指令流水線。圖 5表示超標量流水計算機的時空圖。

圖5 超標量流水計算機時空圖?

?

當流水線滿載時，每一個時鐘周期可以執(zhí)行 2 條以上的指令。因此，圖5中僅用了 9 個時鐘周期就完成了 10 條指令，每條指令平均用時 0.9 個時鐘周期。 超標量流水計算機是時間并行技術和空間并行技術的綜合應用。

三、指令的相關性

指令流水線的一個特點是流水線中的各條指令之間存在一些相關性，使得指令的執(zhí)行受到影響。要使流水線發(fā)揮高效率，就要使流水線連續(xù)不斷地流動，盡量不出現(xiàn)斷流情況。然而，由于流水過程中存在的相關性沖突，斷流現(xiàn)象是不可避免的。

1．數(shù)據(jù)相關

在流水計算機中，指令的處理是重疊進行的，前一條指令還沒有結束，第二、三條指令就陸續(xù)開始工 作。由于多條指令的重疊處理，當后繼指令所需的操作數(shù)剛好是前一指令的運算結果時，便發(fā)生數(shù)據(jù)相關沖突。由于這兩條指令的執(zhí)行順序直接影響到操作數(shù)讀取的內容，必須等前一條指令執(zhí)行完畢后才能執(zhí)行后一條指令。在這種情況下，這兩條指令就是數(shù)據(jù)相關的。因此，數(shù)據(jù)相關是由于指令之間存在數(shù)據(jù)依賴性而引起的。根據(jù)指令間對同一寄存器讀和寫操作的先后次序關系，可將數(shù)據(jù)相關性分為寫后讀（Read-AfterWrite，RAW）相關、讀后寫（Write-After-Read，WAR）相關、寫后寫（Write-After-Write，WAW）相關三種類型。

解決數(shù)據(jù)相關沖突的辦法如下：

采用編譯的方法 編譯程序通過在兩條相關指令之間插入其他不相關的指令（或空操作指令）而推遲指令的執(zhí)行，使數(shù)據(jù)相關消失，從而產生沒有相關性的程序代碼。這種方式簡單，但降低了運行效率。

由硬件監(jiān)測相關性的存在，采用數(shù)據(jù)旁路技術設法解決數(shù)據(jù)相關 當前一條指令要寫入寄存器而下一條指令要讀取同一個寄存器時，在前一條指令執(zhí)行完畢、結果數(shù)據(jù)還未寫入寄存器前，由內部數(shù)據(jù)通路把該結果數(shù)據(jù)直接傳遞給下一條指令，也就是說，下一條指令所需的 操作數(shù)不再通過讀取寄存器獲得，而是直接獲取。這種方式效率較高，但控制較為復雜。

2．資源相關

所謂資源相關，是指多條指令進入流水線后在同一機器周期內爭用同一個功能部件所發(fā)生的沖突。 例如，在圖 4所示的標量流水計算機中，在第 4 個時鐘周期時，第 1 條指令處于訪存取數(shù)（MEM） 階段，而第 4 條指令處于取指令（IF）階段。如果數(shù)據(jù)和指令存放在同一存儲器中，且存儲器只有一個端口，這樣便會發(fā)生這兩條指令爭用存儲器的資源相關沖突。 因為每一條指令都可能需要 2 次訪問存儲器（讀指令和讀寫數(shù)據(jù)），在指令流水過程中，可能會有 2 條指令同時需要訪問存儲器，導致資源相關沖突解決資源相關沖突的一般辦法是增加資源，例如增設一個存儲器，將指令和數(shù)據(jù)分別放在兩個存儲器中。

3．控制相關

控制相關沖突是由轉移指令引起的。當執(zhí)行轉移指令時，依據(jù)轉移條件的產生結果，可能順序取下一 條指令，也可能轉移到新的目標地址取指令。若轉移到新的目標地址取指令，則指令流水線將被排空，并等待轉移指令形成下一條指令的地址，以便讀取新的指令，這就使得流水線發(fā)生斷流。 為了減小轉移指令對流水線性能的影響，通常采用以下兩種轉移處理技術：

延遲轉移法 由編譯程序重排指令序列來實現(xiàn)。其基本思想是“先執(zhí)行再轉移”，即發(fā)生轉移時并不排空指令流水線，而是繼續(xù)完成下幾條指令。如果這些后繼指令是與該轉移指令結果無關的有用指令，那么延遲損失時間片正好得到了有效的利用。

轉移預測法 用硬件方法來實現(xiàn)。依據(jù)指令過去的行為來預測將來的行為，即選擇出現(xiàn)概率較高的分支進行預取。通過使用轉移取和順序取兩路指令預取隊列以及目標指令 Cache，可將轉移預測提前到取指令階段進行，以獲得良好的效果。

四、指令的動態(tài)執(zhí)行技術

1．指令調度

為了減少指令相關性對執(zhí)行速度的影響，可以在保證程序正確性的前提下，調整指令的順序，即進行指令調度。 指令調度可以由編譯程序進行，也可以由硬件在執(zhí)行的時候進行，分別稱為靜態(tài)指令調度和動態(tài)指令調度。靜態(tài)指令調度是指編譯程序通過調整指令的順序來減少流水線的停頓，提高程序的執(zhí)行速度；動態(tài) 指令調度用硬件方法調度指令的執(zhí)行以減少流水線停頓。

流水線中一直采用的有序（in-order）指令啟動是限制流水線性能的主要因素之一。如果有一條指令在流水線中停頓了，則其后的指令就都不能向前流動了，這樣，如果相鄰的兩條指令存在相關性，流水線就將發(fā)生停頓，如果有多個功能部件，這些部件就有可能被閑置。消除這種限制流水線性能的因素從而提高指令執(zhí)行速度，其基本思想就是允許指令的執(zhí)行是無序的（out-of-order，也稱亂序），也就是說，在保持指令間、數(shù)據(jù)間的依賴關系的前提下，允許不相關的指令的執(zhí)行順序與程序的原有順序有所不同，這一思想是實行動態(tài)指令調度的前提。

2．亂序執(zhí)行技術

亂序執(zhí)行（Out-of-order Execution）是以亂序方式執(zhí)行指令，即 CPU 允許將多條指令不按程序規(guī)定的順序而分開發(fā)送給各相應電路單元進行處理。這樣，根據(jù)各個電路單元的狀態(tài)和各指令能否提前執(zhí)行的具體情況分析，將能夠提前執(zhí)行的指令立即發(fā)送給相應電路單元予以執(zhí)行，在這期間不按規(guī)定順序執(zhí)行指令；然后由重新排列單元將各執(zhí)行單元結果按指令順序重新排列。亂序執(zhí)行的目的，就是為了使 CPU 內部電路滿負荷運轉，并相應提高 CPU 運行程序的速度。

實現(xiàn)亂序執(zhí)行的關鍵在于取消傳統(tǒng)的“取指”和“執(zhí)行”兩個階段之間指令需要線性排列的限制，而使用一個指令緩沖池來開辟一個較長的指令窗口，允許執(zhí)行單元在一個較大的范圍內調遣和執(zhí)行已譯碼的程序指令流。

3．分支預測

分支預測（Branch Prediction）是對程序的流程進行預測，然后讀取其中一個分支的指令。采用分支預測的主要目的是為了提高 CPU的運算速度。 分支預測的方法有靜態(tài)預測和動態(tài)預測兩類：靜態(tài)預測方法比較簡單，如預測永遠不轉移、預測永遠轉移、預測后向轉移等等，它并不根據(jù)執(zhí)行時的條件和歷史信息來進行預測，因此預測的準確性不可能很高；動態(tài)預測方法則根據(jù)同一條轉移指令過去的轉移情況來預測未來的轉移情況。 由于程序中的條件分支是根據(jù)程序指令在流水線處理后的結果來執(zhí)行的，所以當 CPU 等待指令結果時， 流水線的前級電路也處于等待分支指令的空閑狀態(tài)，這樣必然出現(xiàn)時鐘周期的浪費。如果 CPU 能在前條指令結果出來之前就預測到分支是否轉移，那么就可以提前執(zhí)行相應的指令，這樣就避免了流水線的空閑等待，也就相應提高了 CPU 的運算速度。但另一方面，一旦前條指令結果出來后證明分支預測是錯誤的，那么就必須將已經裝入流水線執(zhí)行的指令和結果全部清除，然后再裝入正確的指令重新處理，這樣就比不進行分支預測而是等待結果再執(zhí)行新指令還要慢了。

因此，分支預測的錯誤并不會導致結果的錯誤，而只是導致流水線的停頓，如果能夠保持較高的預測 準確率，分支預測就能提高流水線的性能。

五、實例分析

前面的知識只是一個理論基礎鋪墊，下面我們就結合一款真實的CPU架構進行對應分析，圖6和圖7分別是x86和ARM體系結構的內核架構圖（都是具有OoOE特性的CPU架構），可以看到他們基本的組成都是一樣的（雖然x86是CISC而ARM是RISC，但是現(xiàn)代x86內部也是先把CISC翻譯成RISC的），因此我在這里就只分析x86結構。

圖6 intel Nehalem內核架構圖?

?

圖7 ARM Cortex-A57內核架構圖?

?

1．取指令階段（IF）

處理器在執(zhí)行指令之前，必須先裝載指令。指令會先保存在 L1 緩存的 I-cache (Instruction-cache)指令緩存當中，Nehalem 的指令拾取單元使用 128bit 帶寬的通道從 I-cache 中讀取指令。這個 I-cache 的大小為 32KB，采用了 4 路組相連，在后面的存取單元介紹中我們可以得知這種比 Core 更少的集合關聯(lián)數(shù)量是為了降低延遲。

為了適應超線程技術，RIP(Relative Instruction Point，相對指令指針)的數(shù)量也從一個增加到了兩個，每個線程單獨使用一個。

?

指令拾取單元包含了分支預測器(Branch Predictor)，分支預測是在 Pentium Pro 處理器開始加入的功能，預測如 if then 這樣的語句的將來走向，提前讀取相關的指令并執(zhí)行的技術，可以明顯地提升性能。指令拾取單元也包含了 Hardware Prefetcher，根據(jù)歷史操作預先加載以后會用到的指令來提高性能，這會在后面得到詳細的介紹。

?

當分支預測器決定了走向一個分支之后，它使用 BTB(Branch Target Buffer，分支目標緩沖區(qū))來保存預測指令的地址。Nehalem 從以前的一級 BTB 升級到了兩個級別，這是為了適應很大體積的程序(數(shù)據(jù)庫以及 ERP 等應用，跳轉分支將會跨過很大的區(qū)域并具有很多的分支)。Intel 并沒有提及 BTB 詳細的結構。與BTB 相對的 RSB(Return Stack Buffer，返回堆棧緩沖區(qū))也得到了提升，RSB 用來保存一個函數(shù)或功能調用結束之后的返回地址，通過重命名的 RSB 來避免多次推測路徑導致的入口/出口破壞。RSB 每個線程都有一個，一個核心就擁有兩個，以適應超線程技術的存在。

?

指令拾取單元使用預測指令的地址來拾取指令，它通過訪問 L1 ITLB 里的索引來繼續(xù)訪問 L1 ICache，128 條目的小頁面 L1 ITLB 按照兩個線程靜態(tài)分區(qū)，每個線程可以獲得 64 個條目，這個數(shù)目比 Core 2 的少。當關閉超線程時，單獨的線程將可以獲得全部的 TLB 資 源。除了小頁面 TLB 之外，Nehalem 還每個線程擁有 7 個條目的全關聯(lián)(Full Associativity) 大頁面 ITLB，這些 TLB 用于訪問 2M/4M 的大容量頁面，每個線程獨立，因此關閉超線程不會讓你得到 14 個大頁面 ITLB 條目。

?

指令拾取單元通過 128bit 的總線將指令從 L1 ICache 拾取到一個 16Bytes(剛好就是 128bit)的預解碼拾取緩沖區(qū)。128 位的帶寬讓人有些迷惑不解，Opteron 一早就已經使用 了 256bit 的指令拾取帶寬。最重要的是，L1D 和 L1I 都是通過 256bit 的帶寬連接到 L2 Cache 的。

由于一般的CISC x86指令都小于4Bytes（32位x86指令;x86指令的特點就是不等長)， 因此一次可以拾取 4 條以上的指令，而預解碼拾取緩沖區(qū)的輸出帶寬是 6 指令每時鐘周期， 因此可以看出指令拾取帶寬確實有些不協(xié)調，特別是考慮到 64 位應用下指令會長一些的情 況下(解碼器的輸入輸出能力是 4 指令每時鐘周期，因此 32 位下問題不大)。

指令拾取結束后會送到 18 個條目的指令隊列，在 Core 架構，送到的是 LSD 循環(huán)流緩沖區(qū)，在后面可以看到，Nehalem 通過將 LSD 移動后更靠后的位置來提高性能。

2．指令譯碼階段（ID）

在將指令充填到可容納 18 條目的指令隊列之后，就可以進行解碼工作了。解碼是類 RISC (精簡指令集或簡單指令集)處理器導致的一項設計，從 Pentium Pro 開始在 IA 架構出現(xiàn)。 處理器接受的是 x86 指令(CISC 指令，復雜指令集)，而在執(zhí)行引擎內部執(zhí)行的卻不是x86 指令，而是一條一條的類 RISC 指令，Intel 稱之為 Micro Operation——micro-op，或者寫 為 μ-op，一般用比較方便的寫法來替代掉希臘字母:u-op 或者 uop。相對地，一條一條的 x86 指令就稱之為 Macro Operation或 macro-op。

RISC 架構的特點就是指令長度相等，執(zhí)行時間恒定(通常為一個時鐘周期)，因此處理器設計起來就很簡單，可以通過深長的流水線達到很高的頻率，IBM 的 Power6 就可以輕松地達到 4.7GHz 的起步頻率。和 RISC 相反，CISC 指令的長度不固定，執(zhí)行時間也不固定，因此 Intel 的 RISC/CISC 混合處理器架構就要通過解碼器 將 x86 指令翻譯為 uop，從而獲得 RISC 架構的長處，提升內部執(zhí)行效率。

和 Core 一樣，Nehalem 的解碼器也是 4 個（3 個簡單解碼器加 1 個復雜解碼器）。簡單解碼器可以將一條 x86 指令(包括大部分 SSE 指令在內)翻譯為一條 uop，而復雜解碼器則將一些特別的(單條)x86 指令翻譯為 1~4 條 uops——在極少數(shù)的情況下，某些指令需要通過 額外的可編程 microcode 解碼器解碼為更多的 uops(有些時候甚至可以達到幾百個，因為 一些 IA 指令很復雜，并且可以帶有很多的前綴/修改量，當然這種情況很少見)，下圖 Complex Decoder 左方的 ucode 方塊就是這個解碼器，這個解碼器可以通過一些途徑進行升級或者擴展，實際上就是通過主板 Firmware 里面的 Microcode ROM 部分。

之所以具有兩種解碼器，是因為仍然是關于 RISC/CISC 的一個事實: 大部分情況下(90%) 的時間內處理器都在運行少數(shù)的指令，其余的時間則運行各式各樣的復雜指令(不幸的是， 復雜就意味著較長的運行時間)，RISC 就是將這些復雜的指令剔除掉，只留下最經常運行的指令(所謂的精簡指令集)，然而被剔除掉的那些指令雖然實現(xiàn)起來比較麻煩，卻在某些領域確實有其價值，RISC 的做法就是將這些麻煩都交給軟件，CISC 的做法則是像現(xiàn)在這樣: 由硬件設計完成。因此 RISC 指令集對編譯器要求很高，而 CISC 則很簡單。對編程人員的要求也類似。

?

3、循環(huán)流檢測

在解碼為 uop 之后 Nehalem 會將它們都存放在一個叫做 uop LSD Buffer 的緩存區(qū)。在Core 2 上，這個 LSD Buffer 是出現(xiàn)在解碼器前方的，Nehalem 將其移動到解碼器后方，并相對加大了緩沖區(qū)的條目。Core 2 的 LSD 緩存區(qū)可以保存 18 個 x86 指令而 Nehalem 可以保 存 28 個 uop，從前文可以知道，大部分 x86 指令都可以解碼為一個 uop，少部分可以解碼 為 1~4 個 uop，因此 Nehalem 的 LSD 緩沖區(qū)基本上可以相當于保存 21~23 條x86 指令，比 Core 2 要大上一些。

?

LSD 循環(huán)流監(jiān)測器也算包含在解碼部分，它的作用是: 假如程序使用的循環(huán)段(如 for..do/do..while 等)少于 28 個 uops，那么 Nehalem 就可以將這個循環(huán)保存起來，不再需要重新通過取指單元、分支預測操作，以及解碼器，Core 2 的 LSD 放在解碼器前方，因此無法省下解碼的工作。

Nehalem LSD 的工作比較像 NetBurst 架構的 Trace Cache，其也是保存 uops，作用也是部分地去掉一些嚴重的循環(huán)，不過由于 Trace Cache 還同時擔當著類似于 Core/Nehalem 架構的 Reorder Buffer 亂序緩沖區(qū)的作用，容量比較大(可以保存 12k uops，準確的大小 是 20KB)，因此在 cache miss 的時候后果嚴重(特別是在 SMT 同步多線程之后，miss 率加 倍的情況下)，LSD 的小數(shù)目設計顯然會好得多。不過筆者認為 28 個 uop 條目有些少，特 別是考慮到 SMT 技術帶來的兩條線程都同時使用這個 LSD 的時候。

在 LSD 之后，Nehalem 將會進行 Micro-ops Fusion，這也是前端(The Front-End)的最后一個功能，在這些工作都做完之后，uops 就可以準備進入執(zhí)行引擎了。

4．亂序執(zhí)行指令階段（OoOE）

OoOE— Out-of-Order Execution 亂序執(zhí)行也是在 Pentium Pro 開始引入的，它有些類似于多線程的概念。亂序執(zhí)行是為了直接提升 ILP(Instruction Level Parallelism)指令級并行化的設計，在多個執(zhí)行單元的超標量設計當中，一系列的執(zhí)行單元可以同時運行一些沒有數(shù)據(jù)關聯(lián)性的若干指令，只有需要等待其他指令運算結果的數(shù)據(jù)會按照順序執(zhí)行，從而總體提升了運行效率。亂序執(zhí)行引擎是一個很重要的部分，需要進行復雜的調度管理。

首先，在亂序執(zhí)行架構中，不同的指令可能都會需要用到相同的通用寄存器(GPR，General Purpose Registers)，特別是在指令需要改寫該通用寄存器的情況下——為了讓這些指令們能并行工作，處理器需要準備解決方法。一般的 RISC 架構準備了大量的GPR， 而x86 架構天生就缺乏 GPR(x86具有8個GPR，x86-64 具有 16 個，一般 RISC 具有 32 個，IA64 則具有 128 個)，為此 Intel 開始引入重命名寄存器(Rename Register)，不同的指令可以通過具有名字相同但實際不同的寄存器來解決。

此外，為了 SMT 同步多線程，這些寄存器還要準備雙份，每個線程具有獨立的一份。

?

亂序執(zhí)行從Allocator定位器開始，Allocator 管理著RAT(Register Alias Table，寄存器別名表)、ROB(Re-Order Buffer，重排序緩沖區(qū))和 RRF(Retirement Register File，退回寄存器文件)。在 Allocator 之前，流水線都是順序執(zhí)行的，在 Allocator 之后，就可以進入亂序執(zhí)行階段了。在每一個線程方面，Nehalem 和 Core 2 架構相似，RAT 將重命名的、虛擬的寄存器(稱為 Architectural Register 或 Logical Register)指向ROB 或者RRF。RAT 是一式兩份,每個線程獨立，每個 RAT 包含了 128 個重命名寄存器。RAT 指向在 ROB 里面的最近的執(zhí)行寄存器狀態(tài)，或者指向RRF保存的最終的提交狀態(tài)。

ROB(Re-Order Buffer，重排序緩沖區(qū))是一個非常重要的部件，它是將亂序執(zhí)行完畢的指令們按照程序編程的原始順序重新排序的一個隊列，以保證所有的指令都能夠邏輯上實現(xiàn)正確的因果關系。打亂了次序的指令們(分支預測、硬件預取)依次插入這個隊列，當一條指令通過 RAT 發(fā)往下一個階段確實執(zhí)行的時候這條指令(包括寄存器狀態(tài)在內)將被加入 ROB 隊列的一端，執(zhí)行完畢的指令(包括寄存器狀態(tài))將從 ROB 隊列的另一端移除(期間這些指令的數(shù)據(jù)可以被一些中間計算結果刷新)，因為調度器是 In-Order 順序的，這個隊列（ROB）也就是順序的。從 ROB 中移出一條指令就意味著指令執(zhí)行完畢了，這個階段叫做 Retire 回退，相應地 ROB 往往也叫做 Retirement Unit(回退單元)，并將其畫為流水線的最后一部分。

在一些超標量設計中，Retire 階段會將 ROB 的數(shù)據(jù)寫入 L1D 緩存（這是將MOB集成到ROB的情況），而在另一些設計里， 寫入 L1D 緩存由另外的隊列完成。例如，Core/Nehalem 的這個操作就由 MOB(Memory Order Buffer，內存重排序緩沖區(qū))來完成。

ROB 是亂序執(zhí)行引擎架構中都存在的一個緩沖區(qū)，重新排序指令的目的是將指令們的寄存器狀態(tài)依次提交到RRF退回寄存器文件當中，以確保具有因果關系的指令們在亂序執(zhí)行中可以得到正確的數(shù)據(jù)。從執(zhí)行單元返回的數(shù)據(jù)會將先前由調度器加入ROB 的指令刷新數(shù)據(jù)部分并標志為結束(Finished)，再經過其他檢查通過后才能標志為完畢(Complete)，一旦標志為完畢，它就可以提交數(shù)據(jù)并刪除重命名項目并退出ROB 了。提交狀態(tài)的工作由 Retirement Unit(回退單元)完成，它將確實完畢的指令包含的數(shù)據(jù)寫入RRF(“確實” 的意思是，非猜測執(zhí)性、具備正確因果關系，程序可以見到的最終的寄存器狀態(tài))。和 RAT 一樣，RRF 也同時具有兩個，每個線程獨立。Core/Nehalem 的 Retirement Unit 回退單元每時鐘周期可以執(zhí)行 4 個 uops 的寄存器文件寫入，和 RAT 每時鐘 4 個 uops 的重命名一致。

由于 ROB 里面保存的指令數(shù)目是如此之大(128 條目)，因此一些人認為它的作用是用來從中挑選出不相關的指令來進入執(zhí)行單元，這多少是受到一些文檔中的 Out-of-Order Window 亂序窗口這個詞的影響(后面會看到ROB 會和 MOB 一起被計入亂序窗口資源中)。

ROB 確實具有 RS 的一部分相似的作用，不過，ROB 里面的指令是調度器（dispacher）通過 RAT發(fā)往 RS 的同時發(fā)往ROB的（里面包含著正常順序的指令和猜測執(zhí)行的指令，但是亂序執(zhí)行并不是從ROB中亂序挑選的），也就是說，在“亂序”之前，ROB 的指令就已經確定了。指令并不是在 ROB 當中亂序挑選的(這是在RS當中進行)，ROB 擔當?shù)氖橇魉€的最終階段: 一個指令的 Retire回退單元;以及擔當中間計算結果的緩沖區(qū)。 RS(Reservation Station，中繼站): 等待源數(shù)據(jù)到來以進行OoOE亂序執(zhí)行(沒有數(shù)據(jù)的指令將在 RS 等待)， ROB(ReOrder Buffer，重排序緩沖區(qū)): 等待結果到達以進行 Retire 指令回退 (沒有結果的指令將在 ROB等待)。

Nehalem 的 128 條目的 ROB 擔當中間計算結果的緩沖區(qū)，它保存著猜測執(zhí)行的指令及其數(shù)據(jù)，猜測執(zhí)行允許預先執(zhí)行方向未定的分支指令。在大部分情況下，猜測執(zhí)行工作良好——分支猜對了，因此其在 ROB 里產生的結果被標志為已結束，可以立即地被后繼指令使用而不需要進行 L1 Data Cache 的 Load 操作(這也是 ROB 的另一個重要用處，典型的 x86 應用中 Load 操作是如此頻繁，達到了幾乎占 1/3 的地步，因此 ROB 可以避免大量的Cache Load 操作，作用巨大)。在剩下的不幸的情況下，分支未能按照如期的情況進行，這時猜測的分支指令段將被清除，相應指令們的流水線階段清空，對應的寄存器狀態(tài)也就全都無效了，這種無效的寄存器狀態(tài)不會也不能出現(xiàn)在 RRF 里面。

重命名技術并不是沒有代價的，在獲得前面所說的眾多的優(yōu)點之后，它令指令在發(fā)射的時候需要掃描額外的地方來尋找到正確的寄存器狀態(tài)，不過總體來說這種代價是非常值得的。RAT可以在每一個時鐘周期重命名 4 個 uops 的寄存器，經過重命名的指令在讀取到正確的操作數(shù)并發(fā)射到統(tǒng)一的RS(Reservation Station，中繼站，Intel 文檔翻譯為保留站點) 上。RS 中繼站保存了所有等待執(zhí)行的指令。

和 Core 2 相比，Nehalem 的 ROB 大小和 RS 大小都得到了提升，ROB 重排序緩沖區(qū)從 96 條目提升到 128 條目(鼻祖 Pentium Pro 具有 40 條)，RS 中繼站從 32 提升到 36(Pentium Pro 為 20)，它們都在兩個線程(超線程中的線程)內共享，不過采用了不同的策略:ROB 是采用了靜態(tài)的分區(qū)方法，而 RS 則采用了動態(tài)共享，因為有時候會有一條線程內的指令因 等待數(shù)據(jù)而停滯，這時另一個線程就可以獲得更多的 RS 資源。停滯的指令不會發(fā)往 RS，但是仍然會占用 ROB 條目。由于 ROB 是靜態(tài)分區(qū)，因此在開啟 HTT 的情況下，每一個線程只能 分到 64 條，不算多，在一些極少數(shù)的應用上，我們應該可以觀察到一些應用開啟 HTT 后會 速度降低，盡管可能非常微小。

5、執(zhí)行單元

在為 SMT 做好準備工作并打亂指令的執(zhí)行順序之后（指的是分支預測、硬件預?。瑄ops 通過每時鐘周期 4 條的速度進入 Reservation Station 中繼站(保留站)，總共 36 條目的中繼站 uops 就開始等待超標量(Superscaler)執(zhí)行引擎亂序執(zhí)行了。自從 Pentium 開始，Intel 就開始在處理器里面采用了超標量設計(Pentium 是兩路超標量處理器)，超標量的意思就是多個執(zhí)行單元，它可以同時執(zhí)行多條沒有相互依賴性的指令，從而達到提升 ILP 指令級并行化的目的。Nehalem 具備 6 個執(zhí)行端口，每個執(zhí)行端口具有多個不同的單元以執(zhí)行不同的任務，然而同一時間只能有一條指令(uop)進入執(zhí)行端口，因此也可以認為 Nehalem 有 6 個“執(zhí)行單元”，在每個時鐘周期內可以執(zhí)行最多 6 個操作(或者說，6 條指令)，和 Core 一樣。

?

36 條目的中繼站指令在分發(fā)器的管理下，挑選出盡量多的可以同時執(zhí)行的指令(也就是亂序執(zhí)行的意思)——最多 6 條——發(fā)送到執(zhí)行端口。 這些執(zhí)行端口并不都是用于計算，實際上，有三個執(zhí)行端口是專門用來執(zhí)行內存相關的操作的，只有剩下的三個是計算端口，因此，在這一點上 Nehalem 實際上是跟 Core 架構一 樣的，這也可以解釋為什么有些情況下，Nehalem 和 Core 相比沒有什么性能提升。

計算操作分為兩種: 使用 ALU(Arithmetic Logic Unit，算術邏輯單元)的整數(shù)(Integer) 運算和使用 FPU(Floating Point Unit，浮點運算單元)的浮點(Floating Point)運算。SSE 指令(包括 SSE1 到 SSE4)是一種特例，它雖然有整數(shù)也有浮點，然而它們使用的都是 128bit 浮點寄存器，使用的也大部分是 FPU 電路。在 Nehalem 中，三個計算端口都可以做整數(shù)運算(包括 MMX)或者SSE 運算(浮點運算不太一樣，只有兩個端口可以進行浮點 ADD 和 MUL/DIV 運算，因此每時鐘周期最多進行 2 個浮點計算，這也是目前 Intel 處理器浮點性能不如整數(shù)性能突出的原因)，不過每一個執(zhí)行端口都不是完全一致:只有端口 0 有浮點乘和除功能，只有端口 5 有分支能力(這個執(zhí)行單元將會與分支預測單元連接)，其他 FP/SSE 能力也不盡相同，這些不對稱之處都由統(tǒng)一的分發(fā)器來理解，并進行指令的調度管理。沒有采用完全對稱的設計可能是基于統(tǒng)計學上的考慮。和 Core 一樣，Nehalem 的也沒有采用 Pentium 4 那樣的 2 倍頻的 ALU 設計(在 Pentium 4，ALU 的運算頻率是 CPU 主頻的兩倍， 因此整數(shù)性能明顯要比浮點性能突出)。

不幸的是，雖然可以同時執(zhí)行的指令很多，然而在流水線架構當中運行速度并不是由最 “寬”的單元來決定的，而是由最“窄”的單元來決定的。這就是木桶原理，Opteron的解碼器后端只能每時鐘周期輸出 3 條 uops，而 Nehalem/Core2 則能輸出 4 條，因此它們的實際最大每時鐘運行指令數(shù)是 3/4，而不是 6。同樣地，多少路超標量在這些亂序架構處理器中也不再按照運算單元來劃分，Core Duo 及之前(到 Pentium Pro 為止)均為三路超標量處理器，Core 2/Nehalem 則為四路超標量處理器。可見在微架構上，Nehalem/Core 顯然是 要比其他處理器快一些。順便說一下，這也是 Intel 在超線程示意圖中，使用 4 個寬度的方 塊來表示而不是 6 個方塊的原因。

6、存取單元

運算需要用到數(shù)據(jù)，也會生成數(shù)據(jù)，這些數(shù)據(jù)存取操作就是存取單元所做的事情，實際 上，Nehalem 和 Core 的存取單元沒什么變化，仍然是 3 個。

這三個存取單元中，一個用于所有的 Load 操作(地址和數(shù)據(jù))，一個用于 Store 地址，一個用于 Store 數(shù)據(jù)，前兩個數(shù)據(jù)相關的單元帶有 AGU(Address Generation Unit，地址生成單元)功能(NetBurst架構使用快速 ALU 來進行地址生成)。

?

在亂序架構中，存取操作也可以打亂進行。類似于指令預取一樣，Load/Store 操作也可以提前進行以降低延遲的影響，提高性能。然而，由于Store操作會修改數(shù)據(jù)影響后繼的Load 操作，而指令卻不會有這種問題(寄存器依賴性問題通過ROB解決)，因此數(shù)據(jù)的亂序操作更為復雜。

?

如上圖所示，第一條 ALU 指令的運算結果要 Store 在地址 Y(第二條指令)，而第九條 指令是從地址 Y Load 數(shù)據(jù)，顯然在第二條指令執(zhí)行完畢之前，無法移動第九條指令，否則將會產生錯誤的結果。同樣，如果CPU也不知道第五條指令會使用什么地址，所以它也無法確定是否可以把第九條指令移動到第五條指令附近。

?

內存數(shù)據(jù)相依性預測功能(Memory Disambiguation)可以預測哪些指令是具有依賴性的或者使用相關的地址(地址混淆，Alias)，從而決定哪些 Load/Store 指令是可以提前的， 哪些是不可以提前的?？梢蕴崆暗闹噶钤谄浜罄^指令需要數(shù)據(jù)之前就開始執(zhí)行、讀取數(shù)據(jù)到ROB當中，這樣后繼指令就可以直接從中使用數(shù)據(jù)，從而避免訪問了無法提前 Load/Store 時訪問 L1 緩存帶來的延遲(3~4 個時鐘周期)。

不過，為了要判斷一個 Load 指令所操作的地址沒有問題，緩存系統(tǒng)需要檢查處于 in-flight 狀態(tài)(處理器流水線中所有未執(zhí)行的指令)的 Store 操作，這是一個頗耗費資源的過程。在 NetBurst 微架構中，通過把一條 Store 指令分解為兩個 uops——一個用于計算地址、一個用于真正的存儲數(shù)據(jù)，這種方式可以提前預知 Store 指令所操作的地址，初步的解決了數(shù)據(jù)相依性問題。在 NetBurst 微架構中，Load/Store 亂序操作的算法遵循以下幾條 原則:

如果一個對于未知地址進行操作的 Store 指令處于 in-flight 狀態(tài)，那么所有的 Load 指令都要被延遲

在操作相同地址的 Store 指令之前 Load 指令不能繼續(xù)執(zhí)行

一個 Store 指令不能移動到另外一個 Store 指令之前（指的是在RS中不能先挑選執(zhí)行后面的一條store指令，注意這只是說某一種架構不允許重排store，其實還是有很多架構如Alpha等是松散內存模型，允許不相關的store重排序的.）

這種原則下的問題也很明顯，比如第一條原則會在一條處于等待狀態(tài)的 Store 指令所操作的地址未確定之前，就延遲所有的 Load 操作，顯然過于保守了。實際上，地址沖突問題是極少發(fā)生的。根據(jù)某些機構的研究，在一個Alpha EV6 處理器中最多可以允許 512 條指令處于 in-flight 狀態(tài)，但是其中的 97%以上的 Load 和 Store 指令都不會存在地址沖突問題。

基于這種理念，Core 微架構采用了大膽的做法，它令 Load 指令總是提前進行，除非新加入的動態(tài)混淆預測器(Dynamic Alias Predictor)預測到了該 Load 指令不能被移動到 Store 指令附近。這個預測是根據(jù)歷史行為來進行的，據(jù)說準確率超過 90%。

在執(zhí)行了預 Load 之后，一個沖突監(jiān)測器會掃描 MOB 的 Store 隊列，檢查該是否有Store操作與該 Load 沖突。在很不幸的情況下(1%~2%)，發(fā)現(xiàn)了沖突，那么該 Load 操作作廢、 流水線清除并重新進行 Load 操作。這樣大約會損失 20 個時鐘周期的時間，然而從整體上看， Core 微架構的激進 Load/Store 亂序策略確實很有效地提升了性能，因為Load 操作占據(jù)了通常程序的 1/3 左右，并且 Load 操作可能會導致巨大的延遲(在命中的情況下，Core 的 L1D Cache 延遲為 3 個時鐘周期，Nehalem 則為 4 個。L1 未命中時則會訪問 L2 緩存，一般為 10~12 個時鐘周期。訪問 L3 通常需要 30~40 個時鐘周期，訪問主內存則可以達到最多約 100 個時鐘周期)。Store 操作并不重要，什么時候寫入到 L1 乃至主內存并不會影響到執(zhí)行性能。

?

如上圖所示，我們需要載入地址 X 的數(shù)據(jù)，加 1 之后保存結果;載入地址 Y 的數(shù)據(jù)，加1 之后保存結果;載入地址 Z 的數(shù)據(jù)，加 1 之后保存結果。如果根據(jù) Netburst 的基本準則， 在第三條指令未決定要存儲在什么地址之前，處理器是不能移動第四條指令和第七條指令的。實際上，它們之間并沒有依賴性。因此，Core 微架構中則“大膽”的將第四條指令和第七條指令分別移動到第二和第三指令的并行位置，這種行為是基于一定的猜測的基礎上的“投機”行為，如果猜測的對的話(幾率在 90%以上)，完成所有的運算只要5個周期，相比之前的9個周期幾乎快了一倍。

和為了順序提交到寄存器而需要 ROB 重排序緩沖區(qū)的存在一樣，在亂序架構中，多個打亂了順序的 Load 操作和Store操作也需要按順序提交到內存，MOB(Memory Reorder Buffer， 內存重排序緩沖區(qū))就是起到這樣一個作用的重排序緩沖區(qū)(介于 Load/Store 單元 與 L1D Cache 之間的部件，有時候也稱之為LSQ)，MOB 通過一個 128bit 位寬的 Load 通道與一個 128bit 位寬的 Store 通道與雙口 L1D Cache 通信。和 ROB 一樣，MOB的內容按照 Load/Store 指令實際的順序加入隊列的一端，按照提交到 L1 DCache 的順序從隊列的另一端移除。ROB 和 MOB 一起實際上形成了一個分布式的 Order Buffer 結構，有些處理器上只存在 ROB，兼?zhèn)淞?MOB 的功能（把MOB看做ROB的一部分可能更好理解）。

和ROB 一樣，Load/Store 單元的亂序存取操作會在 MOB 中按照原始程序順序排列，以提供正確的數(shù)據(jù)，內存數(shù)據(jù)依賴性檢測功能也在里面實現(xiàn)(內存數(shù)據(jù)依賴性的檢測比指令寄存器間的依賴性檢測要復雜的多)。MOB 的 Load/Store 操作結果也會直接反映到 ROB當中（中間結果）。

MOB還附帶了數(shù)據(jù)預取(Data Prefetch)功能，它會猜測未來指令會使用到的數(shù)據(jù)，并預先從L1D Cache 緩存 Load入MOB 中(Data Prefetcher 也會對 L2 至系統(tǒng)內存的數(shù)據(jù)進行這樣的操作)， 這樣 MOB 當中的數(shù)據(jù)有些在 ROB 中是不存在的(這有些像 ROB 當中的 Speculative Execution 猜測執(zhí)行，MOB 當中也存在著“Speculative Load Execution 猜測載入”，只不過失敗的猜測執(zhí)行會導致管線停頓，而失敗的猜測載入僅僅會影響到性能，然而前端時間發(fā)生的Meltdown漏洞卻造成了嚴重的安全問題)。MOB包括了Load Buffers和Store Buffers。

亂序執(zhí)行中我們可以看到很多緩沖區(qū)性質的東西: RAT 寄存器別名表、ROB 重排序緩沖 區(qū)、RS 中繼站、MOB 內存重排序緩沖區(qū)(包括 load buffer 載入緩沖和 store buffer 存儲緩沖)。在超線程的作 用下，RAT是一式兩份，包含了 128 個重命名寄存器; 128 條目的 ROB、48 條目的 LB 和 32 條目的 SB 都 每個線程 64 個 ROB、24 個 LB 和 16 個 SB; RS 則是在兩個線程中動態(tài)共享。可見，雖然整體數(shù)量增加了，然而就單個線程而言，獲得的資源并沒有 提升。這會影響到 HTT 下單線程下的性能。

六、緩存（cache）

通常緩存具有兩種設計:非獨占和獨占，Nehalem 處理器的 L3 采用了非獨占高速緩存 設計(或者說“包含式”，L3 包含了 L1/L2 的內容)，這種方式在 Cache Miss 的時候比獨 占式具有更好的性能，而在緩存命中的時候需要檢查不同的核心的緩存一致性。Nehalem 并 采用了“內核有效”數(shù)據(jù)位的額外設計，降低了這種檢查帶來的性能影響。隨著核心數(shù)目的 逐漸增多(多線程的加入也會增加 Cache Miss 率)，對緩存的壓力也會繼續(xù)增大，因此這 種方式會比較符合未來的趨勢。在后面可以看到，這種設計也是考慮到了多處理器協(xié)作的情況(此時 Miss 率會很容易地增加)。這可以看作是 Nehalem 與以往架構的基礎不同:之前的架構都是來源于移動處理設計，而 Nehalem 則同時為企業(yè)、桌面和移動考慮而設計。

在 L3 緩存命中的時候(單處理器上是最通常的情況，多處理器下則不然)，處理器檢查內核有效位看看是否其他內核也有請求的緩存頁面內容，決定是否需要對內核進行偵聽。

在NUMA架構中，多個處理器中的同一個緩存頁面必定在其中一個處理器中屬于 F 狀態(tài)(可以修改的狀態(tài))，這個頁面在這個處理器中沒有理由不可以多核心共享(可以多核心共享就意味著這個能進入修改狀態(tài)的頁面的多個有效位被設置為一)。MESIF協(xié)議應該是工作在核心(L1+L2)層面而不是處理器(L3)層面，這樣同一處理器里多個核心共享的頁面，只有其中一個是出于 F 狀態(tài)(可以修改的狀態(tài))。見后面對 NUMA 和 MESIF 的解析。(L1/L2/L3 的同步應該是不需要 MESIF 的同步機制)

在 L3 緩存未命中的時候(多處理器下會頻繁發(fā)生)，處理器決定進行內存存取，按照 頁面的物理位置，它分為近端內存存取(本地內存空間)和遠端內存存取(地址在其他處理 器的內存的空間):

七、緩存Cache架構原理

Cache的容量很小，它保存的內容只是主存內容的一個子集，且Cache與主存的數(shù)據(jù)交換是以塊為單位的。為了把信息放到Cache中，必須應用某種函數(shù)把主存地址定位到Cache中，這稱為地址映射。在信息按這種映射關系裝入Cache后，CPU執(zhí)行程序時，會將程序中的主存地址變換成Cache地址，這個變換過程叫做地址變換。

Cache的地址映射方式有直接映射、全相聯(lián)映射和組相聯(lián)映射。假設某臺計算機主存容量為l MB，被分為2048塊，每塊512B；Cache容量為8KB，被分為16塊，每塊也是512B。下面以此為例介紹三種基本的地址映射方法。

直接映射

直接映射的Cache組織如圖3-14所示。主存中的一個塊只能映射到Cache的某一特定塊中去。例如，主存的第0塊、第16塊、……、第2032塊，只能映射到Cache的第0塊；而主存的第1塊、第17塊、……、第2033塊，只能映射到Cache的第1塊……。

?

直接映射是最簡單的地址映射方式，它的硬件簡單，成本低，地址變換速度快，而且不涉及替換算法問題。但是這種方式不夠靈活，Cache的存儲空間得不到充分利用，每個主存塊只有一個固定位置可存放，容易產生沖突，使Cache效率下降，因此只適合大容量Cache采用。例如，如果一個程序需要重復引用主存中第0塊與第16塊，最好將主存第0塊與第16塊同時復制到Cache中，但由于它們都只能復制到Cache的第0塊中去，即使Cache中別的存儲空間空著也不能占用，因此這兩個塊會不斷地交替裝入Cache中，導致命中率降低。

全相聯(lián)映射

圖3-15 是全相聯(lián)映射的Cache組織，主存中任何一塊都可以映射到Cache中的任何一塊位置上。

?

全相聯(lián)映射方式比較靈活，主存的各塊可以映射到Cache的任一塊中，Cache的利用率高，塊沖突概率低，只要淘汰Cache中的某一塊，即可調入主存的任一塊。但是，由于Cache比較電路的設計和實現(xiàn)比較困難，這種方式只適合于小容量Cache采用。

組相聯(lián)映射

組相聯(lián)映射實際上是直接映射和全相聯(lián)映射的折中方案，其組織結構如圖3-16所示。主存和Cache都分組，主存中一個組內的塊數(shù)與Cache中的分組數(shù)相同，組間采用直接映射，組內采用全相聯(lián)映射。也就是說，將Cache分成u組，每組v塊，主存塊存放到哪個組是固定的，至于存到該組哪一塊則是靈活的。例如，主存分為256組，每組8塊，Cache分為8組，每組2塊。

?

主存中的各塊與Cache的組號之間有固定的映射關系，但可自由映射到對應Cache組中的任何一塊。例如，主存中的第0塊、第8塊……均映射于Cache的第0組，但可映射到Cache第0組中的第0塊或第1塊；主存的第1塊、第9塊……均映射于Cache的第1組，但可映射到Cache第1組中的第2塊或第3塊。

常采用的組相聯(lián)結構Cache，每組內有2、4、8、16塊，稱為2路、4路、8路、16路組相聯(lián)Cache。組相聯(lián)結構Cache是前兩種方法的折中方案，適度兼顧二者的優(yōu)點，盡量避免二者的缺點，因而得到普遍采用。

一次內存訪問示意圖

?

?

注意事項

TLB采用組相聯(lián)

頁表采用兩級頁表

cache采用組相聯(lián)

cache僅考慮L1 d-cache，不考慮L1 i-cache、L2 cache和L3 cache

未考慮頁表缺頁

簡化了cache未命中情況

實際例子

下面展示了現(xiàn)代Intel處理器的CPU cache是如何組織的。有關cache的討論往往缺乏具體的實例，使得一些簡單的概念變得撲朔迷離。也許是我可愛的小腦瓜有點遲鈍吧，但不管怎樣，至少下面講述了故事的前一半，即Core 2的 L1 cache是如何被訪問的：

?

L1 cache – 32KB，8路組相聯(lián)，64字節(jié)緩存線

?

?

?

1. 由索引揀選緩存組（行）

在cache中的數(shù)據(jù)是以緩存線（line）為單位組織的，一條緩存線對應于內存中一個連續(xù)的字節(jié)塊。這個cache使用了64字節(jié)的緩存線。這些線被保存在cache bank中，也叫路（way）。每一路都有一個專門的目錄（directory）用來保存一些登記信息。你可以把每一路連同它的目錄想象成電子表格中的一列，而表的一行構成了cache的一組（set）。列中的每一個單元（cell）都含有一條緩存線，由與之對應的目錄單元跟蹤管理。圖中的cache有64 組、每組8路，因此有512個含有緩存線的單元，合計32KB的存儲空間。

在cache眼中，物理內存被分割成了許多4KB大小的物理內存頁（page）。每一頁都含有4kb/64/bytes== 64條緩存線。在一個4KB的頁中，第0到63字節(jié)是第一條緩存線，第64到127字節(jié)是第二條緩存線，以此類推。每一頁都重復著這種劃分，所以第0頁第3條緩存線與第1頁第3條緩存線是不同的。

在全相聯(lián)緩存（fully associative cache）中，內存中的任意一條緩存線都可以被存儲到任意的緩存單元中。這種存儲方式十分靈活，但也使得要訪問它們時，檢索緩存單元的工作變得復雜、昂貴。由于L1和L2 cache工作在很強的約束之下，包括功耗，芯片物理空間，存取速度等，所以在多數(shù)情況下，使用全相聯(lián)緩存并不是一個很好的折中。

取而代之的是圖中的組相聯(lián)緩存（set associative cache）。意思是，內存中一條給定的緩存線只能被保存在一個特定的組（或行）中。所以，任意物理內存頁的第0條緩存線（頁內第0到63字節(jié)）必須存儲到第0組，第1條緩存線存儲到第1組，以此類推。每一組有8個單元可用于存儲它所關聯(lián)的緩存線，從而形成一個8路關聯(lián)的組（8-way associative set）。當訪問一個內存地址時，地址的第6到11位（譯注：組索引）指出了在4KB內存頁中緩存線的編號，從而決定了即將使用的緩存組。舉例來說，物理地址0x800010a0的組索引是000010，所以此地址的內容一定是在第2組中緩存的。

但是還有一個問題，就是要找出一組中哪個單元包含了想要的信息，如果有的話。這就到了緩存目錄登場的時刻。每一個緩存線都被其對應的目錄單元做了標記（tag）；這個標記就是一個簡單的內存頁編號，指出緩存線來自于哪一頁。由于處理器可以尋址64GB的物理RAM，所以總共有64GB/4KB == 224個內存頁，需要24位來保存標記。前例中的物理地址0x800010a0對應的頁號為524289。下面是故事的后一半：

?

2、在組中搜索匹配標記

由于我們只需要去查看某一組中的8路，所以查找匹配標記是非常迅速的；事實上，從電學角度講，所有的標記是同時進行比對的，我用箭頭來表示這一點。如果此時正好有一條具有匹配標簽的有效緩存線，我們就獲得一次緩存命中（cache hit）。否則，這個請求就會被轉發(fā)的L2 cache，如果還沒匹配上就再轉發(fā)給主系統(tǒng)內存。通過應用各種調節(jié)尺寸和容量的技術，Intel給CPU配置了較大的L2 cache，但其基本的設計都是相同的。比如，你可以將原先的緩存增加8路而獲得一個64KB的緩存；再將組數(shù)增加到4096，每路可以存儲256kb。經過這兩次修改，就得到了一個4MB的L2 cache。在此情況下，需要18位來保存標記，12位保存組索引；緩存所使用的物理內存頁的大小與其一路的大小相等。（譯注：有4096組，就需要lg(4096)==12位的組索引，緩存線依然是64字節(jié)，所以一路有4096*64B==256KB字節(jié)；在L2 cache眼中，內存被分割為許多256KB的塊，所以需要lg(64GB/256KB)==18位來保存標記。）

如果有一組已經被放滿了，那么在另一條緩存線被存儲進來之前，已有的某一條則必須被騰空（evict）。為了避免這種情況，對運算速度要求較高的程序就要嘗試仔細組織它的數(shù)據(jù)，使得內存訪問均勻的分布在已有的緩存線上。舉例來說，假設程序中有一個數(shù)組，元素的大小是512字節(jié)，其中一些對象在內存中相距4KB。這些對象的各個字段都落在同一緩存線上，并競爭同一緩存組。如果程序頻繁的訪問一個給定的字段（比如，通過虛函數(shù)表vtable調用虛函數(shù)），那么這個組看起來就好像一直是被填滿的，緩存開始變得毫無意義，因為緩存線一直在重復著騰空與重新載入的步驟。在我們的例子中，由于組數(shù)的限制，L1 cache僅能保存8個這類對象的虛函數(shù)表。這就是組相聯(lián)策略的折中所付出的代價：即使在整體緩存的使用率并不高的情況下，由于組沖突，我們還是會遇到緩存缺失的情況。然而，鑒于計算機中各個存儲層次的相對速度，不管怎么說，大部分的應用程序并不必為此而擔心。

一個內存訪問經常由一個線性（或虛擬）地址發(fā)起，所以L1 cache需要依賴分頁單元（paging unit）來求出物理內存頁的地址，以便用于緩存標記。與此相反，組索引來自于線性地址的低位，所以不需要轉換就可以使用了（在我們的例子中為第6到11位）。因此L1 cache是物理標記但虛擬索引的（physically tagged but virtually indexed），從而幫助CPU進行并行的查找操作。因為L1 cache的一路絕不會比MMU的一頁還大，所以可以保證一個給定的物理地址位置總是關聯(lián)到同一組，即使組索引是虛擬的。在另一方面L2 cache必須是物理標記和物理索引的，因為它的一路比MMU的一頁要大。但是，當一個請求到達L2 cache時，物理地址已經被L1 cache準備（resolved）完畢了，所以L2 cache會工作得很好。

最后，目錄單元還存儲了對應緩存線的狀態(tài)（state）。在L1代碼緩存中的一條緩存線要么是無效的（invalid）要么是共享的（shared，意思是有效的，真的J）。在L1數(shù)據(jù)緩存和L2緩存中，一條緩存線可以為4個MESI狀態(tài)之一：被修改的（modified），獨占的（exclusive），共享的（shared），無效的（invalid）。Intel緩存是包容式的（inclusive）：L1緩存的內容會被復制到L2緩存中。

總結

內存層次結構的意義在于利用引用的空間局部性和時間局部性原理，將經常被訪問的數(shù)據(jù)放到快速的存儲器中，而將不經常訪問的數(shù)據(jù)留在較慢的存儲器中。

一般情況下，除了寄存器和L1緩存可以操作指定字長的數(shù)據(jù)，下層的內存子系統(tǒng)就不會再使用這么小的單位了，而是直接移動數(shù)據(jù)塊，比如以緩存線為單位訪問數(shù)據(jù)。

對于組沖突，可以這么理解：與上文相似，假設一個緩存，由512條緩存線組成，每條線64字節(jié)，容量32KB。

假如它是直接映射緩存，由于它往往使用地址的低位直接映射緩存線編號，所以所有的32K倍數(shù)的地址（32K，64K，96K等）都會映射到同一條線上（即第0線）。假如程序的內存組織不當，交替的去訪問布置在這些地址的數(shù)據(jù)，則會導致沖突。從外表看來就好像緩存只有1條線了，盡管其他緩存線一直是空閑著的。

如果是全相聯(lián)緩存，那么每條緩存線都是獨立的，可以對應于內存中的任意緩存線。只有當所有的512條緩存線都被占滿后才會出現(xiàn)沖突。

組相聯(lián)是前兩者的折中，每一路中的緩存線采用直接映射方式，而在路與路之間，緩存控制器使用全相聯(lián)映射算法，決定選擇一組中的哪一條線。

如果是2路組相聯(lián)緩存，那么這512條緩存線就被分為了2路，每路256條線，一路16KB。此時所有為16K整數(shù)倍的地址（16K，32K，48K等）都會映射到第0線，但由于2路是關聯(lián)的，所以可以同時有2個這種地址的內容被緩存，不會發(fā)生沖突。當然了，如果要訪問第三個這種地址，還是要先騰空已有的一條才行。所以極端情況下，從外表看來就好像緩存只有2條線了，盡管其他緩存線一直是空閑著的。

如果是8路組相聯(lián)緩存（與文中示例相同），那么這512條緩存線就被分為了8路，每路64條線，一路4KB。所以如果數(shù)組中元素地址是4K對齊的，并且程序交替的訪問這些元素，就會出現(xiàn)組沖突。從外表看來就好像緩存只有8條線了，盡管其他緩存線一直是空閑著的。

根據(jù)內存計算cacde結構：

page是os的概念，而cache是cpu的概念。虛擬地址和物理地址以page為單位進行操作的，由兩部分組成：page地址和page內地址（偏移），所以，os的page和cpu的cache是沒任何必然關系的。

審核編輯：湯梓紅