每個程序員都應該了解的 CPU 高速緩存

英文原文：Memorypart2:CPUcaches來源：oschina

[編者按：這是Ulrich Drepper寫“程序員都該知道存儲器”的第二部。那些沒有讀過第一部的讀者可能希望從這一部開始。這本書寫的非常好，并且感謝Ulrich授權我們出版。

一點說明：書籍出版時可能會有一些印刷錯誤，如果你發現，并且想讓它在后續的出版中更正，請將意見發郵件到lwn@lwn.net ，我們一定會更正，并反饋給Ulrich的文檔副本，別的讀者就不會受到這些困擾。]

現在的CPU比25年前要精密得多了。在那個年代，CPU的頻率與內存總線的頻率基本在同一層面上。內存的訪問速度僅比寄存器慢那么一點點。但是，這一局面在上世紀90年代被打破了。CPU的頻率大大提升，但內存總線的頻率與內存芯片的性能卻沒有得到成比例的提升。并不是因為造不出更快的內存，只是因為太貴了。內存如果要達到目前CPU那樣的速度，那么它的造價恐怕要貴上好幾個數量級。

如果有兩個選項讓你選擇，一個是速度非常快、但容量很小的內存，一個是速度還算快、但容量很多的內存，如果你的工作集比較大，超過了前一種情況，那么人們總是會選擇第二個選項。原因在于輔存(一般為磁盤)的速度。由于工作集超過主存，那么必須用輔存來保存交換出去的那部分數據，而輔存的速度往往要比主存慢上好幾個數量級。

好在這問題也并不全然是非甲即乙的選擇。在配置大量DRAM的同時，我們還可以配置少量SRAM。將地址空間的某個部分劃給SRAM，剩下的部分劃給DRAM。一般來說，SRAM可以當作擴展的寄存器來使用。

上面的做法看起來似乎可以，但實際上并不可行。首先，將SRAM內存映射到進程的虛擬地址空間就是個非常復雜的工作，而且，在這種做法中，每個進程都需要管理這個SRAM區內存的分配。每個進程可能有大小完全不同的SRAM區，而組成程序的每個模塊也需要索取屬于自身的SRAM，更引入了額外的同步需求。簡而言之，快速內存帶來的好處完全被額外的管理開銷給抵消了。 基于以上的原因，我們不將SRAM放在OS或用戶的控制下，而是將它交由處理器來使用和管理。在這種模式下，SRAM用于對存儲在主存中、即將使用的數據進行臨時拷貝(換句話說，緩存)。這種做法的依據是程序代碼和數據具有時間局部性和空間局部性。也就是說，在一段較短的時間內，同一份代碼和數據有很大的可能被重復使用。對代碼來說，是循環，即同一段代碼被反復執行(完美的空間局部性)。對數據來說，是反復訪問某一小片區域中的數據。即使在短時間內對內存的訪問并不連續，但仍有很大可能在不長的時間內重復訪問同一份數據(空間局部性)。這兩個局部性是我們理解CPU高速緩存的關鍵。

我們先用一個簡單的計算來展示一下高速緩存的效率。假設，訪問主存需要200個周期，而訪問高速緩存需要15個周期。如果使用100個數據元素100次，那么在沒有高速緩存的情況下，需要2000000個周期，而在有高速緩存、而且所有數據都已被緩存的情況下，只需要168500個周期。節約了91.5%的時間。

用作高速緩存的SRAM容量比主存小得多。以我的經驗來說，高速緩存的大小一般是主存的千分之一左右(目前一般是4GB主存、4MB緩存)。這一點本身并不是什么問題。只是，計算機一般都會有比較大的主存，因此工作集的大小總是會大于緩存。特別是那些運行多進程的系統，它的工作集大小是所有進程加上內核的總和。

處理高速緩存大小的限制需要制定一套很好的策略來決定在給定的時間內什么數據應該被緩存。由于不是所有數據的工作集都是在完全相同的時間段內被使用的，我們可以用一些技術手段將需要用到的數據臨時替換那些當前并未使用的緩存數據。這種預取將會減少部分訪問主存的成本，因為它與程序的執行是異步的。所有的這些技術將會使高速緩存在使用的時候看起來比實際更大。我們將在3.3節討論這些問題。我們將在第6章討論如何讓這些技術能很好地幫助程序員，讓處理器更高效地工作。

3.1 高速緩存的位置

在深入介紹高速緩存的技術細節之前，有必要說明一下它在現代計算機系統中所處的位置。

圖3.1: 最簡單的高速緩存配置圖

圖3.1展示了最簡單的高速緩存配置。早期的一些系統就是類似的架構。在這種架構中，CPU核心不再直連到主存。{在一些更早的系統中，高速緩存像CPU與主存一樣連到系統總線上。那種做法更像是一種hack，而不是真正的解決方案。}數據的讀取和存儲都經過高速緩存。CPU核心與高速緩存之間是一條特殊的快速通道。在簡化的表示法中，主存與高速緩存都連到系統總線上，這條總線同時還用于與其它組件通信。我們管這條總線叫“FSB”——就是現在稱呼它的術語，參見第2.2節。在這一節里，我們將忽略北橋。

在過去的幾十年，經驗表明使用了馮諾伊曼結構的計算機，將用于代碼和數據的高速緩存分開是存在巨大優勢的。自1993年以來，Intel并且一直堅持使用獨立的代碼和數據高速緩存。由于所需的代碼和數據的內存區域是幾乎相互獨立的，這就是為什么獨立緩存工作得更完美的原因。近年來，獨立緩存的另一個優勢慢慢顯現出來：常見處理器解碼指令的步驟是緩慢的，尤其當管線為空的時候，往往會伴隨著錯誤的預測或無法預測的分支的出現，將高速緩存技術用于指令解碼可以加快其執行速度。

在高速緩存出現后不久，系統變得更加復雜。高速緩存與主存之間的速度差異進一步拉大，直到加入了另一級緩存。新加入的這一級緩存比第一級緩存更大，但是更慢。由于加大一級緩存的做法從經濟上考慮是行不通的，所以有了二級緩存，甚至現在的有些系統擁有三級緩存，如圖3.2所示。隨著單個CPU中核數的增加，未來甚至可能會出現更多層級的緩存。

圖3.2: 三級緩存的處理器

圖3.2展示了三級緩存，并介紹了本文將使用的一些術語。L1d是一級數據緩存，L1i是一級指令緩存，等等。請注意，這只是示意圖，真正的數據流并不需要流經上級緩存。CPU的設計者們在設計高速緩存的接口時擁有很大的自由。而程序員是看不到這些設計選項的。

另外，我們有多核CPU，每個核心可以有多個“線程”。核心與線程的不同之處在于，核心擁有獨立的硬件資源({早期的多核CPU甚至有獨立的二級緩存。})。在不同時使用相同資源(比如，通往外界的連接)的情況下，核心可以完全獨立地運行。而線程只是共享資源。Intel的線程只有獨立的寄存器，而且還有限制——不是所有寄存器都獨立，有些是共享的。綜上，現代CPU的結構就像圖3.3所示。

圖3.3 多處理器、多核心、多線程

在上圖中，有兩個處理器，每個處理器有兩個核心，每個核心有兩個線程。線程們共享一級緩存。核心(以深灰色表示)有獨立的一級緩存，同時共享二級緩存。處理器(淡灰色)之間不共享任何緩存。這些信息很重要，特別是在討論多進程和多線程情況下緩存的影響時尤為重要。

3.2 高級的緩存操作

了解成本和節約使用緩存，我們必須結合在第二節中講到的關于計算機體系結構和RAM技術，以及前一節講到的緩存描述來探討。

默認情況下，CPU核心所有的數據的讀或寫都存儲在緩存中。當然，也有內存區域不能被緩存的，但是這種情況只發生在操作系統的實現者對數據考慮的前提下；對程序實現者來說，這是不可見的。這也說明，程序設計者可以故意繞過某些緩存，不過這將是第六節中討論的內容了。

如果CPU需要訪問某個字(word)，先檢索緩存。很顯然，緩存不可能容納主存所有內容(否則還需要主存干嘛)。系統用字的內存地址來對緩存條目進行標記。如果需要讀寫某個地址的字，那么根據標簽來檢索緩存即可。這里用到的地址可以是虛擬地址，也可以是物理地址，取決于緩存的具體實現。

標簽是需要額外空間的，用字作為緩存的粒度顯然毫無效率。比如，在x86機器上，32位字的標簽可能需要32位，甚至更長。另一方面，由于空間局部性的存在，與當前地址相鄰的地址有很大可能會被一起訪問。再回憶下2.2.1節——內存模塊在傳輸位于同一行上的多份數據時，由于不需要發送新CAS信號，甚至不需要發送RAS信號，因此可以實現很高的效率。基于以上的原因，緩存條目并不存儲單個字，而是存儲若干連續字組成的“線”。在早期的緩存中，線長是32字節，現在一般是64字節。對于64位寬的內存總線，每條線需要8次傳輸。而DDR對于這種傳輸模式的支持更為高效。

當處理器需要內存中的某塊數據時，整條緩存線被裝入L1d。緩存線的地址通過對內存地址進行掩碼操作生成。對于64字節的緩存線，是將低6位置0。這些被丟棄的位作為線內偏移量。其它的位作為標簽，并用于在緩存內定位。在實踐中，我們將地址分為三個部分。32位地址的情況如下:

如果緩存線長度為2O，那么地址的低O位用作線內偏移量。上面的S位選擇“緩存集”。后面我們會說明使用緩存集的原因。現在只需要明白一共有2S個緩存集就夠了。剩下的32 – S – O = T位組成標簽。它們用來區分別名相同的各條線{有相同S部分的緩存線被稱為有相同的別名。}用于定位緩存集的S部分不需要存儲，因為屬于同一緩存集的所有線的S部分都是相同的。

當某條指令修改內存時，仍然要先裝入緩存線，因為任何指令都不可能同時修改整條線(只有一個例外——第6.1節中將會介紹的寫合并(write-combine))。因此需要在寫操作前先把緩存線裝載進來。如果緩存線被寫入，但還沒有寫回主存，那就是所謂的“臟了”。臟了的線一旦寫回主存，臟標記即被清除。

為了裝入新數據，基本上總是要先在緩存中清理出位置。L1d將內容逐出L1d，推入L2(線長相同)。當然，L2也需要清理位置。于是L2將內容推入L3，最后L3將它推入主存。這種逐出操作一級比一級昂貴。這里所說的是現代AMD和VIA處理器所采用的獨占型緩存(exclusive cache)。而Intel采用的是包容型緩存(inclusive cache)，{并不完全正確，Intel有些緩存是獨占型的，還有一些緩存具有獨占型緩存的特點。}L1d的每條線同時存在于L2里。對這種緩存，逐出操作就很快了。如果有足夠L2，對于相同內容存在不同地方造成內存浪費的缺點可以降到最低，而且在逐出時非常有利。而獨占型緩存在裝載新數據時只需要操作L1d，不需要碰L2，因此會比較快。

處理器體系結構中定義的作為存儲器的模型只要還沒有改變，那就允許多CPU按照自己的方式來管理高速緩存。這表示，例如，設計優良的處理器，利用很少或根本沒有內存總線活動，并主動寫回主內存臟高速緩存行。這種高速緩存架構在如x86和x86-64各種各樣的處理器間存在。制造商之間，即使在同一制造商生產的產品中，證明了的內存模型抽象的力量。

在對稱多處理器（SMP）架構的系統中，CPU的高速緩存不能獨立的工作。在任何時候，所有的處理器都應該擁有相同的內存內容。保證這樣的統一的內存視圖被稱為“高速緩存一致性”。如果在其自己的高速緩存和主內存間，處理器設計簡單，它將不會看到在其他處理器上的臟高速緩存行的內容。從一個處理器直接訪問另一個處理器的高速緩存這種模型設計代價將是非常昂貴的，它是一個相當大的瓶頸。相反，當另一個處理器要讀取或寫入到高速緩存線上時，處理器會去檢測。

如果CPU檢測到一個寫訪問，而且該CPU的cache中已經緩存了一個cache line的原始副本，那么這個cache line將被標記為無效的cache line。接下來在引用這個cache line之前，需要重新加載該cache line。需要注意的是讀訪問并不會導致cache line被標記為無效的。

更精確的cache實現需要考慮到其他更多的可能性，比如第二個CPU在讀或者寫他的cache line時，發現該cache line在第一個CPU的cache中被標記為臟數據了，此時我們就需要做進一步的處理。在這種情況下，主存儲器已經失效，第二個CPU需要讀取第一個CPU的cache line。通過測試，我們知道在這種情況下第一個CPU會將自己的cache line數據自動發送給第二個CPU。這種操作是繞過主存儲器的，但是有時候存儲控制器是可以直接將第一個CPU中的cache line數據存儲到主存儲器中。對第一個CPU的cache的寫訪問會導致本地cache line的所有拷貝被標記為無效。

隨著時間的推移，一大批緩存一致性協議已經建立。其中，最重要的是MESI,我們將在第3.3.4節進行介紹。以上結論可以概括為幾個簡單的規則:

一個臟緩存線不存在于任何其他處理器的緩存之中。
同一緩存線中的干凈拷貝可以駐留在任意多個其他緩存之中。

如果遵守這些規則,處理器甚至可以在多處理器系統中更加有效的使用它們的緩存。所有的處理器需要做的就是監控其他每一個寫訪問和比較本地緩存中的地址。在下一節中,我們將介紹更多細節方面的實現,尤其是存儲開銷方面的細節。

最后，我們至少應該關注高速緩存命中或未命中帶來的消耗。下面是英特爾奔騰 M 的數據：

To Where	Cycles
Register	<= 1
L1d	~3
L2	~14
Main Memory	~240

這是在CPU周期中的實際訪問時間。有趣的是，對于L2高速緩存的訪問時間很大一部分（甚至是大部分）是由線路的延遲引起的。這是一個限制，增加高速緩存的大小變得更糟。只有當減小時（例如，從60納米的Merom到45納米Penryn處理器），可以提高這些數據。

表格中的數字看起來很高，但是，幸運的是，整個成本不必須負擔每次出現的緩存加載和緩存失效。某些部分的成本可以被隱藏。現在的處理器都使用不同長度的內部管道，在管道內指令被解碼，并為準備執行。如果數據要傳送到一個寄存器，那么部分的準備工作是從存儲器（或高速緩存）加載數據。如果內存加載操作在管道中足夠早的進行，它可以與其他操作并行發生，那么加載的全部發銷可能會被隱藏。對L1D常常可能如此；某些有長管道的處理器的L2也可以。

提早啟動內存的讀取有許多障礙。它可能只是簡單的不具有足夠資源供內存訪問，或者地址從另一個指令獲取，然后加載的最終地址才變得可用。在這種情況下，加載成本是不能隱藏的（完全的）。

對于寫操作，CPU并不需要等待數據被安全地放入內存。只要指令具有類似的效果，就沒有什么東西可以阻止CPU走捷徑了。它可以早早地執行下一條指令，甚至可以在影子寄存器(shadow register)的幫助下，更改這個寫操作將要存儲的數據。

圖3.4: 隨機寫操作的訪問時間

圖3.4展示了緩存的效果。關于產生圖中數據的程序，我們會在稍后討論。這里大致說下，這個程序是連續隨機地訪問某塊大小可配的內存區域。每個數據項的大小是固定的。數據項的多少取決于選擇的工作集大小。Y軸表示處理每個元素平均需要多少個CPU周期，注意它是對數刻度。X軸也是同樣，工作集的大小都以2的n次方表示。

圖中有三個比較明顯的不同階段。很正常，這個處理器有L1d和L2，沒有L3。根據經驗可以推測出，L1d有213字節，而L2有220字節。因為，如果整個工作集都可以放入L1d，那么只需不到10個周期就可以完成操作。如果工作集超過L1d，處理器不得不從L2獲取數據，于是時間飄升到28個周期左右。如果工作集更大，超過了L2，那么時間進一步暴漲到480個周期以上。這時候，許多操作將不得不從主存中獲取數據。更糟糕的是，如果修改了數據，還需要將這些臟了的緩存線寫回內存。

看了這個圖，大家應該會有足夠的動力去檢查代碼、改進緩存的利用方式了吧？這里的性能改善可不只是微不足道的幾個百分點，而是幾個數量級呀。在第6節中，我們將介紹一些編寫高效代碼的技巧。而下一節將進一步深入緩存的設計。雖然精彩，但并不是必修課，大家可以選擇性地跳過。

3.3 CPU 緩存實現細節

高速緩存的實現者遇到這樣的難題：巨大的主內存中每一個單元都潛在的需要緩存。如果程序的工作集足夠大，這意味著很多主內存單元競爭高速緩存的每一個地方。先前有過提示，主存和高速緩存的大小比是1000：1，這是不常見的。

3.3.1 關聯性

可以這樣實現一個高速緩存，每個高速緩存段（高速緩存行：cache line）都可以容納任何內存位置的一個副本。這就是所謂的全關聯。要訪問一個緩存段，處理器核心不得不用所有緩存段的標簽和請求地址的標簽一一做比較。標簽將包含除去緩存段的偏移量全部的地址，（譯注：也就是去除3.2節中圖的O）（這意味著，S在3.2節的圖中是零）

高速緩存有類似這樣的實現，但是，看看在今天使用的L2的數目，表明這是不切實際的。給定4MB的高速緩存和64B的高速緩存段，高速緩存將有65,536個項。為了達到足夠的性能，緩存邏輯必須能夠在短短的幾個時鐘周期內，從所有這些項中，挑一個匹配給定的標簽。實現這一點的工作將是巨大的。

Figure 3.5: 全關聯高速緩存原理圖

對于每個高速緩存行，比較器是需要比較大標簽（注意，S是零）。每個連接旁邊的字母表示位的寬度。如果沒有給出，它是一個單比特線。每個比較器都要比較兩個T-位寬的值。然后，基于該結果，適當的高速緩存行的內容被選中，并使其可用。這需要合并多套O數據線，因為他們是緩存桶（譯注：這里類似把O輸出接入多選器，所以需要合并）。實現僅僅一個比較器，需要晶體管的數量就非常大，特別是因為它必須非常快。沒有迭代比較器是可用的。節省比較器的數目的唯一途徑是通過反復比較標簽，以減少它們的數目。這是不適合的，出于同樣的原因，迭代比較器不可用：它的時間太長。

全關聯高速緩存對小緩存是實用的（例如，在某些Intel處理器的TLB緩存是全關聯的），但這些緩存都很小，非常小的。我們正在談論的最多幾十項。

對于L1i，L1d和更高級別的緩存，需要采用不同的方法。可以做的就是是限制搜索。最極端的限制是，每個標簽映射到一個明確的緩存條目。計算很簡單：給定的4MB/64B緩存有65536項，我們可以使用地址的bit6到bit21（16位）來直接尋址高速緩存的每一個項。地址的低6位作為高速緩存段的索引。

Figure 3.6: Direct-Mapped Cache Schematics

在圖3.6中可以看出，這種直接映射的高速緩存，速度快，比較容易實現。它只是需要一個比較器，一個多路復用器（在這個圖中有兩個，標記和數據是分離的，但是對于設計這不是一個硬性要求），和一些邏輯來選擇只是有效的高速緩存行的內容。由于速度的要求，比較器是復雜的，但是現在只需要一個，結果是可以花更多的精力，讓其變得快速。這種方法的復雜性在于在多路復用器。一個簡單的多路轉換器中的晶體管的數量增速是O（log N）的，其中N是高速緩存段的數目。這是可以容忍的，但可能會很慢，在某種情況下，速度可提升，通過增加多路復用器晶體管數量，來并行化的一些工作和自身增速。晶體管的總數只是隨著快速增長的高速緩存緩慢的增加，這使得這種解決方案非常有吸引力。但它有一個缺點：只有用于直接映射地址的相關的地址位均勻分布，程序才能很好工作。如果分布的不均勻，而且這是常態，一些緩存項頻繁的使用，并因此多次被換出，而另一些則幾乎不被使用或一直是空的。

Figure 3.7: 組關聯高速緩存原理圖

可以通過使高速緩存的組關聯來解決此問題。組關聯結合高速緩存的全關聯和直接映射高速緩存特點，在很大程度上避免那些設計的弱點。圖3.7顯示了一個組關聯高速緩存的設計。標簽和數據存儲分成不同的組并可以通過地址選擇。這類似直接映射高速緩存。但是，小數目的值可以在同一個高速緩存組緩存，而不是一個緩存組只有一個元素，用于在高速緩存中的每個設定值是相同的一組值的緩存。所有組的成員的標簽可以并行比較，這類似全關聯緩存的功能。

其結果是高速緩存，不容易被不幸或故意選擇同屬同一組編號的地址所擊敗，同時高速緩存的大小并不限于由比較器的數目，可以以并行的方式實現。如果高速緩存增長，只（在該圖中）增加列的數目，而不增加行數。只有高速緩存之間的關聯性增加，行數才會增加。今天，處理器的L2高速緩存或更高的高速緩存，使用的關聯性高達16。 L1高速緩存通常使用8。

L2 Cache Size	Associativity
Direct	2	4	8
CL=32	CL=64	CL=32	CL=64	CL=32	CL=64	CL=32	CL=64
512k	27,794,595	20,422,527	25,222,611	18,303,581	24,096,510	17,356,121	23,666,929	17,029,334
1M	19,007,315	13,903,854	16,566,738	12,127,174	15,537,500	11,436,705	15,162,895	11,233,896
2M	12,230,962	8,801,403	9,081,881	6,491,011	7,878,601	5,675,181	7,391,389	5,382,064
4M	7,749,986	5,427,836	4,736,187	3,159,507	3,788,122	2,418,898	3,430,713	2,125,103
8M	4,731,904	3,209,693	2,690,498	1,602,957	2,207,655	1,228,190	2,111,075	1,155,847
16M	2,620,587	1,528,592	1,958,293	1,089,580	1,704,878	883,530	1,671,541	862,324

Table 3.1: 高速緩存大小，關聯行，段大小的影響

給定我們4MB/64B高速緩存，8路組關聯，相關的緩存留給我們的有8192組，只用標簽的13位，就可以尋址緩集。要確定哪些（如果有的話）的緩存組設置中的條目包含尋址的高速緩存行，8個標簽都要進行比較。在很短的時間內做出來是可行的。通過一個實驗，我們可以看到，這是有意義的。

表3.1顯示一個程序在改變緩存大小，緩存段大小和關聯集大小，L2高速緩存的緩存失效數量（根據Linux內核相關的方面人的說法，GCC在這種情況下，是他們所有中最重要的標尺）。在7.2節中，我們將介紹工具來模擬此測試要求的高速緩存。

萬一這還不是很明顯，所有這些值之間的關系是高速緩存的大小為：

cache line size × associativity × number of sets

地址被映射到高速緩存使用

O= log2cache line size
S= log2number of sets

在第3.2節中的圖顯示的方式。

Figure 3.8: 緩存段大小 vs 關聯行 (CL=32)

圖3.8表中的數據更易于理解。它顯示一個固定的32個字節大小的高速緩存行的數據。對于一個給定的高速緩存大小，我們可以看出，關聯性，的確可以幫助明顯減少高速緩存未命中的數量。對于8MB的緩存，從直接映射到2路組相聯，可以減少近44％的高速緩存未命中。組相聯高速緩存和直接映射緩存相比，該處理器可以把更多的工作集保持在緩存中。

在文獻中，偶爾可以讀到，引入關聯性，和加倍高速緩存的大小具有相同的效果。在從4M緩存躍升到8MB緩存的極端的情況下，這是正確的。關聯性再提高一倍那就肯定不正確啦。正如我們所看到的數據，后面的收益要小得多。我們不應該完全低估它的效果，雖然。在示例程序中的內存使用的峰值是5.6M。因此，具有8MB緩存不太可能有很多（兩個以上）使用相同的高速緩存的組。從較小的緩存的關聯性的巨大收益可以看出，較大工作集可以節省更多。

在一般情況下，增加8以上的高速緩存之間的關聯性似乎對只有一個單線程工作量影響不大。隨著介紹一個使用共享L2的多核處理器，形勢發生了變化。現在你基本上有兩個程序命中相同的緩存， 實際上導致高速緩存減半（對于四核處理器是1/4）。因此，可以預期，隨著核的數目的增加，共享高速緩存的相關性也應增長。一旦這種方法不再可行（16 路組關聯性已經很難）處理器設計者不得不開始使用共享的三級高速緩存和更高級別的，而L2高速緩存只被核的一個子集共享。

從圖3.8中，我們還可以研究緩存大小對性能的影響。這一數據需要了解工作集的大小才能進行解讀。很顯然，與主存相同的緩存比小緩存能產生更好的結果，因此，緩存通常是越大越好。

上文已經說過，示例中最大的工作集為5.6M。它并沒有給出最佳緩存大小值，但我們可以估算出來。問題主要在于內存的使用并不連續，因此，即使是16M的緩存，在處理5.6M的工作集時也會出現沖突(參見2路集合關聯式16MB緩存vs直接映射式緩存的優點)。不管怎樣，我們可以有把握地說，在同樣5.6M的負載下，緩存從16MB升到32MB基本已沒有多少提高的余地。但是，工作集是會變的。如果工作集不斷增大，緩存也需要隨之增大。在購買計算機時，如果需要選擇緩存大小，一定要先衡量工作集的大小。原因可以參見圖3.10。

圖3.9: 測試的內存分布情況

我們執行兩項測試。第一項測試是按順序地訪問所有元素。測試程序循著指針n進行訪問，而所有元素是鏈接在一起的，從而使它們的被訪問順序與在內存中排布的順序一致，如圖3.9的下半部分所示，末尾的元素有一個指向首元素的引用。而第二項測試(見圖3.9的上半部分)則是按隨機順序訪問所有元素。在上述兩個測試中，所有元素都構成一個單向循環鏈表。

3.3.2 Cache的性能測試

用于測試程序的數據可以模擬一個任意大小的工作集：包括讀、寫訪問，隨機、連續訪問。在圖3.4中我們可以看到，程序為工作集創建了一個與其大小和元素類型相同的數組：

1 2 3 4

struct l { struct l *n; long int pad[NPAD]; };

n字段將所有節點隨機得或者順序的加入到環形鏈表中，用指針從當前節點進入到下一個節點。pad字段用來存儲數據，其可以是任意大小。在一些測試程序中，pad字段是可以修改的, 在其他程序中，pad字段只可以進行讀操作。

在性能測試中，我們談到工作集大小的問題，工作集使用結構體l定義的元素表示的。2N字節的工作集包含

2N/sizeof(struct l)

個元素. 顯然sizeof(struct l) 的值取決于NPAD的大小。在32位系統上，NPAD=7意味著數組的每個元素的大小為32字節，在64位系統上，NPAD=7意味著數組的每個元素的大小為64字節。

單線程順序訪問

最簡單的情況就是遍歷鏈表中順序存儲的節點。無論是從前向后處理，還是從后向前，對于處理器來說沒有什么區別。下面的測試中，我們需要得到處理鏈表中一個元素所需要的時間，以CPU時鐘周期最為計時單元。圖3.10顯示了測試結構。除非有特殊說明, 所有的測試都是在Pentium4 64-bit 平臺上進行的，因此結構體l中NPAD=0，大小為8字節。

圖 3.10: 順序讀訪問, NPAD=0

圖 3.11: 順序讀多個字節

一開始的兩個測試數據收到了噪音的污染。由于它們的工作負荷太小，無法過濾掉系統內其它進程對它們的影響。我們可以認為它們都是4個周期以內的。這樣一來，整個圖可以劃分為比較明顯的三個部分:

工作集小于214字節的。
工作集從215字節到220字節的。
工作集大于221字節的。

這樣的結果很容易解釋——是因為處理器有16KB的L1d和1MB的L2。而在這三個部分之間，并沒有非常銳利的邊緣，這是因為系統的其它部分也在使用緩存，我們的測試程序并不能獨占緩存的使用。尤其是L2，它是統一式的緩存，處理器的指令也會使用它(注: Intel使用的是包容式緩存)。

測試的實際耗時可能會出乎大家的意料。L1d的部分跟我們預想的差不多，在一臺P4上耗時為4個周期左右。但L2的結果則出乎意料。大家可能覺得需要14個周期以上，但實際只用了9個周期。這要歸功于處理器先進的處理邏輯，當它使用連續的內存區時，會預先讀取下一條緩存線的數據。這樣一來，當真正使用下一條線的時候，其實已經早已讀完一半了，于是真正的等待耗時會比L2的訪問時間少很多。

在工作集超過L2的大小之后，預取的效果更明顯了。前面我們說過，主存的訪問需要耗時200個周期以上。但在預取的幫助下，實際耗時保持在9個周期左右。200 vs 9，效果非常不錯。

我們可以觀察到預取的行為，至少可以間接地觀察到。圖3.11中有4條線，它們表示處理不同大小結構時的耗時情況。隨著結構的變大，元素間的距離變大了。圖中4條線對應的元素距離分別是0、56、120和248字節。

圖中最下面的這一條線來自前一個圖，但在這里更像是一條直線。其它三條線的耗時情況比較差。圖中這些線也有比較明顯的三個階段，同時，在小工作集的情況下也有比較大的錯誤(請再次忽略這些錯誤)。在只使用L1d的階段，這些線條基本重合。因為這時候還不需要預取，只需要訪問L1d就行。

在L2階段，三條新加的線基本重合，而且耗時比老的那條線高很多，大約在28個周期左右，差不多就是L2的訪問時間。這表明，從L2到L1d的預取并沒有生效。這是因為，對于最下面的線(NPAD=0)，由于結構小，8次循環后才需要訪問一條新緩存線，而上面三條線對應的結構比較大，拿相對最小的NPAD=7來說，光是一次循環就需要訪問一條新線，更不用說更大的NPAD=15和31了。而預取邏輯是無法在每個周期裝載新線的，因此每次循環都需要從L2讀取，我們看到的就是從L2讀取的時延。

更有趣的是工作集超過L2容量后的階段。快看，4條線遠遠地拉開了。元素的大小變成了主角，左右了性能。處理器應能識別每一步(stride)的大小，不去為NPAD=15和31獲取那些實際并不需要的緩存線(參見6.3.1)。元素大小對預取的約束是根源于硬件預取的限制——它無法跨越頁邊界。如果允許預取器跨越頁邊界，而下一頁不存在或無效，那么OS還得去尋找它。這意味著，程序需要遭遇一次并非由它自己產生的頁錯誤，這是完全不能接受的。在NPAD=7或者更大的時候，由于每個元素都至少需要一條緩存線，預取器已經幫不上忙了，它沒有足夠的時間去從內存裝載數據。 另一個導致慢下來的原因是TLB緩存的未命中。TLB是存儲虛實地址映射的緩存，參見第4節。為了保持快速，TLB只有很小的容量。如果有大量頁被反復訪問，超出了TLB緩存容量，就會導致反復地進行地址翻譯，這會耗費大量時間。TLB查找的代價分攤到所有元素上，如果元素越大，那么元素的數量越少，每個元素承擔的那一份就越多。

為了觀察TLB的性能，我們可以進行另兩項測試。第一項：我們還是順序存儲列表中的元素，使NPAD=7，讓每個元素占滿整個cache line，第二項：我們將列表的每個元素存儲在一個單獨的頁上，忽略每個頁沒有使用的部分以用來計算工作集的大小。（這樣做可能不太一致，因為在前面的測試中，我計算了結構體中每個元素沒有使用的部分，從而用來定義NPAD的大小，因此每個元素占滿了整個頁，這樣以來工作集的大小將會有所不同。但是這不是這項測試的重點，預取的低效率多少使其有點不同）。結果表明，第一項測試中，每次列表的迭代都需要一個新的cache line，而且每64個元素就需要一個新的頁。第二項測試中，每次迭代都會在一個新的頁中加載一個新的cache line。

圖 3.12: TLB 對順序讀的影響

結果見圖3.12。該測試與圖3.11是在同一臺機器上進行的。基于可用RAM空間的有限性，測試設置容量空間大小為2的24次方字節，這就需要1GB的容量將對象放置在分頁上。圖3.12中下方的紅色曲線正好對應了圖3.11中NPAD等于7的曲線。我們看到不同的步長顯示了高速緩存L1d和L2的大小。第二條曲線看上去完全不同，其最重要的特點是當工作容量到達2的13次方字節時開始大幅度增長。這就是TLB緩存溢出的時候。我們能計算出一個64字節大小的元素的TLB緩存有64個輸入。成本不會受頁面錯誤影響，因為程序鎖定了存儲器以防止內存被換出。

可以看出，計算物理地址并把它存儲在TLB中所花費的周期數量級是非常高的。圖3.12的表格顯示了一個極端的例子，但從中可以清楚的得到：TLB緩存效率降低的一個重要因素是大型NPAD值的減緩。由于物理地址必須在緩存行能被L2或主存讀取之前計算出來，地址轉換這個不利因素就增加了內存訪問時間。這一點部分解釋了為什么NPAD等于31時每個列表元素的總花費比理論上的RAM訪問時間要高。

圖3.13 NPAD等于1時的順序讀和寫

通過查看鏈表元素被修改時測試數據的運行情況，我們可以窺見一些更詳細的預取實現細節。圖3.13顯示了三條曲線。所有情況下元素寬度都為16個字節。第一條曲線“Follow”是熟悉的鏈表走線在這里作為基線。第二條曲線，標記為“Inc”，僅僅在當前元素進入下一個前給其增加thepad[0]成員。第三條曲線，標記為”Addnext0″， 取出下一個元素的thepad[0]鏈表元素并把它添加為當前鏈表元素的thepad[0]成員。

在沒運行時，大家可能會以為”Addnext0″更慢，因為它要做的事情更多——在沒進到下個元素之前就需要裝載它的值。但實際的運行結果令人驚訝——在某些小工作集下，”Addnext0″比”Inc”更快。這是為什么呢？原因在于，系統一般會對下一個元素進行強制性預取。當程序前進到下個元素時，這個元素其實早已被預取在L1d里。因此，只要工作集比L2小，”Addnext0″的性能基本就能與”Follow”測試媲美。

但是，”Addnext0″比”Inc”更快離開L2，這是因為它需要從主存裝載更多的數據。而在工作集達到221字節時，”Addnext0″的耗時達到了28個周期，是同期”Follow”14周期的兩倍。這個兩倍也很好解釋。”Addnext0″和”Inc”涉及對內存的修改，因此L2的逐出操作不能簡單地把數據一扔了事，而必須將它們寫入內存。因此FSB的可用帶寬變成了一半，傳輸等量數據的耗時也就變成了原來的兩倍。

圖3.14: 更大L2/L3緩存的優勢

決定順序式緩存處理性能的另一個重要因素是緩存容量。雖然這一點比較明顯，但還是值得一說。圖3.14展示了128字節長元素的測試結果(64位機，NPAD=15)。這次我們比較三臺不同計算機的曲線，兩臺P4，一臺Core 2。兩臺P4的區別是緩存容量不同，一臺是32k的L1d和1M的L2，一臺是16K的L1d、512k的L2和2M的L3。Core 2那臺則是32k的L1d和4M的L2。

圖中最有趣的地方，并不是Core 2如何大勝兩臺P4，而是工作集開始增長到連末級緩存也放不下、需要主存熱情參與之后的部分。

Set Size	Sequential	Random
L2 Hit	L2 Miss	#Iter	Ratio Miss/Hit	L2 Accesses Per Iter	L2 Hit	L2 Miss	#Iter	Ratio Miss/Hit	L2 Accesses Per Iter
220	88,636	843	16,384	0.94%	5.5	30,462	4721	1,024	13.42%	34.4
221	88,105	1,584	8,192	1.77%	10.9	21,817	15,151	512	40.98%	72.2
222	88,106	1,600	4,096	1.78%	21.9	22,258	22,285	256	50.03%	174.0
223	88,104	1,614	2,048	1.80%	43.8	27,521	26,274	128	48.84%	420.3
224	88,114	1,655	1,024	1.84%	87.7	33,166	29,115	64	46.75%	973.1
225	88,112	1,730	512	1.93%	175.5	39,858	32,360	32	44.81%	2,256.8
226	88,112	1,906	256	2.12%	351.6	48,539	38,151	16	44.01%	5,418.1
227	88,114	2,244	128	2.48%	705.9	62,423	52,049	8	45.47%	14,309.0
228	88,120	2,939	64	3.23%	1,422.8	81,906	87,167	4	51.56%	42,268.3
229	88,137	4,318	32	4.67%	2,889.2	119,079	163,398	2	57.84%	141,238.5

表3.2: 順序訪問與隨機訪問時L2命中與未命中的情況，NPAD=0

與我們預計的相似，最末級緩存越大，曲線停留在L2訪問耗時區的時間越長。在220字節的工作集時，第二臺P4(更老一些)比第一臺P4要快上一倍，這要完全歸功于更大的末級緩存。而Core 2拜它巨大的4M L2所賜，表現更為卓越。

對于隨機的工作負荷而言，可能沒有這么驚人的效果，但是，如果我們能將工作負荷進行一些裁剪，讓它匹配末級緩存的容量，就完全可以得到非常大的性能提升。也是由于這個原因，有時候我們需要多花一些錢，買一個擁有更大緩存的處理器。

單線程隨機訪問模式的測量

前面我們已經看到，處理器能夠利用L1d到L2之間的預取消除訪問主存、甚至是訪問L2的時延。

圖3.15: 順序讀取vs隨機讀取，NPAD=0

但是，如果換成隨機訪問或者不可預測的訪問，情況就大不相同了。圖3.15比較了順序讀取與隨機讀取的耗時情況。

換成隨機之后，處理器無法再有效地預取數據，只有少數情況下靠運氣剛好碰到先后訪問的兩個元素挨在一起的情形。

圖3.15中有兩個需要關注的地方。首先，在大的工作集下需要非常多的周期。這臺機器訪問主存的時間大約為200-300個周期，但圖中的耗時甚至超過了450個周期。我們前面已經觀察到過類似現象(對比圖3.11)。這說明，處理器的自動預取在這里起到了反效果。

其次，代表隨機訪問的曲線在各個階段不像順序訪問那樣保持平坦，而是不斷攀升。為了解釋這個問題，我們測量了程序在不同工作集下對L2的訪問情況。結果如圖3.16和表3.2。

從圖中可以看出，當工作集大小超過L2時，未命中率(L2未命中次數/L2訪問次數)開始上升。整條曲線的走向與圖3.15有些相似: 先急速爬升，隨后緩緩下滑，最后再度爬升。它與耗時圖有緊密的關聯。L2未命中率會一直爬升到100%為止。只要工作集足夠大(并且內存也足夠大)，就可以將緩存線位于L2內或處于裝載過程中的可能性降到非常低。

緩存未命中率的攀升已經可以解釋一部分的開銷。除此以外，還有一個因素。觀察表3.2的L2/#Iter列，可以看到每個循環對L2的使用次數在增長。由于工作集每次為上一次的兩倍，如果沒有緩存的話，內存的訪問次數也將是上一次的兩倍。在按順序訪問時，由于緩存的幫助及完美的預見性，對L2使用的增長比較平緩，完全取決于工作集的增長速度。

圖3.16: L2d未命中率

圖3.17: 頁意義上(Page-Wise)的隨機化，NPAD=7

而換成隨機訪問后，單位耗時的增長超過了工作集的增長，根源是TLB未命中率的上升。圖3.17描繪的是NPAD=7時隨機訪問的耗時情況。這一次，我們修改了隨機訪問的方式。正常情況下是把整個列表作為一個塊進行隨機(以∞表示)，而其它11條線則是在小一些的塊里進行隨機。例如，標簽為’60′的線表示以60頁(245760字節)為單位進行隨機。先遍歷完這個塊里的所有元素，再訪問另一個塊。這樣一來，可以保證任意時刻使用的TLB條目數都是有限的。 NPAD=7對應于64字節，正好等于緩存線的長度。由于元素順序隨機，硬件預取不可能有任何效果，特別是在元素較多的情況下。這意味著，分塊隨機時的L2未命中率與整個列表隨機時的未命中率沒有本質的差別。隨著塊的增大，曲線逐漸逼近整個列表隨機對應的曲線。這說明，在這個測試里，性能受到TLB命中率的影響很大，如果我們能提高TLB命中率，就能大幅度地提升性能(在后面的一個例子里，性能提升了38%之多)。

3.3.3 寫入時的行為

在我們開始研究多個線程或進程同時使用相同內存之前，先來看一下緩存實現的一些細節。我們要求緩存是一致的，而且這種一致性必須對用戶級代碼完全透明。而內核代碼則有所不同，它有時候需要對緩存進行轉儲(flush)。

這意味著，如果對緩存線進行了修改，那么在這個時間點之后，系統的結果應該是與沒有緩存的情況下是相同的，即主存的對應位置也已經被修改的狀態。這種要求可以通過兩種方式或策略實現：

寫通(write-through)
寫回(write-back)

寫通比較簡單。當修改緩存線時，處理器立即將它寫入主存。這樣可以保證主存與緩存的內容永遠保持一致。當緩存線被替代時，只需要簡單地將它丟棄即可。這種策略很簡單，但是速度比較慢。如果某個程序反復修改一個本地變量，可能導致FSB上產生大量數據流，而不管這個變量是不是有人在用，或者是不是短期變量。

寫回比較復雜。當修改緩存線時，處理器不再馬上將它寫入主存，而是打上已弄臟(dirty)的標記。當以后某個時間點緩存線被丟棄時，這個已弄臟標記會通知處理器把數據寫回到主存中，而不是簡單地扔掉。

寫回有時候會有非常不錯的性能，因此較好的系統大多采用這種方式。采用寫回時，處理器們甚至可以利用FSB的空閑容量來存儲緩存線。這樣一來，當需要緩存空間時，處理器只需清除臟標記，丟棄緩存線即可。

但寫回也有一個很大的問題。當有多個處理器(或核心、超線程)訪問同一塊內存時，必須確保它們在任何時候看到的都是相同的內容。如果緩存線在其中一個處理器上弄臟了(修改了，但還沒寫回主存)，而第二個處理器剛好要讀取同一個內存地址，那么這個讀操作不能去讀主存，而需要讀第一個處理器的緩存線。在下一節中，我們將研究如何實現這種需求。

在此之前，還有其它兩種緩存策略需要提一下:

寫入合并
不可緩存

這兩種策略用于真實內存不支持的特殊地址區，內核為地址區設置這些策略(x86處理器利用內存類型范圍寄存器MTRR)，余下的部分自動進行。MTRR還可用于寫通和寫回策略的選擇。

寫入合并是一種有限的緩存優化策略，更多地用于顯卡等設備之上的內存。由于設備的傳輸開銷比本地內存要高的多，因此避免進行過多的傳輸顯得尤為重要。如果僅僅因為修改了緩存線上的一個字，就傳輸整條線，而下個操作剛好是修改線上的下一個字，那么這次傳輸就過于浪費了。而這恰恰對于顯卡來說是比較常見的情形——屏幕上水平鄰接的像素往往在內存中也是靠在一起的。顧名思義，寫入合并是在寫出緩存線前，先將多個寫入訪問合并起來。在理想的情況下，緩存線被逐字逐字地修改，只有當寫入最后一個字時，才將整條線寫入內存，從而極大地加速內存的訪問。

最后來講一下不可緩存的內存。一般指的是不被RAM支持的內存位置，它可以是硬編碼的特殊地址，承擔CPU以外的某些功能。對于商用硬件來說，比較常見的是映射到外部卡或設備的地址。在嵌入式主板上，有時也有類似的地址，用來開關LED。對這些地址進行緩存顯然沒有什么意義。比如上述的LED，一般是用來調試或報告狀態，顯然應該盡快點亮或關閉。而對于那些PCI卡上的內存，由于不需要CPU的干涉即可更改，也不該緩存。

3.3.4 多處理器支持

在上節中我們已經指出當多處理器開始發揮作用的時候所遇到的問題。甚至對于那些不共享的高速級別的緩存（至少在L1d級別）的多核處理器也有問題。

直接提供從一個處理器到另一處理器的高速訪問，這是完全不切實際的。從一開始，連接速度根本就不夠快。實際的選擇是，在其需要的情況下，轉移到其他處理器。需要注意的是，這同樣應用在相同處理器上無需共享的高速緩存。

現在的問題是，當該高速緩存線轉移的時候會發生什么？這個問題回答起來相當容易：當一個處理器需要在另一個處理器的高速緩存中讀或者寫的臟的高速緩存線的時候。但怎樣處理器怎樣確定在另一個處理器的緩存中的高速緩存線是臟的？假設它僅僅是因為一個高速緩存線被另一個處理器加載將是次優的（最好的）。通常情況下，大多數的內存訪問是只讀的訪問和產生高速緩存線，并不臟。在高速緩存線上處理器頻繁的操作（當然，否則為什么我們有這樣的文件呢？），也就意味著每一次寫訪問后，都要廣播關于高速緩存線的改變將變得不切實際。

多年來，人們開發除了MESI緩存一致性協議(MESI=Modified, Exclusive, Shared, Invalid，變更的、獨占的、共享的、無效的)。協議的名稱來自協議中緩存線可以進入的四種狀態:

變更的: 本地處理器修改了緩存線。同時暗示，它是所有緩存中唯一的拷貝。
獨占的: 緩存線沒有被修改，而且沒有被裝入其它處理器緩存。
共享的: 緩存線沒有被修改，但可能已被裝入其它處理器緩存。
無效的: 緩存線無效，即，未被使用。

MESI協議開發了很多年，最初的版本比較簡單，但是效率也比較差。現在的版本通過以上4個狀態可以有效地實現寫回式緩存，同時支持不同處理器對只讀數據的并發訪問。

圖3.18: MESI協議的狀態躍遷圖

在協議中，通過處理器監聽其它處理器的活動，不需太多努力即可實現狀態變更。處理器將操作發布在外部引腳上，使外部可以了解到處理過程。目標的緩存線地址則可以在地址總線上看到。在下文講述狀態時，我們將介紹總線參與的時機。

一開始，所有緩存線都是空的，緩存為無效(Invalid)狀態。當有數據裝進緩存供寫入時，緩存變為變更(Modified)狀態。如果有數據裝進緩存供讀取，那么新狀態取決于其它處理器是否已經狀態了同一條緩存線。如果是，那么新狀態變成共享(Shared)狀態，否則變成獨占(Exclusive)狀態。

如果本地處理器對某條Modified緩存線進行讀寫，那么直接使用緩存內容，狀態保持不變。如果另一個處理器希望讀它，那么第一個處理器將內容發給第一個處理器，然后可以將緩存狀態置為Shared。而發給第二個處理器的數據由內存控制器接收，并放入內存中。如果這一步沒有發生，就不能將這條線置為Shared。如果第二個處理器希望的是寫，那么第一個處理器將內容發給它后，將緩存置為Invalid。這就是臭名昭著的”請求所有權(Request For Ownership,RFO)”操作。在末級緩存執行RFO操作的代價比較高。如果是寫通式緩存，還要加上將內容寫入上一層緩存或主存的時間，進一步提升了代價。 對于Shared緩存線，本地處理器的讀取操作并不需要修改狀態，而且可以直接從緩存滿足。而本地處理器的寫入操作則需要將狀態置為Modified，而且需要將緩存線在其它處理器的所有拷貝置為Invalid。因此，這個寫入操作需要通過RFO消息發通知其它處理器。如果第二個處理器請求讀取，無事發生。因為主存已經包含了當前數據，而且狀態已經為Shared。如果第二個處理器需要寫入，則將緩存線置為Invalid。不需要總線操作。

Exclusive狀態與Shared狀態很像，只有一個不同之處: 在Exclusive狀態時，本地寫入操作不需要在總線上聲明，因為本地的緩存是系統中唯一的拷貝。這是一個巨大的優勢，所以處理器會盡量將緩存線保留在Exclusive狀態，而不是Shared狀態。只有在信息不可用時，才退而求其次選擇shared。放棄Exclusive不會引起任何功能缺失，但會導致性能下降，因為E→M要遠遠快于S→M。

從以上的說明中應該已經可以看出，在多處理器環境下，哪一步的代價比較大了。填充緩存的代價當然還是很高，但我們還需要留意RFO消息。一旦涉及RFO，操作就快不起來了。

RFO在兩種情況下是必需的:

線程從一個處理器遷移到另一個處理器，需要將所有緩存線移到新處理器。
某條緩存線確實需要被兩個處理器使用。{對于同一處理器的兩個核心，也有同樣的情況，只是代價稍低。RFO消息可能會被發送多次。}

多線程或多進程的程序總是需要同步，而這種同步依賴內存來實現。因此，有些RFO消息是合理的，但仍然需要盡量降低發送頻率。除此以外，還有其它來源的RFO。在第6節中，我們將解釋這些場景。緩存一致性協議的消息必須發給系統中所有處理器。只有當協議確定已經給過所有處理器響應機會之后，才能進行狀態躍遷。也就是說，協議的速度取決于最長響應時間。{這也是現在能看到三插槽AMD Opteron系統的原因。這類系統只有三個超級鏈路(hyperlink)，其中一個連接南橋，每個處理器之間都只有一跳的距離。}總線上可能會發生沖突，NUMA系統的延時很大，突發的流量會拖慢通信。這些都是讓我們避免無謂流量的充足理由。

此外，關于多處理器還有一個問題。雖然它的影響與具體機器密切相關，但根源是唯一的——FSB是共享的。在大多數情況下，所有處理器通過唯一的總線連接到內存控制器(參見圖2.1)。如果一個處理器就能占滿總線(十分常見)，那么共享總線的兩個或四個處理器顯然只會得到更有限的帶寬。

即使每個處理器有自己連接內存控制器的總線，如圖2.2，但還需要通往內存模塊的總線。一般情況下，這種總線只有一條。退一步說，即使像圖2.2那樣不止一條，對同一個內存模塊的并發訪問也會限制它的帶寬。

對于每個處理器擁有本地內存的AMD模型來說，也是同樣的問題。的確，所有處理器可以非常快速地同時訪問它們自己的內存。但是，多線程呢？多進程呢？它們仍然需要通過訪問同一塊內存來進行同步。

對同步來說，有限的帶寬嚴重地制約著并發度。程序需要更加謹慎的設計，將不同處理器訪問同一塊內存的機會降到最低。以下的測試展示了這一點，還展示了與多線程代碼相關的其它效果。

多線程測量

為了幫助大家理解問題的嚴重性，我們來看一些曲線圖，主角也是前文的那個程序。只不過這一次，我們運行多個線程，并測量這些線程中最快那個的運行時間。也就是說，等它們全部運行完是需要更長時間的。我們用的機器有4個處理器，而測試是做多跑4個線程。所有處理器共享同一條通往內存控制器的總線，另外，通往內存模塊的總線也只有一條。

圖3.19: 順序讀操作，多線程

圖3.19展示了順序讀訪問時的性能，元素為128字節長(64位計算機，NPAD=15)。對于單線程的曲線，我們預計是與圖3.11相似，只不過是換了一臺機器，所以實際的數字會有些小差別。

更重要的部分當然是多線程的環節。由于是只讀，不會去修改內存，不會嘗試同步。但即使不需要RFO，而且所有緩存線都可共享，性能仍然分別下降了18%(雙線程)和34%(四線程)。由于不需要在處理器之間傳輸緩存，因此這里的性能下降完全由以下兩個瓶頸之一或同時引起: 一是從處理器到內存控制器的共享總線，二是從內存控制器到內存模塊的共享總線。當工作集超過L3后，三種情況下都要預取新元素，而即使是雙線程，可用的帶寬也無法滿足線性擴展(無懲罰)。

當加入修改之后，場面更加難看了。圖3.20展示了順序遞增測試的結果。

圖3.20: 順序遞增，多線程

圖中Y軸采用的是對數刻度，不要被看起來很小的差值欺騙了。現在，雙線程的性能懲罰仍然是18%，但四線程的懲罰飆升到了93%！原因在于，采用四線程時，預取的流量與寫回的流量加在一起，占滿了整個總線。

我們用對數刻度來展示L1d范圍的結果。可以發現，當超過一個線程后，L1d就無力了。單線程時，僅當工作集超過L1d時訪問時間才會超過20個周期，而多線程時，即使在很小的工作集情況下，訪問時間也達到了那個水平。

這里并沒有揭示問題的另一方面，主要是用這個程序很難進行測量。問題是這樣的，我們的測試程序修改了內存，所以本應看到RFO的影響，但在結果中，我們并沒有在L2階段看到更大的開銷。原因在于，要看到RFO的影響，程序必須使用大量內存，而且所有線程必須同時訪問同一塊內存。如果沒有大量的同步，這是很難實現的，而如果加入同步，則會占滿執行時間。

圖3.21: 隨機的Addnextlast，多線程

最后，在圖3.21中，我們展示了隨機訪問的Addnextlast測試的結果。這里主要是為了讓大家感受一下這些巨大到爆的數字。極端情況下，甚至用了1500個周期才處理完一個元素。如果加入更多線程，真是不可想象哪。我們把多線程的效能總結了一下:

#Threads	Seq Read	Seq Inc	Rand Add
2	1.69	1.69	1.54
4	2.98	2.07	1.65

表3.3: 多線程的效能

這個表展示了圖3.21中多線程運行大工作集時的效能。表中的數字表示測試程序在使用多線程處理大工作集時可能達到的最大加速因子。雙線程和四線程的理論最大加速因子分別是2和4。從表中數據來看，雙線程的結果還能接受，但四線程的結果表明，擴展到雙線程以上是沒有什么意義的，帶來的收益可以忽略不計。只要我們把圖3.21換個方式呈現，就可以很容易看清這一點。

圖3.22: 通過并行化實現的加速因子

圖3.22中的曲線展示了加速因子，即多線程相對于單線程所能獲取的性能加成值。測量值的精確度有限，因此我們需要忽略比較小的那些數字。可以看到，在L2與L3范圍內，多線程基本可以做到線性加速，雙線程和四線程分別達到了2和4的加速因子。但是，一旦工作集的大小超出L3，曲線就崩塌了，雙線程和四線程降到了基本相同的數值(參見表3.3中第4列)。也是部分由于這個原因，我們很少看到4CPU以上的主板共享同一個內存控制器。如果需要配置更多處理器，我們只能選擇其它的實現方式(參見第5節)。

可惜，上圖中的數據并不是普遍情況。在某些情況下，即使工作集能夠放入末級緩存，也無法實現線性加速。實際上，這反而是正常的，因為普通的線程都有一定的耦合關系，不會像我們的測試程序這樣完全獨立。而反過來說，即使是很大的工作集，即使是兩個以上的線程，也是可以通過并行化受益的，但是需要程序員的聰明才智。我們會在第6節進行一些介紹。

特例: 超線程

由CPU實現的超線程(有時又叫對稱多線程，SMT)是一種比較特殊的情況，每個線程并不能真正并發地運行。它們共享著除寄存器外的絕大多數處理資源。每個核心和CPU仍然是并行工作的，但核心上的線程則受到這個限制。理論上，每個核心可以有大量線程，不過到目前為止，Intel的CPU最多只有兩個線程。CPU負責對各線程進行時分復用，但這種復用本身并沒有多少厲害。它真正的優勢在于，CPU可以在當前運行的超線程發生延遲時，調度另一個線程。這種延遲一般由內存訪問引起。

如果兩個線程運行在一個超線程核心上，那么只有當兩個線程合起來的運行時間少于單線程運行時間時，效率才會比較高。我們可以將通常先后發生的內存訪問疊合在一起，以實現這個目標。有一個簡單的計算公式，可以幫助我們計算如果需要某個加速因子，最少需要多少的緩存命中率。

程序的執行時間可以通過一個只有一級緩存的簡單模型來進行估算(參見[htimpact]):

Texe= N[(1-Fmem)Tproc+ Fmem(GhitTcache+ (1-Ghit)Tmiss)]

各變量的含義如下:

N	=	指令數
Fmem	=	N中訪問內存的比例
Ghit	=	命中緩存的比例
Tproc	=	每條指令所用的周期數
Tcache	=	緩存命中所用的周期數
Tmiss	=	緩沖未命中所用的周期數
Texe	=	程序的執行時間

為了讓任何判讀使用雙線程，兩個線程之中任一線程的執行時間最多為單線程指令的一半。兩者都有一個唯一的變量緩存命中數。 如果我們要解決最小緩存命中率相等的問題需要使我們獲得的線程的執行率不少于50%或更多，如圖 3.23.

圖3.23: 最小緩存命中率-加速

X軸表示單線程指令的緩存命中率Ghit，Y軸表示多線程指令所需的緩存命中率。這個值永遠不能高于單線程命中率，否則，單線程指令也會使用改良的指令。為了使單線程的命中率在低于55%的所有情況下優于使用多線程，cup要或多或少的足夠空閑因為緩存丟失會運行另外一個超線程。

綠色區域是我們的目標。如果線程的速度沒有慢過50%，而每個線程的工作量只有原來的一半，那么它們合起來的耗時應該會少于單線程的耗時。對我們用的示例系統來說(使用超線程的P4機器)，如果單線程代碼的命中率為60%，那么多線程代碼至少要達到10%才能獲得收益。這個要求一般來說還是可以做到的。但是，如果單線程代碼的命中率達到了95%，那么多線程代碼要做到80%才行。這就很難了。而且，這里還涉及到超線程，在兩個超線程的情況下，每個超線程只能分到一半的有效緩存。因為所有超線程是使用同一個緩存來裝載數據的，如果兩個超線程的工作集沒有重疊，那么原始的95%也會被打對折——47%，遠低于80%。

因此，超線程只在某些情況下才比較有用。單線程代碼的緩存命中率必須低到一定程度，從而使緩存容量變小時新的命中率仍能滿足要求。只有在這種情況下，超線程才是有意義的。在實踐中，采用超線程能否獲得更快的結果，取決于處理器能否有效地將每個進程的等待時間與其它進程的執行時間重疊在一起。并行化也需要一定的開銷，需要加到總的運行時間里，這個開銷往往是不能忽略的。

在6.3.4節中，我們會介紹一種技術，它將多個線程通過公用緩存緊密地耦合起來。這種技術適用于許多場合，前提是程序員們樂意花費時間和精力擴展自己的代碼。

如果兩個超線程執行完全不同的代碼(兩個線程就像被當成兩個處理器，分別執行不同進程)，那么緩存容量就真的會降為一半，導致緩沖未命中率大為攀升，這一點應該是很清楚的。這樣的調度機制是很有問題的，除非你的緩存足夠大。所以，除非程序的工作集設計得比較合理，能夠確實從超線程獲益，否則還是建議在BIOS中把超線程功能關掉。{我們可能會因為另一個原因開啟超線程，那就是調試，因為SMT在查找并行代碼的問題方面真的非常好用。}

3.3.5 其它細節

我們已經介紹了地址的組成，即標簽、集合索引和偏移三個部分。那么，實際會用到什么樣的地址呢？目前，處理器一般都向進程提供虛擬地址空間，意味著我們有兩種不同的地址: 虛擬地址和物理地址。

虛擬地址有個問題——并不唯一。隨著時間的變化，虛擬地址可以變化，指向不同的物理地址。同一個地址在不同的進程里也可以表示不同的物理地址。那么，是不是用物理地址會比較好呢？

問題是，處理器指令用的虛擬地址，而且需要在內存管理單元(MMU)的協助下將它們翻譯成物理地址。這并不是一個很小的操作。在執行指令的管線(pipeline)中，物理地址只能在很后面的階段才能得到。這意味著，緩存邏輯需要在很短的時間里判斷地址是否已被緩存過。而如果可以使用虛擬地址，緩存查找操作就可以更早地發生，一旦命中，就可以馬上使用內存的內容。結果就是，使用虛擬內存后，可以讓管線把更多內存訪問的開銷隱藏起來。

處理器的設計人員們現在使用虛擬地址來標記第一級緩存。這些緩存很小，很容易被清空。在進程頁表樹發生變更的情況下，至少是需要清空部分緩存的。如果處理器擁有指定變更地址范圍的指令，那么可以避免緩存的完全刷新。由于一級緩存L1i及L1d的時延都很小(~3周期)，基本上必須使用虛擬地址。

對于更大的緩存，包括L2和L3等，則需要以物理地址作為標簽。因為這些緩存的時延比較大，虛擬到物理地址的映射可以在允許的時間里完成，而且由于主存時延的存在，重新填充這些緩存會消耗比較長的時間，刷新的代價比較昂貴。

一般來說，我們并不需要了解這些緩存處理地址的細節。我們不能更改它們，而那些可能影響性能的因素，要么是應該避免的，要么是有很高代價的。填滿緩存是不好的行為，緩存線都落入同一個集合，也會讓緩存早早地出問題。對于后一個問題，可以通過緩存虛擬地址來避免，但作為一個用戶級程序，是不可能避免緩存物理地址的。我們唯一可以做的，是盡最大努力不要在同一個進程里用多個虛擬地址映射同一個物理地址。

另一個細節對程序員們來說比較乏味，那就是緩存的替換策略。大多數緩存會優先逐出最近最少使用(Least Recently Used,LRU)的元素。這往往是一個效果比較好的策略。在關聯性很大的情況下(隨著以后核心數的增加，關聯性勢必會變得越來越大)，維護LRU列表變得越來越昂貴，于是我們開始看到其它的一些策略。

在緩存的替換策略方面，程序員可以做的事情不多。如果緩存使用物理地址作為標簽，我們是無法找出虛擬地址與緩存集之間關聯的。有可能會出現這樣的情形: 所有邏輯頁中的緩存線都映射到同一個緩存集，而其它大部分緩存卻空閑著。即使有這種情況，也只能依靠OS進行合理安排，避免頻繁出現。

虛擬化的出現使得這一切變得更加復雜。現在不僅操作系統可以控制物理內存的分配。虛擬機監視器（VMM，也稱為hypervisor）也負責分配內存。

對程序員來說，最好 a) 完全使用邏輯內存頁面b) 在有意義的情況下，使用盡可能大的頁面大小來分散物理地址。更大的頁面大小也有其他好處，不過這是另一個話題（見第4節）。

3.4 指令緩存

其實，不光處理器使用的數據被緩存，它們執行的指令也是被緩存的。只不過，指令緩存的問題相對來說要少得多，因為:

執行的代碼量取決于代碼大小。而代碼大小通常取決于問題復雜度。問題復雜度則是固定的。
程序的數據處理邏輯是程序員設計的，而程序的指令卻是編譯器生成的。編譯器的作者知道如何生成優良的代碼。
程序的流向比數據訪問模式更容易預測。現如今的CPU很擅長模式檢測，對預取很有利。
代碼永遠都有良好的時間局部性和空間局部性。

有一些準則是需要程序員們遵守的，但大都是關于如何使用工具的，我們會在第6節介紹它們。而在這里我們只介紹一下指令緩存的技術細節。

隨著CPU的核心頻率大幅上升，緩存與核心的速度差越拉越大，CPU的處理開始管線化。也就是說，指令的執行分成若干階段。首先，對指令進行解碼，隨后，準備參數，最后，執行它。這樣的管線可以很長(例如，Intel的Netburst架構超過了20個階段)。在管線很長的情況下，一旦發生延誤(即指令流中斷)，需要很長時間才能恢復速度。管線延誤發生在這樣的情況下: 下一條指令未能正確預測，或者裝載下一條指令耗時過長(例如，需要從內存讀取時)。

為了解決這個問題，CPU的設計人員們在分支預測上投入大量時間和芯片資產(chip real estate)，以降低管線延誤的出現頻率。

在CISC處理器上，指令的解碼階段也需要一些時間。x86及x86-64處理器尤為嚴重。近年來，這些處理器不再將指令的原始字節序列存入L1i，而是緩存解碼后的版本。這樣的L1i被叫做“追蹤緩存(trace cache)”。追蹤緩存可以在命中的情況下讓處理器跳過管線最初的幾個階段，在管線發生延誤時尤其有用。

前面說過，L2以上的緩存是統一緩存，既保存代碼，也保存數據。顯然，這里保存的代碼是原始字節序列，而不是解碼后的形式。

在提高性能方面，與指令緩存相關的只有很少的幾條準則:

生成盡量少的代碼。也有一些例外，如出于管線化的目的需要更多的代碼，或使用小代碼會帶來過高的額外開銷。
盡量幫助處理器作出良好的預取決策，可以通過代碼布局或顯式預取來實現。

這些準則一般會由編譯器的代碼生成階段強制執行。至于程序員可以參與的部分，我們會在第6節介紹。

3.4.1 自修改的代碼

在計算機的早期歲月里，內存十分昂貴。人們想盡千方百計，只為了盡量壓縮程序容量，給數據多留一些空間。其中，有一種方法是修改程序自身，稱為自修改代碼(SMC)。現在，有時候我們還能看到它，一般是出于提高性能的目的，也有的是為了攻擊安全漏洞。

一般情況下，應該避免SMC。雖然一般情況下沒有問題，但有時會由于執行錯誤而出現性能問題。顯然，發生改變的代碼是無法放入追蹤緩存(追蹤緩存放的是解碼后的指令)的。即使沒有使用追蹤緩存(代碼還沒被執行或有段時間沒執行)，處理器也可能會遇到問題。如果某個進入管線的指令發生了變化，處理器只能扔掉目前的成果，重新開始。在某些情況下，甚至需要丟棄處理器的大部分狀態。

最后，由于處理器認為代碼頁是不可修改的(這是出于簡單化的考慮，而且在99.9999999%情況下確實是正確的)，L1i用到并不是MESI協議，而是一種簡化后的SI協議。這樣一來，如果萬一檢測到修改的情況，就需要作出大量悲觀的假設。

因此，對于SMC，強烈建議能不用就不用。現在內存已經不再是一種那么稀缺的資源了。最好是寫多個函數，而不要根據需要把一個函數改來改去。也許有一天可以把SMC變成可選項，我們就能通過這種方式檢測入侵代碼。如果一定要用SMC，應該讓寫操作越過緩存，以免由于L1i需要L1d里的數據而產生問題。更多細節，請參見6.1節。

在Linux上，判斷程序是否包含SMC是很容易的。利用正常工具鏈(toolchain)構建的程序代碼都是寫保護(write-protected)的。程序員需要在鏈接時施展某些關鍵的魔術才能生成可寫的代碼頁。現代的Intel x86和x86-64處理器都有統計SMC使用情況的專用計數器。通過這些計數器，我們可以很容易判斷程序是否包含SMC，即使它被準許運行。

3.5 緩存未命中的因素

我們已經看過內存訪問沒有命中緩存時，那陡然猛漲的高昂代價。但是有時候，這種情況又是無法避免的，因此我們需要對真正的代價有所認識，并學習如何緩解這種局面。

3.5.1 緩存與內存帶寬

為了更好地理解處理器的能力，我們測量了各種理想環境下能夠達到的帶寬值。由于不同處理器的版本差別很大，所以這個測試比較有趣，也因為如此，這一節都快被測試數據灌滿了。我們使用了x86和x86-64處理器的SSE指令來裝載和存儲數據，每次16字節。工作集則與其它測試一樣，從1kB增加到512MB，測量的具體對象是每個周期所處理的字節數。

圖3.24: P4的帶寬

圖3.24展示了一顆64位Intel Netburst處理器的性能圖表。當工作集能夠完全放入L1d時，處理器的每個周期可以讀取完整的16字節數據，即每個周期執行一條裝載指令(moveaps指令，每次移動16字節的數據)。測試程序并不對數據進行任何處理，只是測試讀取指令本身。當工作集增大，無法再完全放入L1d時，性能開始急劇下降，跌至每周期6字節。在218工作集處出現的臺階是由于DTLB緩存耗盡，因此需要對每個新頁施加額外處理。由于這里的讀取是按順序的，預取機制可以完美地工作，而FSB能以5.3字節/周期的速度傳輸內容。但預取的數據并不進入L1d。當然，真實世界的程序永遠無法達到以上的數字，但我們可以將它們看作一系列實際上的極限值。

更令人驚訝的是寫操作和復制操作的性能。即使是在很小的工作集下，寫操作也始終無法達到4字節/周期的速度。這意味著，Intel為Netburst處理器的L1d選擇了寫通(write-through)模式，所以寫入性能受到L2速度的限制。同時，這也意味著，復制測試的性能不會比寫入測試差太多(復制測試是將某塊內存的數據拷貝到另一塊不重疊的內存區)，因為讀操作很快，可以與寫操作實現部分重疊。最值得關注的地方是，兩個操作在工作集無法完全放入L2后出現了嚴重的性能滑坡，降到了0.5字節/周期！比讀操作慢了10倍！顯然，如果要提高程序性能，優化這兩個操作更為重要。

再來看圖3.25，它來自同一顆處理器，只是運行雙線程，每個線程分別運行在處理器的一個超線程上。

圖3.25: P4開啟兩個超線程時的帶寬表現

圖3.25采用了與圖3.24相同的刻度，以方便比較兩者的差異。圖3.25中的曲線抖動更多，是由于采用雙線程的緣故。結果正如我們預期，由于超線程共享著幾乎所有資源(僅除寄存器外)，所以每個超線程只能得到一半的緩存和帶寬。所以，即使每個線程都要花上許多時間等待內存，從而把執行時間讓給另一個線程，也是無濟于事——因為另一個線程也同樣需要等待。這里恰恰展示了使用超線程時可能出現的最壞情況。

圖3.26: Core 2的帶寬表現

再來看Core 2處理器的情況。看看圖3.26和圖3.27，再對比下P4的圖3.24和3.25，可以看出不小的差異。Core 2是一顆雙核處理器，有著共享的L2，容量是P4 L2的4倍。但更大的L2只能解釋寫操作的性能下降出現較晚的現象。

當然還有更大的不同。可以看到，讀操作的性能在整個工作集范圍內一直穩定在16字節/周期左右，在220處的下降同樣是由于DTLB的耗盡引起。能夠達到這么高的數字，不但表明處理器能夠預取數據，并且按時完成傳輸，而且還意味著，預取的數據是被裝入L1d的。

寫/復制操作的性能與P4相比，也有很大差異。處理器沒有采用寫通策略，寫入的數據留在L1d中，只在必要時才逐出。這使得寫操作的速度可以逼近16字節/周期。一旦工作集超過L1d，性能即飛速下降。由于Core 2讀操作的性能非常好，所以兩者的差值顯得特別大。當工作集超過L2時，兩者的差值甚至超過20倍！但這并不表示Core 2的性能不好，相反，Core 2永遠都比Netburst強。

圖3.27: Core 2運行雙線程時的帶寬表現

在圖3.27中，啟動雙線程，各自運行在Core 2的一個核心上。它們訪問相同的內存，但不需要完美同步。從結果上看，讀操作的性能與單線程并無區別，只是多了一些多線程情況下常見的抖動。

有趣的地方來了——當工作集小于L1d時，寫操作與復制操作的性能很差，就好像數據需要從內存讀取一樣。兩個線程彼此競爭著同一個內存位置，于是不得不頻頻發送RFO消息。問題的根源在于，雖然兩個核心共享著L2，但無法以L2的速度處理RFO請求。而當工作集超過L1d后，性能出現了迅猛提升。這是因為，由于L1d容量不足，于是將被修改的條目刷新到共享的L2。由于L1d的未命中可以由L2滿足，只有那些尚未刷新的數據才需要RFO，所以出現了這樣的現象。這也是這些工作集情況下速度下降一半的原因。這種漸進式的行為也與我們期待的一致:由于每個核心共享著同一條FSB，每個核心只能得到一半的FSB帶寬，因此對于較大的工作集來說，每個線程的性能大致相當于單線程時的一半。

由于同一個廠商的不同處理器之間都存在著巨大差異，我們沒有理由不去研究一下其它廠商處理器的性能。圖3.28展示了AMD家族10h Opteron處理器的性能。這顆處理器有64kB的L1d、512kB的L2和2MB的L3，其中L3緩存由所有核心所共享。

圖3.28: AMD家族10h Opteron的帶寬表現

大家首先應該會注意到，在L1d緩存足夠的情況下，這個處理器每個周期能處理兩條指令。讀操作的性能超過了32字節/周期，寫操作也達到了18.7字節/周期。但是，不久，讀操作的曲線就急速下降，跌到2.3字節/周期，非常差。處理器在這個測試中并沒有預取數據，或者說，沒有有效地預取數據。

另一方面，寫操作的曲線隨幾級緩存的容量而流轉。在L1d階段達到最高性能，隨后在L2階段下降到6字節/周期，在L3階段進一步下降到2.8字節/周期，最后，在工作集超過L3后，降到0.5字節/周期。它在L1d階段超過了Core 2，在L2階段基本相當(Core 2的L2更大一些)，在L3及主存階段比Core 2慢。

復制的性能既無法超越讀操作的性能，也無法超越寫操作的性能。因此，它的曲線先是被讀性能壓制，隨后又被寫性能壓制。

圖3.29顯示的是Opteron處理器在多線程時的性能表現。

圖3.29: AMD Fam 10h在雙線程時的帶寬表現

讀操作的性能沒有受到很大的影響。每個線程的L1d和L2表現與單線程下相仿，L3的預取也依然表現不佳。兩個線程并沒有過渡爭搶L3。問題比較大的是寫操作的性能。兩個線程共享的所有數據都需要經過L3，而這種共享看起來卻效率很差。即使是在L3足夠容納整個工作集的情況下，所需要的開銷仍然遠高于L3的訪問時間。再來看圖3.27，可以發現，在一定的工作集范圍內，Core 2處理器能以共享的L2緩存的速度進行處理。而Opteron處理器只能在很小的一個范圍內實現相似的性能，而且，它僅僅只能達到L3的速度，無法與Core 2的L2相比。

3.5.2 關鍵字加載

內存以比緩存線還小的塊從主存儲器向緩存傳送。如今64位可一次性傳送，緩存線的大小為64或128比特。這意味著每個緩存線需要8或16次傳送。

DRAM芯片可以以觸發模式傳送這些64位的塊。這使得不需要內存控制器的進一步指令和可能伴隨的延遲，就可以將緩存線充滿。如果處理器預取了緩存，這有可能是最好的操作方式。

如果程序在訪問數據或指令緩存時沒有命中(這可能是強制性未命中或容量性未命中，前者是由于數據第一次被使用，后者是由于容量限制而將緩存線逐出)，情況就不一樣了。程序需要的并不總是緩存線中的第一個字，而數據塊的到達是有先后順序的，即使是在突發模式和雙倍傳輸率下，也會有明顯的時間差，一半在4個CPU周期以上。舉例來說，如果程序需要緩存線中的第8個字，那么在首字抵達后它還需要額外等待30個周期以上。

當然，這樣的等待并不是必需的。事實上，內存控制器可以按不同順序去請求緩存線中的字。當處理器告訴它，程序需要緩存中具體某個字，即「關鍵字(critical word)」時，內存控制器就會先請求這個字。一旦請求的字抵達，雖然緩存線的剩余部分還在傳輸中，緩存的狀態還沒有達成一致，但程序已經可以繼續運行。這種技術叫做關鍵字優先及較早重啟(Critical Word First & Early Restart)。

現在的處理器都已經實現了這一技術，但有時無法運用。比如，預取操作的時候，并不知道哪個是關鍵字。如果在預取的中途請求某條緩存線，處理器只能等待，并不能更改請求的順序。

圖3.30: 關鍵字位于緩存線尾時的表現

在關鍵字優先技術生效的情況下，關鍵字的位置也會影響結果。圖3.30展示了下一個測試的結果，圖中表示的是關鍵字分別在線首和線尾時的性能對比情況。元素大小為64字節，等于緩存線的長度。圖中的噪聲比較多，但仍然可以看出，當工作集超過L2后，關鍵字處于線尾情況下的性能要比線首情況下低0.7%左右。而順序訪問時受到的影響更大一些。這與我們前面提到的預取下條線時可能遇到的問題是相符的。

3.5.3 緩存設定

緩存放置的位置與超線程，內核和處理器之間的關系，不在程序員的控制范圍之內。但是程序員可以決定線程執行的位置，接著高速緩存與使用的CPU的關系將變得非常重要。

這里我們將不會深入（探討）什么時候選擇什么樣的內核以運行線程的細節。我們僅僅描述了在設置關聯線程的時候，程序員需要考慮的系統結構的細節。

超線程，通過定義，共享除去寄存器集以外的所有數據。包括 L1 緩存。這里沒有什么可以多說的。多核處理器的獨立核心帶來了一些樂趣。每個核心都至少擁有自己的 L1 緩存。除此之外，下面列出了一些不同的特性：

早期多核心處理器有獨立的 L2 緩存且沒有更高層級的緩存。
之后英特爾的雙核心處理器模型擁有共享的L2 緩存。對四核處理器，則分對擁有獨立的L2 緩存，且沒有更高層級的緩存。
AMD 家族的 10h 處理器有獨立的 L2 緩存以及一個統一的L3 緩存。

關于各種處理器模型的優點，已經在它們各自的宣傳手冊里寫得夠多了。在每個核心的工作集互不重疊的情況下，獨立的L2擁有一定的優勢，單線程的程序可以表現優良。考慮到目前實際環境中仍然存在大量類似的情況，這種方法的表現并不會太差。不過，不管怎樣，我們總會遇到工作集重疊的情況。如果每個緩存都保存著某些通用運行庫的常用部分，那么很顯然是一種浪費。

如果像Intel的雙核處理器那樣，共享除L1外的所有緩存，則會有一個很大的優點。如果兩個核心的工作集重疊的部分較多，那么綜合起來的可用緩存容量會變大，從而允許容納更大的工作集而不導致性能的下降。如果兩者的工作集并不重疊，那么則是由Intel的高級智能緩存管理(Advanced Smart Cache management)發揮功用，防止其中一個核心壟斷整個緩存。

即使每個核心只使用一半的緩存，也會有一些摩擦。緩存需要不斷衡量每個核心的用量，在進行逐出操作時可能會作出一些比較差的決定。我們來看另一個測試程序的結果。

圖3.31: 兩個進程的帶寬表現

這次，測試程序兩個進程，第一個進程不斷用SSE指令讀/寫2MB的內存數據塊，選擇2MB，是因為它正好是Core 2處理器L2緩存的一半，第二個進程則是讀/寫大小變化的內存區域，我們把這兩個進程分別固定在處理器的兩個核心上。圖中顯示的是每個周期讀/寫的字節數，共有4條曲線，分別表示不同的讀寫搭配情況。例如，標記為讀/寫(read/write)的曲線代表的是后臺進程進行寫操作(固定2MB工作集)，而被測量進程進行讀操作(工作集從小到大)。

圖中最有趣的是220到223之間的部分。如果兩個核心的L2是完全獨立的，那么所有4種情況下的性能下降均應發生在221到222之間，也就是L2緩存耗盡的時候。但從圖上來看，實際情況并不是這樣，特別是背景進程進行寫操作時尤為明顯。當工作集達到1MB(220)時，性能即出現惡化，兩個進程并沒有共享內存，因此并不會產生RFO消息。所以，完全是緩存逐出操作引起的問題。目前這種智能的緩存處理機制有一個問題，每個核心能實際用到的緩存更接近1MB，而不是理論上的2MB。如果未來的處理器仍然保留這種多核共享緩存模式的話，我們唯有希望廠商會把這個問題解決掉。

推出擁有雙L2緩存的4核處理器僅僅只是一種臨時措施，是開發更高級緩存之前的替代方案。與獨立插槽及雙核處理器相比，這種設計并沒有帶來多少性能提升。兩個核心是通過同一條總線(被外界看作FSB)進行通信，并沒有什么特別快的數據交換通道。

未來，針對多核處理器的緩存將會包含更多層次。AMD的10h家族是一個開始，至于會不會有更低級共享緩存的出現，還需要我們拭目以待。我們有必要引入更多級別的緩存，因為頻繁使用的高速緩存不可能被許多核心共用，否則會對性能造成很大的影響。我們也需要更大的高關聯性緩存，它們的數量、容量和關聯性都應該隨著共享核心數的增長而增長。巨大的L3和適度的L2應該是一種比較合理的選擇。L3雖然速度較慢，但也較少使用。

對于程序員來說，不同的緩存設計就意味著調度決策時的復雜性。為了達到最高的性能，我們必須掌握工作負載的情況，必須了解機器架構的細節。好在我們在判斷機器架構時還是有一些支援力量的，我們會在后面的章節介紹這些接口。

3.5.4 FSB的影響

FSB在性能中扮演了核心角色。緩存數據的存取速度受制于內存通道的速度。我們做一個測試，在兩臺機器上分別跑同一個程序，這兩臺機器除了內存模塊的速度有所差異，其它完全相同。圖3.32展示了Addnext0測試(將下一個元素的pad[0]加到當前元素的pad[0]上)在這兩臺機器上的結果(NPAD=7，64位機器)。兩臺機器都采用Core 2處理器，一臺使用667MHz的DDR2內存，另一臺使用800MHz的DDR2內存(比前一臺增長20%)。

圖3.32: FSB速度的影響

圖上的數字表明，當工作集大到對FSB造成壓力的程度時，高速FSB確實會帶來巨大的優勢。在我們的測試中，性能的提升達到了18.5%，接近理論上的極限。而當工作集比較小，可以完全納入緩存時，FSB的作用并不大。當然，這里我們只測試了一個程序的情況，在實際環境中，系統往往運行多個進程，工作集是很容易超過緩存容量的。

如今，一些英特爾的處理器，支持前端總線(FSB)的速度高達1,333 MHz，這意味著速度有另外60％的提升。將來還會出現更高的速度。速度是很重要的，工作集會更大，快速的RAM和高FSB速度的內存肯定是值得投資的。我們必須小心使用它，因為即使處理器可以支持更高的前端總線速度，但是主板的北橋芯片可能不會。使用時，檢查它的規范是至關重要的。

總結

以上是生活随笔為你收集整理的每个程序员都应该了解的 CPU 高速缓存的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。