原文PDF: http://futuretech.blinkenlights.nl/misc/cpumemory.pdf
一二章參考博文：
圖3.1：最小緩存配置
圖3.1展示了最小緩存系統的布局。它是早期系統對CPU緩存部署的構架。CPU核不再直接和主存連接配接，所有的存儲和讀取都通過緩存進行。CPU核和緩存之間的連接配接是快速連接配接。為了簡化表達，主存和緩存都連接配接到總線上，總線可以和其他系統元件通信。我們把系統總線稱為“FSB”，這個概念沿用至今，參考第2.2節。在這一節中我們忽略北橋，假設它的存在是促進CPU和主存的通信。
盡管過去的數十年，大多數計算機使用馮諾依曼體系結構，總結以往經驗說明将指令和資料使用的緩存獨立開是有優勢的。因特爾自從1993年就将指令和資料緩存分開，這樣指令和資料需要的記憶體區域更加獨立。近年來，又出現了另外一個優勢：對于多數處理器指令譯碼的速度慢，緩存譯碼指令可以加快指令的執行，尤其是當管道由于錯誤的預測為空時。
在引入緩存後系統得更加複雜了。主存和緩存的速度有明顯的差別，增加了另一級緩存，它比一級緩存大且慢。僅僅增加一級緩存的大小出于經濟的考慮是不可取的。如今，有的機器通常使用三級緩存，這樣的系統如圖3.2。随着單CPU中核的數量的增加，進階緩存的數量也會在以後增加更多。
圖3.2 三級緩存處理器
圖3.2展示了三級緩存，并引入了幾個術語将在後面的文章中使用。L1d是一級資料緩存，L1i是一級指令緩存等。注意這是一個示意圖，真實的情況資料流從CPU核到主存不需要經過任何進階緩存。CPU設計者在設計緩存接口的時候有很大的自由度，對于程式開發者而言這些設計是不可見的。
另外，處理器有多核，一個核可以擁有多個線程。核和線程之間的差別是不同的核對硬體資源有單獨的一份拷貝，核可以完全獨立的運作除非它們使用共同的資源。線程共享幾乎所有的處理器資源。英特爾對線程的實作僅僅擁有獨立的寄存器但也是有限的，有些寄存器也是共享的。現代CPU模型參考圖3.3。
圖3.3 多處理器，多核，多線程
圖3.3中有兩個處理器，每個處理器有兩個核，每個核有兩個線程。線程共享一級緩存。每個核擁有獨立的一級緩存，所有的CPU核共享更進階的緩存。兩個處理器不共享任何的緩存。這些概念比較重要尤其是對後面讨論的緩存對多處理器和多線程應用程式的影響。
3.2 進階緩存操作
為了了解使用緩存的開銷和效率，我們必須将第2節中關于機器架構和RAM技術的知識與前一節中描述的緩存結構結合起來。
預設情況下，由CPU核讀取和寫入的所有資料都存儲在緩存中。有些記憶體區域不能被緩存但這是隻有OS實作者才去考慮的事情，對于應用程式開發者不需要考慮。還有些指令運作程式員故意繞過某些緩存。這将在第6章講述。
如果CPU需要一資料字首先在緩存中搜尋，很明顯緩存不可能容納整個主存中的所有内容否則也就不需要緩存了。但是由于所有的記憶體位址都是可緩存的，每個緩存條目在主存中都是通過資料字的位址進行标記的。通過這種方式，對位址的讀寫請求可以在緩存中搜尋比對的标記。這個上下文中的位址可以是虛拟位址，也可以是實體位址，随緩存實作的不同而不同。
由于标記也需要額外的記憶體，所有用一個字作為緩存的粒度是低效的。對于一個字32位元組的X86機器标記自己就需要32位甚至更多位來表示。而且，空間局部性是緩存基本的原則之一，是以需要考慮這個問題。由于相鄰的記憶體很可能被同時使用，是以應該将它們一起加載進緩存。記得2.2.1節我們所學的内容：RAM模式在沒有新的CAS和RAS信号時以行傳輸更多的資料字将會更高效。是以存儲在緩存的條目是以行為粒度的多個連續的資料字。在早期的緩存中，這些行是以32位元組為長度，現在通常是64位元組。如果記憶體總線是64位（8位元組）寬意味着每個緩存行有8次傳輸，DDR能夠更有效的傳輸。
當處理器需要記憶體中的内容整個緩存行被加載到L1d。每個緩存行的記憶體位址是根據高速緩存行的大小和位址值計算的掩碼。對于64位元組的緩存行意味着低6位被置0（2^6 = 64），這6位用來表示在一個緩存行裡的偏移。剩下的位元組有些情況被用來定位該行在緩存的位置和作為一個标簽。在實踐中，位址值被分為3個部分。對于32位的位址可能如下劃分：
低O位被用來作為緩存行的行内偏移。下個S位用來選擇緩存組（了解為一個緩存組包括很多緩存行）。現在能夠了解為該緩存中有2^S個緩存組。剩下的T位構成了标簽。這些标簽位用來區分同一個緩存組裡不同的緩存行。同一個緩存組的不同緩存行的S值是相同的是以不需要存儲。
當一條指令修改記憶體，雖然沒有一條指令同時修改一整個緩存行的内容，處理器任然需要加載一個緩存行。寫入操作之前的緩存行的内容必須被加載。緩存不可能隻持有部分緩存行内容，一個緩存行已經被寫入但是沒有更新到主存中，緩存行标記為髒的，一旦寫入主存就将髒的标記清除。
為了能夠加載新的資料到緩存中需要在緩存中為其開辟空間。如果一級緩存空間不足，将L1d緩存行内容向下驅逐到2級緩存，同樣2級也可以向下驅逐到3級緩存最後存儲到主存中。每次驅逐的代價都越來越大，這裡描述的是現代AMD和VIA處理器首選的獨占緩存模型。Intel實作了包容性緩存 L1d中的每條緩存行在L2中也都有。是以從L1d驅逐更快速。擁有足夠大的2級緩存在兩個地方存儲同樣内容的資源浪費的劣勢将減小并且在驅逐的時候得到益處。獨占式緩存可能的優勢是加載一個新的緩存行僅僅需要和L1d接觸不需要和L2，可能更快。
隻要為處理器架構設定的記憶體模型沒有改變，允許CPU用它們喜歡的模式管理緩存。舉例說明，處理器利用很少或沒有記憶體總線活動的時機将髒的緩存行内容寫入主存中是很不錯的選擇。x86和x86-64處理器之間、制造商之間、甚至同一制造商的模型内部的各種緩存體系結構都證明了記憶體模型抽象的強大功能。
對稱多處理器系統（SMP）中，CPU的緩存不能彼此獨立的工作。所有的處理器都應該在任何時候看到相同的内容。維持這個記憶體的一緻性稱為“緩存一緻性”。如果一個處理器隻是檢視自己的緩存，主存将看不到其他處理器的髒緩存行。提供一個處理器直接通路另一個處理器的緩存将是非常昂貴且有巨大的瓶頸。取代的方案是，處理器檢測另一個處理器何時想要讀或寫某個緩存行。
如果檢測到一個寫請求，如果處理器在它的緩存中有這個緩存行的一個幹淨的副本，這個緩存行被标記為無效。将來的引用需要重新加載這個緩存行。其他處理器的讀操作不需要标記無效，可以有多個幹淨的拷貝。
複雜的緩存機制可能發生另一種情況。假設一個緩存行在一個處理器的緩存中是髒的，第二個處理器想要讀寫這個緩存行，這種情況下，主存中的内容還是舊的，第二個處理器必須從第一個處理器那擷取緩存行的内容。第一個處理器注意到這種情況自動将資料傳輸給請求的處理器。這個過程繞過了主存，盡管在一些實作機制中記憶體控制器應該注意到這次直接傳輸并更新緩存行内容到主存中。如果請求是需要寫入第一個處理器的緩存，那麼本地的緩存行的拷貝将會被設定為無效。
随着時間的推移，大量的緩存一緻性協定被開發出來。最重要的是MESI協定我們将在3.4小節講述。所有的這些可以總結以下幾點簡單的規則：
- 一個髒緩存行不會出現在其他處理器中。
- 同一緩存行的幹淨副本可以駐留在任意多個緩存中。
如果支援這些規則，就算是多處理系統也可以高效的使用緩存。所有的處理器需要做的是監控其他處理器的寫請求并且把位址和本地的緩存進行比較。在下一節中我們将詳細講述實作細節尤其是開銷細節。
最後，我們至少應該了解與緩存命中和脫靶時的開銷。以下是英特爾奔騰M的資料：
| To Where | 周期 |
| Register L1d L2 Main Memory | ≤ 1 ∼ 3 ∼ 14 ∼ 240 |
這是以CPU時鐘周期為機關的實際通路時間。
表中的數字看起來很大，但幸運的是，不必為每次緩存加載和脫靶付出全部的代價。一部分的開銷可以被抵消。如今的處理器都使用不同長度的内部管線，在内部管線内指令被譯碼和預執行。如果他們被傳輸到寄存器部分準備工作是從記憶體或緩存中加載資料。如果記憶體加載操作能夠在管線中盡早的開始，就可以和其他操作并行執行，這樣整個加載開銷可以忽略。這對于L1d通常是可能的;對于一些具有長的L2管道的處理器也是如此。
在早期開始記憶體讀有很多的障礙。這可能是由于沒有足夠的記憶體通路資源，也可能是由于另一條指令導緻加載的最終位址延遲可用。在這種情況下，加載的開銷就不能忽略了。
對于寫操作，CPU不必等到資料被安全地存儲在記憶體中。隻要下列指令的執行似乎與資料存儲在記憶體中的效果相同，就沒有什麼可以阻止CPU走捷徑。它可以提前開始執行下一條指令。在影子寄存器的幫助下，它可以儲存對正常寄存器中不可用的值，甚至可以更改要存儲在不完整的寫操作中的值。
圖3.4 随機寫的通路時間
圖3.4舉例說明了緩存機制帶來的影響。稍後我們将讨論一個資料生成的程式，這個簡單的仿真程式可以以随機的方式重複的通路一個可配置大小的記憶體。每個資料條目有固定的大小。元素的數量依賴于選的資料集大小。Y軸是處理一個元素平均的CPU周期；注意到Y軸是以對數形式劃分的。X軸是工作資料集的大小。
圖表顯示了三個不同的區域。這并不奇怪：這個處理器有L1d和L2緩存但是沒有L3。依靠經驗我們可以推斷一級緩存有2^13位元組，二級緩存有2^20位元組大小。如果整個工作資料集在一級緩存大小的範圍内，每個元素的通路時間将控制在10個時鐘周期以内。一旦超出了L1d的範圍處理器就需要從L2二級緩存加載資料，平均時間消耗上升到28個周期左右。一旦二級緩存也滿足不了時間将攀升到了480個周期甚至更多。這時候大多數操作需要從主存加載資料。更糟糕的情況是：一旦有資料被修改，髒緩存行需要寫回主存。
這個圖表應該能夠給我們足夠的動機深入探究代碼的優化來提升緩存的使用情況。我們這裡不是讨論幾個百分點的差別，讨論有時是幾個數量級提升的差別。在第6章中我們将讨論怎麼寫出更好更有效的代碼。下一節繼續深入研究CPU緩存的設計細節。
3.3 CPU緩存實作細節
緩存實作者面臨的問題是，可能必須緩存巨大主記憶體中的每個單元。如果一個程式的工作集足夠大，這意味着主記憶體中的許多條目要争奪緩存中的位置。前面提到過，緩存與主記憶體大小的比例為1比1000是比較常見的。
3.3.1 關聯性
可以實作一個緩存的每個緩存行儲存任何記憶體位置的一個拷貝，這種稱謂全關聯緩存。為了通路一個緩存行需要将請求的位址标簽和緩存的每個緩存行的标簽進行比較。标簽由整個位址組成不包括緩存行的偏移，也就是說上文提到的S為0。
有些緩存是這樣實作的，但是，通過檢視今天使用的L2的數字，将表明這是不切實際的。給定一個4M的緩存，擁有64位元組的緩存行，緩存的條目将有65536條。為了獲得足夠的性能，緩存邏輯必須能夠在幾個周期内從所有這些條目中選擇與給定标記比對的條目，實作這個的工作量是巨大的。
圖3.5 全關聯型緩存
對于每個緩存行比較器需要比較一個長标簽（因為S為0）。每個比較器需要比較T個位的值，然後比中的緩存行被選中。這需要合并盡可能多的O資料行，因為有緩存桶。實作一個比較器需要大量的半導體，因為它必須工作得非常快。在沒有疊代比較器可用的情況下，節省比較器數量的惟一方法是通過疊代比較标記來減少比較器的數量。這與疊代比較器不适合的原因是不一樣的:它花費的時間太長。
全關聯緩存适用于小型緩存(例如，某些Intel處理器上的TLB緩存是完全關聯的)，但是這些緩存非常小。我們說的最多是幾十個條目。對于L1i、L1d和更進階别的緩存，需要一種不同的方法。所能做的就是限制搜尋。在最極端的限制中，每個标記隻映射到一個緩存條目。計算很簡單:給定4MB/64B緩存和65,536個條目，我們可以使用位址的第6位到第21位(16位)直接尋址每個條目。低6位是緩存行的索引。
圖3.6 直接映射型緩存機制
這種直接映射型緩存很快并且相對容易實作。 隻需要一個比較器一個複用器（圖中用了兩個因為标簽和資料分開，但這并不是硬性要求），一些邏輯隻選擇有效的緩存線内容，比較器比較複雜，因為有速度的要求，但現在隻有一個。是以要在使比較器工作的更快速上下功夫。這種方法的真正複雜性在于多路複用器，一個簡單多路複用器中的半導體數量随O(log N)增長，N是緩存行的數量。這是可以容忍的，但可能會變慢，在這種情況下，可以通過在多路複用器上的半導體上花費更多的空間來增加速度，進而并行化一些工作并提高速度。半導體的總數可以随着緩存大小的增長而緩慢增長，這使得這個解決方案非常有吸引力。但是它有一個缺點:隻有當程式使用的位址相對于用于直接映射的位是均勻分布的時候，它才能很好地工作。如果不是這樣，通常情況下，一些緩存條目會被大量使用，會被重複地清除，而其他的則幾乎不被使用或保持為空。
圖3.7 組相關緩存機制
這個問題可以使用組相關緩存機制得到解決。這種機制結合了全相關緩存機制和直接映射緩存機制的優勢大大的避免了這些設計的缺陷。圖3.7展示了組相關緩存機制的設計。标簽和資料的存儲被分為組，一組由多個緩存行組成。這類似于直接映射緩存。但是，緩存中的每個設定值隻有一個元素，而緩存中的少量值用于相同的設定值。所有組成員的标簽都是并行比較的，這與完全關聯緩存的功能類似。
其結果是緩存不容易被具有相同緩存行的組錯誤的或故意選擇的位址擊敗，同時緩存的大小不受可經濟實作的比較器數量的限制。如果緩存增長，它隻是(在圖中)增加的列數，而不是行數。隻有當緩存的關聯度增加時，行數(以及比較器)才會增加。現在的處理器對L2或更高的緩存使用最多24級的結合度。L1緩存通常需要8組資料。
表3.1 緩存大小的影響，關聯性，和行大小
給定4MB和64位，8路組相關緩存，有8192個組标簽中僅僅13位用于組位址尋找。決定緩存組中的哪個條目包含尋址的緩存行，必須比較8個标簽。這可以在很短的時間内完成。
表3.1展示了二級緩存随着緩存大小，緩存行的大小和關聯組大小的變化沒命中的數量的變化。在7.2節我們将介紹一個工具來模拟測試中需要的緩存。這些值的關系是緩存大小 = 緩存行大小 x 關聯(一組多少個緩存行) x 組數量
O = log2 cache line size
S = log2 number of sets
圖3.8 緩存大小 VS 關聯性 （CL = 32）
圖3.8 使得表3.1的資料更直覺。緩存行的大小固定為32位元組，檢視給定緩存大小的數字，我們可以看到，關聯性确實有助于顯著減少緩存脫靶的數量。對于8MB的緩存，從直接映射到2路組關聯緩存幾乎可以節省44%的緩存脫靶。與直接映射緩存相比，使用組關聯緩存的處理器可以在緩存中保留更多的工作集。
在文獻中，我們偶爾會讀到引入關聯性與将緩存大小加倍具有相同的效果。在某些極端情況下确實如此，從4MB到8MB緩存的跳轉就可以看出這一點，但對于關聯性的進一步倍增，肯定不是這樣的，正如我們從資料中看到的那樣，連續的上漲脫靶率變化很小。然而，我們不應該完全忽視其影響。在示例程式中，峰值記憶體使用為5.6M。是以，對于一個8MB的緩存，對于相同的緩存集不太可能有很多(多于兩個)的使用。對于一個較大的工作集，節省的空間可能會更大，這可以從較小的緩存大小帶來的更大的相聯性好處中看出。
通常，将緩存的關聯度提高到8以上對單線程工作負載的影響似乎很小。随着超線程處理器的引入，第一級緩存是共享的，多核處理器使用共享的L2緩存，情況發生了變化。現在，您基本上有兩個程式在相同的緩存上，這導緻了在實踐中的關聯性減半(或四核處理器的四分之一)。是以，可以預期，随着核心數量的增加，共享緩存的結合性應該會增加。一旦這是不可能的(16路集關聯性已經很困難了)，處理器設計者就必須開始使用共享的L3緩存，而L2緩存則可能由核心的子集共享。
圖3.8中我們可以研究的另一個影響是緩存大小的增加如何有助于提高性能。這些資料不能解釋在不知道工作集時的情況。很顯然，與主存同樣大小的緩存比小的緩存能獲得更好的結果，是以緩存的大小通常是沒有限制的。
之前提到的工作集的最高峰是5.6M，這并不能告訴我們最大的有效的緩存的絕對大小，但是允許我們做個估計。問題是并不是所有的使用的記憶體都是連續的，是以即使是16M的緩存和5.6M的工作集也是有沖突的。但是可以肯定的是，在相同的工作負載下，32MB緩存的好處可以忽略不計。但誰說工作環境必須保持不變呢?工作負載随着時間的推移而增長，緩存的大小也應如此。在購買機器時，必須選擇願意購買的緩存大小，是以測量工作集大小是值得的。
圖3.9 測試記憶體分布
跑兩種類型的測試。第一種測試按順序處理元素。 測試程式跟随指針n但是數組元素是連結起來的是以他們在記憶體中是按照順序周遊的，如圖3.9的下半部分。第二種測試是随機周遊，如3.9圖的上半部分。兩種測試數組元素都是循環連結清單構成的。
3.3.1 緩存效果的衡量
所有的圖表都是通過測量一個可以模拟任意大小的工作集、讀寫通路、順序通路或随機通路的程式來建立的。我們已經在圖3.4看到一些結果了。程式建立的數組相應的工作集元素的類型如下：
struct l {
struct l *n;
long int pad[NPAD];
};
所有節點使用n元素連結成一個循環連結清單，或者是随機的或者是順序的。 從一個節點前進到下一個節點總是使用指針，即使元素是按順序排列的。pad元素是有效的載體可以設定的很大。在一些測試中修改資料，另一些測試僅僅隻是讀資料。
關于性能的度量的度量我們一直在讨論工作集的大小，工作集是由struct l 元素構成的數組，一個2^N位元組的工作集包含
2^N / sizeof(struct l)個元素。顯然，sizeof(struct l)的大小由NPAD的大小決定。對于32位的系統，NPAD=7意味着每個元素是32位元組，而對于64位的系統則是64位元組。
（1）單線程順序通路
最簡單的測試用例是周遊連結清單的所有元素，連結清單元素是按順序排列，密集排列，向前還是向後的順序處理都無所謂。所有的一系列測試我們度量的是處理單個連結清單元素需要多長時間，時間機關是處理器周期。圖3.10展示了測試結果。除非特别的指出，所有的測試都是在64位奔騰處理器4上做的，意味着當NPAD=0時結構體l大小為8個位元組。
圖3.10 順序讀取，NPAD=0
前兩個測量值被噪聲污染了。測量的工作負載太小，無法排除系統其餘部分的影響。我們可以保守估計這些值在4個周期左右。考慮到這一點，我們可以從圖中看到三個不同的層次:
- 小于2^14位元組大小
- 從2^15位元組到2^20位元組大小
- 2^21位元組以上
産生這樣的階梯式的結果很容易解釋: 處理器有16kB L1d和1MB L2，在從上一級到下一級緩存的轉換中，我們看不到明顯的邊緣，因為系統的其他部分也使用緩存，是以緩存并不隻對程式資料可用。具體來說，L2緩存是一個統一的緩存，也用于指令(注意:Intel使用的是包含性的緩存)。
我們可能不能預計不同工作集大小所需要的确切時間。L1d命中的時間是可以預計的：在P4上大概是4個時鐘周期。但是二級緩存的通路時間呢？一旦一級緩存沒有足夠空間儲存資料，預計需要花費14個時鐘周期甚至更多來處理每個元素，因為這是通路二級緩存的所需要的時間。但是圖中的結果顯示隻需要9個時鐘周期。這沖突可以由處理器進階邏輯解釋。在預期使用連續的記憶體區域時，處理器預取下一個高速緩存行。這意味着當實際使用下一行時，它已經加載了一半。是以，等待下一條高速緩存行加載所需的延遲遠遠小于L2通路時間。
一旦工作集超過二級緩存的大小，預取得效果就更加顯現出來了。之前我們提到主存的通路時間需要花費200+個時鐘周期。隻有通過有效的預取才可能将時間控制在9個周期以下。從200縮短到9這個效果是很明顯的。
圖3.11 不同大小元素的順序讀取
我們可以在預取得時候間接的觀察處理器。圖3.11我們可以看到結構體l大小不同時的結果，意味着我們的連結清單有更大或更小的節點。元素大小不同使得随着連結清單的增長每個元素之間的距離增大。在這四個case中每個元素之間的距離分别為0，56，120，248位元組。從圖中可以看出四條線在L1d級别時都很接近，因為所有的元素都在L1d緩存中命中沒有預取得必要。
對于L2緩存的命中，我們看到其中三條線高度吻合，但是它們的值都挺大的（大概28個周期），這個時間級别是通路二級緩存的時間，這意味着從二級緩存預取資料到一級緩存基本上是不可用的。甚至NPAD=7時我們每次循環疊代時需要一個新的緩存行；對于NPAD=0時疊代8次才需要下一個緩存行。預取邏輯不能在每個循環中加載新的緩存行。是以，在每次疊代中，我們都可以看到從L2加載的延遲。
更有意思的是當工作集超過二級緩存的大小時，四條曲線的差别很大。元素的大小在性能中起到重大的影響。由于NPAD = 15和31的元素大小小于預取視窗(參見6.3.1節)，是以處理器應該識别大步的大小，而不擷取不必要的高速緩存行。元素大小阻礙預取的原因是硬體預取的限制:它不能跨越頁面邊界。對于每個size的增加硬體排程的效率減小了百分之五十。如果硬體預取器能夠跨越頁的邊界并且下個頁不是常駐或有效的，OS将必須參與頁的定位。這意味着程式将出現一個未初始化的頁錯誤。這是完全不能接受的因為處理器不知道某個頁是否存在。後面的case中，OS将會中斷處理。任何測試用例，當NPAD=7甚至更大時，對于連結清單中的每個元素都需要一個緩存行，硬體預取器能做的有限。根本沒有時間從記憶體中加載資料，因為所有的處理器所做的隻是讀取一個字然後加載下一個元素。（這段沒了解透？？？？）
速度下降的另一個重要原因是TLB緩存的脫靶。TLB緩存是存儲虛拟位址轉換為實體位址的結果，在第四章将詳細講述。TLB緩存非常小因為它必須足夠快速。如果重複通路的頁面數量比TLB緩存的條目多的話，那麼虛拟位址到實體位址的轉換必須不斷的重複的進行，這是非常耗時的操作。對于較大的元素，TLB查找的成本将分攤到較少的元素上，也就是說每個連結清單元素計算的TLB條目的總數更高。
圖3.12 TLB對順序讀的影響
為了觀察TLB的影響我們跑了另一個測試。一個測試條件是：還是按順序排列每個元素，我們将NPAD=7這樣每個元素占據一個緩存行。另一個測試條件是：将連結清單中的每個元素放在不同的頁上，每個頁的剩餘記憶體我們保持不變，也不計算到總的工作集大小中。結果是，對于第一次測試，每次連結清單疊代需要一個新的緩存行，每64個元素需要一個新頁。對于第二個測試，每次疊代都需要加載位于新頁面上的新緩存行。
結果展示在圖3.12中和圖3.11所用的機器相同。由于RAM的限制，工作集大小限制在4GB（2^24）的範圍内，需要1GB的空間存放獨立的頁。紅色曲線與圖3.11 NPAD=7時的曲線是一緻的。可以看出L1d和L2緩存大小的跳變。第二條曲線看起來截然不同。重要的特性是當工作集大小達到2^13位元組的時候曲線陡然上升。這時候TLB緩存益處了。元素大小為64位元組時，我們可以計算出TLB緩存有64個條目。沒有頁錯誤影響程式開銷，因為程式鎖定記憶體，以防止它被換出。
可以看到，計算實體位址并将其存儲在TLB中所需要的周期非常長。圖3.12展示了極端的情況，但現在應該清楚了，對于較大的NPAD值來說，降低速度的一個重要因素是TLB緩存的效率降低。由于實體位址必須在為L2或主存讀取高速緩存線之前進行計算，是以位址轉換會增加記憶體通路時間。這部分解釋了為什麼NPAD=31的每個連結清單元素的總成本高于RAM的理論通路時間。
圖3.13 順序讀和寫，NPAD=1
通過檢視修改了連結清單元素的測試運作資料，我們可以看到更多關于預取實作的細節。圖3.13有三條曲線，每個元素都是16位元組。第一條線是熟悉的連結清單周遊作為基線。第二條标記為Inc的線簡單得遞增了下pad[0]成員的值再通路下一個元素。第三條标記為Addnext0的線是取得下一個元素的pad[0]成員值并加到目前元素的pad[0]成員上。
可能會天真的認為“Addnext0”的測試更慢因為需要做更多事，在前進到下一個元素前下個元素的值就需要被加載了。這就是為什麼看到實際運作結果時會感覺驚訝：對于有的工作集大小比“Inc”測試更快。對此的解釋是，來自下一個連結清單元素的加載基本上是強制預取。每當程式前進到下一個連結清單元素時，我們可以确定該元素已經在L1d緩存中。結果我們看到，隻要工作集大小在L2緩存大小範圍内，Addnext0的性能與簡單的Follow測試一樣好。
不過Addnext0測試消耗二級緩存的速度比Inc測試快，因為它需要從主存加載更多資料。這就是為什麼對于工作集大小為2^21位元組大小時，Addnext0測試需要28個周期的原因。28個周期是同樣工作集Follow測試所需14個周期的2倍。由于其他兩個測試修改記憶體，L2緩存清除為新的緩存行騰出空間不能簡單地丢棄資料。相反，它必須被寫到記憶體中。這意味着FSB上的可用帶寬減少了一半，是以将資料從主存傳輸到L2的時間增加了一倍。
圖3.14 更大的二級、三級緩存的優勢
最後一方面，緩存的大小影響緩存的效率。這是比較明顯的，圖3.14展示了以每個元素128位元組為基準的時間開銷。這次度量了三種不同的機器，第一二個是P4系列，最後一個是Core2處理器。第一和第二台機器的差別是緩存大小的不同。第一個處理器有32K的L1d緩存，1M的二級緩存。第二台處理器有16K的L1d緩存，512K的二級緩存和2M的三級緩存。第三台處理器有32K的L1d緩存和4M的二級緩存。
圖表中最有意思的不是Core2處理器比其他兩個的性能如何，這裡的主要興趣點是工作集的大小對于各自的最後一級緩存來說太大，而主記憶體會大量參與其中的區域。正如預期的那樣，最後一級緩存越大，曲線在L2通路成本對應的低一級停留的時間就越長，需要注意的是它提供的性能優勢。第二個處理器在工作集是2^20位元組大小的時候性能是第一個處理器的兩倍。這一切都歸功于最後一級緩存大小的增加。擁有4M L2的Core2處理器性能更好。
對于随機工作負載，這可能沒有多大意義。但是，如果工作負載可以根據最後一級緩存的大小進行調整，則程式性能可以顯著提高。這就是為什麼有時值得為擁有更大緩存的處理器花費額外的錢。
（2）單線程随機通路
我們已經知道處理器可以通過預取緩存行内容到二級和一級緩存而隐藏了通路主存和二級緩存的延時。這種機制僅對于記憶體可以預取起作用。
圖3.15 順序 VS 随機讀取， NPAD=0
如果通路模式不可以預取或者是随機通路那麼情況就大不相同了。圖3.15展示了順序讀取連結清單中的元素的開銷和随機讀取的比較結果。順序由随機化的連結清單決定。處理器無法可靠地預取資料。這隻能在元素在記憶體中彼此相鄰的情況下偶然起作用。圖3.15有兩點需要注意：第一，随着工作集的增加時間周期大量增加，機器通路主存可能需要200個時間周期但這裡達到了450個甚至更多。我們以前見過這種現象(比較圖3.11)。自動預取在這裡實際上是沒有優勢的。第二，在不同的平台上，曲線并不像在順序通路情況下那樣平坦。曲線不斷上升。為了解釋這一點，我們可以測量程式對不同工作集大小的L2通路。結果如圖3.16和表3.2所示。
表3.2 順序通路和随機通路二級緩存的命中和脫靶，NPAD=0
圖3.16 二級緩存的脫靶率
不斷增加的脫靶率就可以解釋一些開銷的原因，但還有其他因素。從表3.2中我們可以看出，在L2/#Iter列中，每次程式疊代使用L2的總數在增長。每次工作集都是上一個的兩倍，沒有緩存預計需要兩倍的主存通路量，有了緩存和(幾乎)完全的可預測性，我們就可以看到連續通路資料中L2使用的适度增加。增加是由于工作集大小的增加，而不是其他原因。
圖3.17 page-wise随機化，NPAD=7
對于随機通路，每個元素的通路時間在工作集大小每增加一倍時增加一倍以上。背後的原因是TLB脫靶率增加了。圖3.17可以看到NPAD=7時随機通路的開銷，隻是這次修改了随機化。正常情況下整個随機連結清單視為一個塊（圖中無窮符号标記的），其他11條曲線在較小區域内進行的随機化。标記‘60’的曲線表示在60頁内進行獨立的随機化。這意味着在轉到下一個塊中的元素之前周遊塊中的所有連結清單元素。這導緻在任何時間使用的TLB條目的數量是有限的。
對于NPAD=7時元素的大小是64位元組，正好和緩存行的大小一緻。由于連結清單元素順序的随機化，硬體預取器不太可能有比較好的效果。這意味着L2緩存失誤率與在一個塊中随機化整個清單沒有顯著差異。對于單塊随機化，随着塊大小的增加，測試性能逐漸接近一個塊随機化的曲線。這意味着後面測試用例的性能受到TLB miss的顯著影響。如果能夠降低TLB的脫靶量，則可以顯著提高性能。
3.3.3 寫的行為
在檢視多個執行上下文(線程或程序)使用相同記憶體時的緩存行為之前，我們必須研究緩存實作的細節。緩存應該是一緻的，這種一緻性對于使用者級代碼應該是完全透明的。核心代碼則是另一回事;它偶爾需要緩存重新整理。這具體意味着，如果修改了高速緩存行，則系統在此時間點之後的結果與根本沒有緩存并且修改了主記憶體位置本身一樣。這可以通過兩種方式或政策實作：
- 直寫式緩存實作
- 回寫式緩存實作
直寫式緩存實作是實作緩存一緻性最簡單的方式。如果緩存行被寫了處理器馬上把緩存行寫入記憶體。這就保證了再任何時間緩存和主存的内容保持同步。隻要緩存行内容被替換就可以簡單的丢棄。這種緩存機制簡單但不高效。舉例說明，一個程式重複的修改一個局部變量将會造成FSB總線的擁堵，盡管這些資料可能不會在其他任何地方使用，而且可能是短期存在的。
回寫式緩存機制更加複雜。處理器不會立即将被修改的緩存行寫到主存中，而是将緩存行标記為髒緩存。當緩存行在将來的某個時候從緩存中删除時，髒位将訓示處理器在那時将資料寫回，而不是僅僅丢棄内容。回寫緩存有機會獲得更好的性能，這就是為什麼在一個擁有良好處理器的系統中，大多數記憶體都是這樣緩存的。處理器可以利用FSB空閑的帶寬在緩存行被丢棄之前将其内容寫到主存中。當需要緩存騰出空間時，這時候髒的标記将會被清除，處理器丢棄緩存行。
但在回寫緩存機制的實作上還存在一個重大的問題。當不隻一個處理器想要通路同一塊記憶體單元時，必須保證所有的處理器看到同一塊記憶體單元的内容是一緻的。如果緩存行在一個處理器上是髒緩存（這時候還沒寫回到主存），而第二個處理器想要讀取這塊記憶體的内容，讀操作不能從主存中讀取，而應該從第一個處理器的緩存中讀取。下一節我們将看到目前是如何實作這一機制的。
在我們往下進行前，需要提及兩個緩存政策：寫合并和不可緩存。這兩個政策都用于位址空間中不受實際RAM支援的特殊區域。核心為位址範圍設定這些政策(在x86處理器上使用記憶體類型範圍寄存器，MTRRs)，其餘的自動發生。mtrr還可以用來在寫進和寫回政策之間進行選擇。
寫合并緩存優化機制有局限性，通常擁有顯示卡裝置。由于裝置的傳輸成本比本地RAM通路要高得多，是以更重要的是要避免進行太多的傳輸。如果下個操作修改了下個字，僅僅因為一個字的改寫而轉移一整個緩存行是浪費的。很容易想象這是一種常見的現象，螢幕上水準相鄰像素的記憶體在大多數情況下也是相鄰的。寫合并顧名思義就是在緩存行被寫到主存前将多次寫通路合并。理想的情況下整個緩存行被一個字一個字的修改，僅在最後一個字寫完後，整個緩存行寫入裝置。這樣就能夠在裝置上加速通路RAM。
最後是不可緩存的記憶體。通常意味着記憶體位置不被RAM支援。它可能是一個寫死的特殊位址，以便在CPU外部實作某些功能。對于普通硬體來說，最常見的情況是記憶體映射位址範圍轉換成對連接配接到總線(PCIe等)上的卡片和裝置的通路。在嵌入式電路闆上，人們有時會發現這樣一個記憶體位址，可以用來打開和關閉一個LED。緩存這樣的位址顯然不是一個好主意。在這種情況下，LEDs用于調試或狀态報告，希望盡快看到這一點。PCIe卡上的記憶體可以在沒有CPU互動的情況下改變，是以不應該緩存這些記憶體。
3.3.4 支援多處理器
在上一節中我們已經提到了多處理器會面臨的問題。 即使是有的緩存不共享的多核處理器也有同樣的問題。從一個處理器提供對另一處理器緩存的通路是不切實際的。首先，連接配接也是不夠快的。可替代的方案是傳輸緩存内容到另一個處理器，這也同樣适用于在同一處理器不共享的緩存。
問題是何時傳輸緩存内容？這個問題相當容易解答：當一個處理器需要緩存行的内容，但是在另一個處理器上是髒資料是。
但是又有一個問題，處理器怎麼知道緩存行在另外的處理器上是不是髒緩存呢？通常大多數的記憶體通路都是讀操作，緩存行不是髒資料。處理器對于緩存行的操作是非常頻繁，這意味着在每次寫通路之後廣播緩存行被更改的資訊是不切實際的。
多年來發展起來的是MESI緩存一緻性協定(可修改的、獨占的、共享的、無效的)。該協定是根據使用MESI協定時緩存行可能處于的四種狀态命名的：
- 可修改的（Modified)： 本地處理器已經修改了緩存行的内容。
- 獨占的（Exclusive）： 緩存行沒有被修改，但是知道沒有被加載到任何其他處理器的緩存中。
- 共享的（Shared）：緩存行沒有被修改，在其他處理器中可能存在。
- 無效的（Invaild）：緩存行無效。
多年來，這個協定從比較簡單的版本發展而來，這些版本比較簡單，但是也比較低效。使用這四種狀态可以有效地實作寫回緩存，同時還支援在不同的處理器上并發地使用隻讀資料。
圖3.18 MESI傳輸協定
通過處理器監聽或窺探其他處理器的工作，無需太多的工作就可以完成狀态更改。處理器執行的某些操作是在外部引腳上聲明的，這樣使得處理器的緩存操作對外部是可見的。在接下來的對于狀态和狀态遷移的描述中我們将指出涉及到的總線。
初始狀态所有的緩存行都是空的無效的資料。如果資料被加載進緩存線用于寫緩存，緩存就是處于可寫狀态。如果資料被加載用來讀，新的狀态取決于其他處理器是否也加載了這個緩存行。如果是則新的狀态為可共享的，否則為獨占的。
如果一個可寫的緩存行由自己的處理器讀寫操作将不改變其狀态。如果第二個處理器想要讀取這個緩存行的内容第一個處理器必須将其傳輸給第二個處理器，然後把自己緩存行的狀态改變為共享的。傳輸到第二個處理器上的資料也是由記憶體控制接收和處理的并存儲到記憶體中，如果這個過程沒有發生，則不能被标記為共享的。如果第二個處理器想要修改第一個處理器傳輸過來的緩存行内容，标記第一個處理器的緩存行為無效狀态。這就是臭名昭著的“請求所有權”ROF操作。在最後一級緩存中執行像I狀态到M狀态的操作代價是很大的。對于直寫緩存，我們還必須增加将新緩存行内容寫入下一個更進階别緩存或主記憶體的時間，進而進一步增加成本。
如果一個緩存行處于可共享的狀态，本地處理器讀取内容不需要改變其狀态，可以從緩存中完成讀操作。如果緩存行被自己的處理器寫入并且是可用的則狀态修改為可修改的狀态。任然也可以請求其他處理器的副本标記為無效。是以，寫入操作必須通過RFO消息通知其他處理器。如果第二個處理器請求緩存行進行讀取，則什麼也不會發生。主記憶體包含目前資料，并且已經共享了本地狀态。如果第二個處理器想要向緩存行(RFO)寫入資料，那麼緩存行将被簡單地标記為無效。不需要總線操作。
獨占狀态預共享狀态基本相同但有一個關鍵性的差別：本地處理器的寫操作不需要通知總線。本地緩存是唯一持有該緩存行的緩存。這可以産生巨大的優勢是以處理器将盡可能的讓更多的緩存行處于獨占狀态而不是共享狀态。後者是在此時無法獲得資訊時的後備選擇。獨占狀态也可以完全忽略，而不會引起功能問題。隻是性能将遭受自E->M的轉換比S->M的轉換快多了。從對狀态轉換的描述中，應該可以清楚地看到多處理器操作的具體開銷。是的，填充緩存仍然開銷很大，但是現在我們還必須注意RFO消息。每當需要發送這樣的消息時，速度就會變慢。以下有兩個場景需要用的RFO消息：
- 一個線程從一個處理器遷移到另一個處理器，所有的緩存行必須遷移到新的處理器。
- 一個緩存行被兩處理器需要
多線程或多程序程式總是需要考慮同步問題；這種同步是使用記憶體實作的。是以有一些有效的RFO消息。它們仍然必須盡可能地不要頻繁使用。不過，還有其他的RFO消息來源。在第6節中，我們将解釋這些場景。緩存一緻性協定消息分布在系統的各個處理器之間。MESI轉換無法執行直到系統中的所有處理器都有機會回複消息。這意味着一個應答可能花費的最長時間決定了一緻性協定的速度。總線沖突是可能的，NUMA系統的延遲可能很高，當然，龐大的通信量會降低速度。是以把注意力放在避免不必要的總線阻塞上是理所當然的。
還有一個與使用多個處理器相關的問題。這些影響是機器特有的，但原則上問題總是存在：FSB是共享資源。大多數機器所有的處理器通過一條單一總線和記憶體控制器連接配接（參見圖2.1）。如果單一的處理器可以是總線飽和，那麼兩個或四個處理器共享同條總線将進一步現在每個處理器的可用帶寬。
盡管每個處理器擁有自己到記憶體控制器的總線如圖2.2所示，但仍然是到記憶體子產品的總線。并發的通路同一個記憶體子產品将限制總線的帶寬。在AMD模型中也是一樣，每個處理器都可以有本地記憶體。所有處理器确實可以同時快速通路它們的本地記憶體，特别是使用內建的記憶體控制器。但是多線程和多程序程式至少在某些時候必須通路相同的記憶體區域來進行同步。
并發将受到因為需要實作同步的有限可用帶寬的嚴重限制。程式需要精心設計，減少不同處理器和不同核對相同記憶體位置的通路。下面的測量将顯示這個和其他與多線程代碼相關的緩存效果。
（1）多線程通路
為了確定不同的處理器并發的使用相同的緩存行所帶來的問題的嚴重性被了解，我們将使用和之前相同的程式來呈現更多的圖表。這次同時有多個線程運作，所度量的是任何線程的最快運作時。這意味着當所有線程都完成時，完成一次完整運作的時間會更長。機器有四個處理器，測試使用了至少四個線程。所有的處理器共享一條到記憶體控制器的總線，而且隻有一條到記憶體子產品的總線。
圖3.19 多線程順序通路
圖3.19展示了多線程順序通路一個元素128位元組的性能。對于一個線程的曲線，我們期望類似于圖3.11的曲線。因為這次測量是針對不同的機器，是以實際的數字是不同的。這次重點當然是關注多線程的行為。注意到在周遊連結清單是不會修改記憶體也不試圖去保持線程同步。盡管RFO消息是需要的并且所有的緩存行是可共享的，我們可以看到當有兩個線程時最快的線程性能和隻有一個線程比性能損失達到18%，四個線程時達到34%。由于沒有緩存行在處理器之間傳輸，是以性能下降僅由一個或兩個瓶頸造成的：從處理器到記憶體控制器的共享總線和記憶體控制器到記憶體子產品的總線。一旦工作集比三級緩存容量大所有的三個線程都将預取新的連結清單元素。即使有兩個線程，可用帶寬也不足以線性擴充。
圖3.20 多線程順序遞增
當我們修改記憶體時事情變得更加棘手。圖3.20Y軸使用的是以對數的形式标記的，所有不要被表面看上去差别不是很大所迷惑。當兩個線程時任然有18%的性能損失，當四個線程時損失達到了93%之多。這意味着當四個線程時，預取和寫回的操作使總線的帶寬達到了飽和狀态。
我們可以看到，一旦多于一個線程通路，L1d緩存基本是起不到作用的。隻有L1d不滿足工作集時單個線程的通路才會超過20個時鐘周期。在小的工作集多線程通路也能很快的命中。這裡沒有顯示問題的一個方面。用這個特定的測試程式很難測量。盡管測試修改了記憶體，是以我們必須期望RFO消息，但當使用多個線程時，我們沒有看到二級緩存的開銷更高。程式必須使用大量的記憶體，并且所有線程必須并行地通路相同的記憶體。如果沒有大量的同步，這很難實作，因為同步會控制執行時間。
圖3.21 多線程操作随機加下一進制素的最後一個成員值
最後在圖3.21顯示了驚人的數字，極端的情況需要花費大概1500個時鐘周期處理單個連結清單元素。表3.3總結了多線程的效率：
表3.3 多線程的效率
| #Threads | Seq Read | Seq Inc | Rand Add |
| 2 4 | 1.69 2.98 | 1.69 2.07 | 1.54 1.65 |
該表顯示了圖3.19，3.20，3.21中最大工作集時多線程的工作效率。表中的數值表示在最大工作集時最佳可能的加速倍速。對于兩個線程的情況理論上加速極限可以達到2，對于4個線程時是4（理論上幾個線程就是幾倍的效率）。實際情況是兩個線程時結果不是特别糟糕，但是四個線程時，對于最後一項測試顯示了兩個線程以上就不值得加速了。如果我們以稍微不同的方式表示圖3.21中的資料，我們可以更容易地看到這一點。
圖3.22 并發的加速效果
圖3.22展示了多線程和單線程的加速效果值的比較結果。對于小的資料集的度量不夠準确，是以我們忽略最小的工作資料集。對于在二級緩存到三級緩存大的範圍，我們可以看到我們幾乎是獲得了線性的加速效果。我們幾乎獲得了完美的2和4倍的加速效果。但是隻要超過了三級緩存的大小，效率馬上就降低到了奔潰的邊緣，導緻4個線程和2個線程的加速效果基本一緻。這就是很難找到擁有四個CPU以上的支援套接字的主機闆使用同一個記憶體控制器的一個原因。擁有更多處理器的機器必須建構不同的記憶體控制器（見第5章）。測試結果的數值并不通用于所有情況，有時候經過工作集在最後一級緩存的範圍内也可能達不到線性的倍速。實際上這是一種常态因為線程通常不像這個測試程式中那樣解耦。另一方面，使用大型工作集仍然可以利用兩個以上的線程。不過這樣做需要考慮考慮。我們将在第6章中讨論一些方案。
（2）特殊用例：超線程
超線程（有時被稱為對稱多線程-SMT）是CPU應對單線程不能真正實作并發運作而實作的。它們共享幾乎所有處理器的資源除了寄存器組。單核和cpu仍然并行工作，但是在每個核心上實作的線程受到這個限制。理論上每個核上可以跑很多的線程，但是目前為止，英特爾的CPU一個核最多跑兩個線程。CPU負責對線程進行時間多路複用，然而，單憑這一點是沒有多大意義的。真正的好處是，當目前運作的超線程被延遲時（多數情況是記憶體通路引起的延時），CPU可以排程另一個超線程并利用可用的資源如算術邏輯單元(ALUs)。
如果兩個線程在一個超線程核心上運作，那麼隻有當兩個線程的聯合運作時間低于單線程代碼的運作時間時，程式才會比單線程代碼更有效。連續通路兩塊不同的記憶體的等待時間可能疊加。一個簡單的計算公式顯示了實作一定加速所需的緩存命中率的最低要求。程式的執行時間可以用一個隻有一級緩存的簡單模型來近似，如下所示：
其中：
N 表示指令的數量；Fmem表示 N個指令中通路記憶體的比例；Ghit表示負載命中緩存的比例；Tproc表示每條指令的周期數；Tcache緩存命中的周期數；Tmiss表示緩存脫靶的周期數；Texe表示程式執行的時間；
為了使運作兩個線程看起來更有意義，兩線程中每個線程的執行時間幾乎是運作單個線程執行時間的一半。兩邊唯一的變量是緩存命中的次數。如果我們解出想不使線程執行速度降低50%或更多所需的最小緩存命中率的方程，我們将得到圖3.23：
圖3.23 達到加速效果要求的最小緩存命中率
X軸作為輸入表示單線程代碼的緩存命中率Ghit。Y軸表示多線程代碼的緩存命中率。多線程的命中率不可能比單線程的高。對于單線程命中率低于55%的特定情況，程式在任何情況下都可以從使用多線程中獲益。由于緩存丢失CPU或多或少有足夠的時間來運作第二個超線程。
綠色是目标區域，如果線程的減速小于50%，并且每個線程的工作負載減半，則合并運作時可能小于單線程運作時間。一個緩存命中率為60%的單線程程式要求在多線程的情況下命中率至少是10%。這通常是可行的。但是，如果單線程代碼的命中率為95%，那麼多線程代碼需要至少80%的命中率，這就比較困難了。特别是對于超線程的情況，因為現在每個超線程可用的有效緩存大小(這裡是L1d，實際上也是L2等等)被削減了一半。兩個超級線程使用相同的緩存來加載它們的資料。如果兩個線程的工作集不重疊，原來的95%命中率也可以減半，是以大大低于要求的80%。
是以，超線程僅僅适用于某些場合。單線程代碼的緩存命中率必須足夠低，進而在給定上述等式和減少緩存大小的情況下，新的命中率仍然滿足目标。隻有這樣，使用超線程才有意義。實際上，結果是否更快取決于處理器是否能夠充分地将一個線程中的等待時間與其他線程中的執行時間疊加。必須将并行化代碼的開銷添加到新的總運作時中，通常不能忽略這一額外的開銷。
在第6.3.4節中，我們将看到一種技術，其中線程緊密協作，通過公共緩存實作緊密耦合實際上是有優勢的。如果程式員願意投入時間和精力來擴充他們的代碼，這種技術可以适用于許多情況。
我們應該清楚的認識到如果兩個超線程執行不同的代碼，緩存大小确實減小了一半意味着緩存脫靶率顯著增加。除非緩存足夠大，否則這種作業系統排程實際上是有問題的。除非機器的工作任務由程序組成，這些程序通過它們的設計确實可以從超線程中獲益，否則最好關閉計算機BIOS中的超線程。
3.3.5 其他細節
到目前為止我們挑了了位址由三個部分組成：标簽，組索引，緩存行偏移。但是實際使用的位址是哪個？因為現在所有相關的處理器都為程序提供虛拟位址空間，這意味着有兩種不同的位址: 虛拟位址和實體位址。
虛拟位址的問題是它們并不唯一。一個虛拟位址随着時間的變化可以映射到不同的實體記憶體位址上。不同處理器的相同的位址也可能指向不同的實體位址。是以最好使用實體位址嗎？這裡的問題是在執行期間使用的虛拟位址必須在記憶體管理單元(MMU)的幫助下轉換為實體位址。這是一個重要的操作。在執行指令的管道中，實體位址可能在稍後的階段才可用。這意味着緩存邏輯必須非常快地确定記憶體位址是否被緩存了。如果可以使用虛拟位址，緩存查找可以在管道中更早地進行，并且在緩存命中的情況下記憶體内容變得可用。這樣管道可以隐藏更多的記憶體通路成本。
處理器設計者目前使用虛拟位址為一級緩存添加标簽。這些緩存相當的小且清除不會有太多開銷。如果處理器的頁表樹發生了變化至少需要清除部分緩存。如果處理器允許指定已經改變的虛拟位址的範圍可能可以避免重新整理整個緩存。L1i和L1d緩存（大概3個周期）使用虛拟位址必須是低延遲的。
對于像二級，三級那樣的大緩存需要實體位址作為标簽。這些緩存有較大的延時，要求虛拟位址到實體位址的轉換能夠及時的完成。因為這些緩存更大，填充和重新整理它們因為主存的延時需要更多的開銷。一般來說不需要知道這些緩存中位址處理的細節，位址處理是不能改變的，影響性能的因素都是那些應該避免或開銷大相關的操作。溢出緩存容量是糟糕的，并且如果使用的大多數緩存行都屬于同一組，那麼所有緩存都會在早期遇到問題。後者可以通過虛拟尋址的緩存來避免，但是對于使用實體位址尋址的緩存，使用者級程序不可能避免。唯一需要記住的細節是，如果可能的話，不要将同一個實體記憶體位置映射到同一個程序中的兩個或多個虛拟位址。
另一個開發者不感興趣的緩存實作細節是緩存替換機制。大多數緩存首先驅逐最近最少使用的(LRU)元素。這總的來說是一個不錯的預設的機制。随着更大的關聯性(并且關聯性可能在未來幾年由于更多核心的增加而進一步增長)，維護LRU清單開銷變得越來越大，我們可能會看到不同的政策被采用。
因為程式員不能為緩存替換機制做點什麼。如果緩存使用的是實體位址标記，則無法找出虛拟位址如何與緩存組關聯。可能是所有邏輯頁中的緩存行都映射到相同的緩存組導緻大部分緩存未被使用。作業系統能做的就是盡量避免這種情況經常發生。
随着虛拟化的到來，事情變得更加複雜。現在，甚至作業系統也不能控制實體記憶體的配置設定。虛拟機螢幕(VMM，又稱Hypervisor)負責配置設定實體記憶體。
程式員所能做的最好的事情是 a)完全使用邏輯記憶體頁，b) 使用盡可能大的有意義的頁大小來盡可能多地分散實體位址。更大的頁面大小也有其他好處，但這是另一個主題(參見第4節)。
3.4 指令緩存
不僅是處理器使用的資料被緩存，處理器執行的指令也需要緩存。然而，指令緩存比資料緩存的問題少是因為：
- 執行的代碼數量取決于所需代碼的大小。代碼的大小通常取決于問題的複雜性。問題的複雜性是固定的。
- 雖然程式的資料處理是由程式員設計的，但程式的指令通常是由編譯器生成的。編譯器編寫者知道良好代碼生成的規則。
- 程式流程比資料通路模式更容易預測。如今的CPU非常擅長于檢測模式，這對預取有幫助。
- 代碼總是具有較好的空間局限性。
程式員應該遵循一些規則，但這些規則主要是關于如何使用工具的規則。我們将在第6節中讨論它們。這裡我們隻讨論指令緩存的技術細節。
自從CPU核的時鐘急劇增加，緩存(甚至是一級緩存)和CPU核之間的速度差異增大以來，CPU就被設計成使用管道。這意味着指令的執行是分階段進行的。首先譯碼一條指令，然後準備參數，最後執行。這樣的管道可能相當長(英特爾Netburst架構的> 20個階段)。長管道意味着如果管道停止運作(當指令流程中斷時)需要一段時間才能恢複到原來的速度。例如，如果無法正确預測下一條指令的位置，或者加載下一條指令的時間過長(例如，必須從記憶體中讀取指令)，就會發生管道阻塞。是以，CPU設計人員在分支預測上花費了大量的時間和晶片空間，以盡可能減少管道阻塞的發生。
在CISC處理器上，譯碼階段也需要一些時間，x86和x86-64處理器受到的影響尤其嚴重。是以，近年來這些處理器并不緩存L1i中指令的原始位元組序列，而是緩存譯碼指令。在本例中，L1i稱為跟蹤緩存。跟蹤緩存允許處理器在緩存命中時跳過管道的第一步，這在管道停止時尤其有效。如前所述，從L2開始的緩存是包含代碼和資料的統一緩存。顯然，這裡的代碼以位元組序列形式緩存，而不是譯碼。為了獲得最佳的性能，隻有一些與指令緩存相關的規則：
- 生成的代碼盡可能小。
- 協助處理器做出好的預取決策。這可以通過代碼布局或顯式預取來實作。
這些規則通常由編譯器的代碼生成器來實施。程式員可以做的事我們将在第6節中讨論。
3.4.1 自修改代碼
早期計算機的記憶體是非常寶貴的。人們竭盡全力縮小程式的大小，為程式資料騰出更多的空間。經常使用的一個技巧是随着時間改變程式本身。這種自修改代碼(SMC)偶爾還會被發現，主要是由于性能原因或安全漏洞。一般來說應避免SMC。雖然它通常可以正确執行的，但有一些極端情況不是這樣的，如果執行不正确，就會産生性能問題。顯然，更改的代碼不能儲存在包含譯碼指令的跟蹤緩存中。但是，即使由于根本沒有執行代碼(或一段時間沒有執行代碼)而沒有使用跟蹤緩存，處理器也可能會出現問題。如果一條即将執行的指令在它已經進入流水線的時候被改變了，處理器不得不扔掉大量的工作，重新開始。甚至在某些情況下，必須丢棄處理器的大部分狀态。最後，由于處理器假設代碼頁是不可變的(因為在99.9999999%的情況下都是如此)，是以L1i實作不使用MESI協定，而是使用簡化的SI協定。這意味着如果檢測到修改，就必須做出許多悲觀的假設。
強烈建議盡量避免SMC，記憶體已經不再是稀缺資源。最好是編寫單獨的函數，而不是根據特定的需要修改一個函數。也許有一天SMC成為可選的，我們可以以這種方式檢測利用代碼試圖修改代碼。如果必須使用SMC，則寫操作應該繞過緩存，以免造成L1i中需要的資料在L1d中問題。有關這些說明的更多資訊，請參見第6.1節。
在Linux上，通常很容易識别包含SMC的程式。當使用正常工具鍊建構時，所有的程式代碼都是寫保護的。程式員必須在連結時執行重要的魔術來建立可寫代碼頁的可執行檔案。當這種情況發生時，現代的Intel x86和x86-64處理器都有專用的性能計數器，用于計算使用自修改代碼的次數。在這些計數器的幫助下識别SMC程式是很容易的。
3.5 緩存脫靶因素
我們已經看到，當記憶體通路在緩存中脫靶時，開銷會急劇上升。有時這是不可避免的，重要的是要了解實際的開銷和可以做什麼來減輕這種問題。
3.5.1 緩存和記憶體的帶寬
為了了解處理器的性能，我們測量了處理器最佳狀态下的帶寬。這次測量比較有意思，因為不同的處理器版本差異很大。這就是為什麼這一節擁有幾個不同機器的資料。測量性能的程式使用x86和x86-64處理器的SSE指令一次加載或存儲16個位元組。與我們的其他測試一樣，工作集從1kB增加到512MB，并測量每個循環可以加載或存儲多少位元組。
圖3.24 奔騰4帶寬
圖3.24顯示了64位Intel Netburst處理器的性能。對于小于L1d緩存大小的工作集，處理器能夠在每個周期讀取完整的16個位元組，即，每個循環執行一條加載指令(movaps指令一次移動16個位元組)。測試對讀資料不做任何事情，我們隻測試讀指令本身。一旦超出L1d緩存，性能就會急劇下降到每個周期不到6個位元組。工作集為2^18位元組的時候由于耗盡了DTLB緩存，這意味着每個新頁面都需要額外的開銷。由于是順序讀取的預取能夠很好的發揮效果，對于所有大小的工作集，FSB總線可以以大約5.3位元組/周期的速度傳輸記憶體内容。
比讀性能更驚人的是寫和複制性能。即使對于較小的工作集，寫性能也不會超過每個周期4個位元組。這表明，在這些Netburst 處理器中，Intel選擇在L1d中使用直寫模式，該性能明顯受到L2速度的限制。這還意味着，從一個記憶體區域複制到另一個非重疊記憶體區域的複制測試的性能并沒有顯著下降。必要的讀操作很快，并且可以與寫操作部分重疊。關于寫和複制的測試最值得注意的細節是，一旦L2緩存不再足夠，就會出現性能低下的情況。性能下降到每個周期0.5位元組!這意味着寫操作比讀操作慢10倍。這意味着優化這些操作對于程式的性能來說更加重要。
圖3.25 擁有2個超線程的奔騰4帶寬
在圖3.25中，我們看到的結果在同一個處理器上，但是有兩個線程在運作，其中一個固定在處理器的兩個超線程中。該圖與前一個圖相同的比例顯示來說明差異。結果與預期一緻。由于超級線程共享除了寄存器之外的所有資源，每個線程隻有一半的緩存和帶寬可用。這意味着即使每個線程都要等待很多時間，并且可以給另一個線程執行時間，這也沒有任何差別，因為另一個線程也必須等待記憶體。這确實顯示了超線程最糟糕的用法。
圖3.26 Core2帶寬
圖3.27 兩線程Core2的帶寬
與圖3.24和3.25相比，圖3.26和3.27中的結果看起來與Intel Core 2處理器有很大的不同。這是一個共享L2的雙核處理器，二級緩存的大小是P4機器上的四倍。不過，這隻解釋了寫入和複制性能延遲下降的原因。 還有其他更大的差別。整個工作集範圍内的讀取性能在每個周期内保持在最佳16位元組左右。工作集為2^20位元組之後讀取性能的下降再次是因為工作集對于DTLB來說太大了。能獲得這麼大的數值意味着處理器不僅能夠預取資料并及時傳輸資料，還意味着資料被預取到L1d中。寫和複制性能也有顯著的不同。處理器采用的不少直寫政策; 已經寫的資料存儲在L1d中，隻有在必要時才會被逐出。這使得寫入速度接近于最佳的16位元組/周期。一旦L1d不夠，性能就會顯著下降。與Netburst處理器一樣，寫性能要低得多。由于高讀性能，這裡的差異甚至更大。事實上，當L2不夠時，速度差增加到原來的20倍! 這并不意味着Core 2處理器性能很差。相反，它們的性能總是優于Netburst核。
在圖3.27中，測試運作兩個線程，分别在Core 2處理器的兩個核心上運作。兩個線程通路相同的記憶體，但不一定完全同步。讀取性能的結果與單線程情況沒有什麼不同。在任何多線程測試用例中都可以看到更多的抖動。有趣的一點是在L1d緩存區的工作集的寫和複制性能。從圖中可以看出，性能與從主記憶體中讀取資料一樣。兩個線程競争相同的記憶體位置，必須發送用于緩存行的RFO消息。問題是即使兩個核共享緩存這些請求沒有以L2緩存的速度處理。一旦L1d緩存不再足夠，修改的條目将從每個核的L1d緩存重新整理到共享的L2緩存中。此時性能顯著提高，因為L2緩存滿足了L1d緩存未命中的而且隻有在資料尚未重新整理時才需要RFO消息。這就是為什麼我們看到在這些工作集上速度降低了50%。漸近行為在預料之中: 因為兩個核共享相同的FSB每個核得到一半的FSB帶寬這意味着大型工作集的每個線程性能大約是單線程時的一半。
圖3.28 AMD家族10h Opteron帶寬
因為即使同一個供應商的處理器版本之間也有顯著的差異，是以研究其他供應商處理器的性能是值得的。圖3.28顯示了AMD家族10h Opteron處理器的性能。這個處理器有64kB L1d、512kB L2和2MB L3。L3緩存在處理器的所有核心之間共享。性能測試結果如圖3.28所示。
第一個需要注意的細節是，如果L1d緩存足夠，處理器可以在每個周期中處理兩條指令。讀性能每周期超過32位元組，甚至寫性能也很高，每周期為18.7位元組。不過讀取曲線很快下降變平了，而且每周期2.3位元組的速度是非常低的。此測試的處理器不預取任何資料沒有效率。另一方面，寫曲線根據不同緩存的大小變化，整個L1d區間達到了最佳性能，L2降低到每個周期6位元組，L3降低到每個周期2.8位元組，如果L3不能容納所有資料，則最後降低到每個周期5位元組。L1d緩存的性能超過了(舊的)Core 2處理器，L2的通路速度也一樣快(Core 2的緩存更大)，而L3和主存的通路速度更慢。複制性能不會比讀或寫性能強，這就是為什麼我們看到曲線最初由讀性能決定，後來由寫性能決定。
圖3.29 兩線程AMD家族10h Opteron帶寬
Opteron處理器的多線程性能如圖3.29所示。讀取性能基本上不受影響。每個線程的L1d和L2和以前一樣工作，L3緩存在這種情況下預取的不是很好。這兩個線程并沒有過分強調L3。這個測試的主要問題是寫性能。所有線程共享的資料都必須經過L3緩存。這種共享似乎效率很低，因為即使L3緩存大小足以容納整個工作集，其開銷也遠遠高于L3通路。将此圖與圖3.27進行比較，我們可以看到Core 2處理器的兩個線程以共享L2緩存的速度運作，以獲得适當的工作集大小範圍。對于Opteron處理器，隻有在非常小的工作集大小範圍内才能達到這種水準的性能，即使這樣，它也隻能達到比Core 2的L2慢的L3的速度。
3.5.2 關鍵字負載
記憶體以比緩存行大小更小的塊為機關從主記憶體轉移到緩存中。如今一次傳輸64位，緩存行的大小是64或128位元組。這意味着每條緩存行需要8到16次傳輸。DRAM晶片可以在突發模式下傳輸64位元組的資料塊。這樣就可以填滿緩存線，而不需要來自記憶體控制器的任何其他指令而産生相應的延遲。更好的方式是處理器預取緩存行。
如果程式對資料或指令的高速緩存通路失敗(這意味着強制的高速緩存失敗，因為資料是第一次使用，或者容量高速緩存失敗，因為有限的高速緩存大小需要清除緩存行）的情況就不同了。程式繼續運作所需的緩存行中的字資料可能不是緩存行中的第一個字。即使在突發模式下，使用雙資料速率傳輸，各個64位資料塊到達的時間也明顯不同。每個塊比前一個塊晚4個或更多CPU周期。如果程式繼續運作需要的字資料是緩存行中的第8個字，則程式必須在第一個字到達後再等待30個周期或更多。
情況不一定要這樣。記憶體控制器可以自由地以不同的順序請求緩存行的字。處理器可以告知程式正在等待哪個字資料-關鍵字，記憶體控制器可以先請求這個字資料。一旦字資料到達，程式可以繼續，而其餘的緩存行到達且緩存還不是在一個一緻的狀态。這種技術稱為關鍵字優先&早期重新開機。
現在的處理器實作了這種技術，但是在某些情況下是不行的，比如處理器預取資料而關鍵字是未知的。處理器在預取操作進行期間請求緩存行，它将不得不等待，直到關鍵字到達，而不能影響順序。
圖3.30 關鍵字在緩存行末
即使有了這些優化，關鍵字在緩存行上的位置仍然很重要。圖3.30顯示了順序通路和随機通路的Follow測試。圖中顯示的關鍵字在緩存行的行末比在行首的慢的比例。元素大小為64位元組與緩存行大小一樣。這些數字非常嘈雜，但可以看出，當L2不足以儲存工作集資料時，關鍵字在最後的情況下的性能大約慢0.7%。順序通路似乎受到更多的影響。這與前面提到的預取下一條緩存行的問題是一樣的。
3.5.3 緩存的放置
緩存放在哪裡與超線程、核和處理器的關系不受程式員控制。但是程式員可以确定線程在哪裡執行，然後緩存與使用的cpu之間的關系就變得非常重要。在這裡，我們不會詳細讨論什麼時候選擇哪個核運作哪個線程。我們将隻描述架構細節，程式員在設定線程關聯性時必須考慮這些細節。根據定義，超線程除了寄存器集之外共享所有内容，包括一級緩存。這裡沒什麼好說的了，樂趣始于處理器的各個核。每個核至少有自己的一級緩存。
- 早期的多核處理器根本沒有共享緩存
- 後來的英特爾模型為雙核處理器共享L2緩存。對于四核處理器，每一對雙核處理器有單獨的L2緩存。沒有更進階别的緩存。
- AMD的家族10h處理器有單獨的L2緩存和統一的L3緩存。
處理器廠商的宣傳材料中寫了很多關于他們各自型号的優勢。如果核處理的工作集不重疊，則沒有共享緩存是有好處的。這對于單線程程式很有效。這種方案表現的不是太糟糕這在今天仍然是現實。但總會有一些重疊，緩存都包含公共運作庫中最活躍的部分，這意味着一些緩存空間被浪費了。
完全共享除了一級緩存的所有緩存，就像Intel的dualcore處理器所做的那樣，會有很大的優勢。如果在兩個核心上工作的線程的工作集明顯重疊，那麼可用的緩存記憶體總量就會增加，并且工作集可以更大而不會降低性能。如果工作集不重疊英特爾的先進智能緩存管理應該防止任何一個核獨占整個緩存。
但是，如果兩個核都為各自的工作集使用了大約一半的緩存，就會産生一些沖突。緩存必須不斷權衡兩個核對緩存的使用，而作為重新平衡的逐出操作可能會被錯誤地執行。為了看待這個問題，我們看看另一個測試程式的結果。
測試程式有一個程序不斷地讀寫，使用SSE指令和一個2MB的記憶體塊。記憶體塊選擇2MB大小是因為它是Core 2處理器二級緩存大小的一半。程序固定在一個核上，而第二個程序固定在另一個核上。第二個程序讀寫可變大小的記憶體區域。該圖顯示了每個周期中讀取或寫入的位元組數。這裡顯示了四個不同的圖，分别表示讀寫過程的每個組合。讀/寫曲線是背景程序，背景程序總是使用一個2MB的工作集來寫，而被測量的程序則使用一個可變的工作集來讀。圖中有趣的部分是2^20到2^23位元組之間的部分。如果兩個核的L2緩存是完全獨立的，這意味着一旦L2緩存被耗盡, 我們可以預期所有四個測試的性能将下降2^21到2^22位元組之間。我們可以看到在圖3.31中情況并非如此。對于背景程序正在寫入的情況，這是最明顯的。在工作集大小達到1MB之前，性能就開始下降。這兩個程序不共享記憶體，是以不會生成RFO消息。這些都是純粹的緩存逐出問題。智能緩存處理有它的問題，即每個核的緩存大小接近1MB，而不是可用的2MB。人們隻能希望，如果核之間共享緩存仍然是将來處理器的一個特性，那麼用于智能緩存處理的算法是固定的。
圖3.31 兩個程序的帶寬
在引入更進階别的緩存之前，擁有兩個L2緩存的四核處理器的設計隻是一個權宜之計。與單獨的套接字和雙核處理器相比，這種設計沒有顯著的性能優勢。兩個核通過同一外部的FSB總線通信。沒有特殊的快速資料交換。
未來多核處理器的緩存設計将在更多的層上。AMD的10h處理器系列開始了。我們是否會繼續看到低級緩存被一個處理器核心的子集共享還有待觀察(在2008年的第一代處理器中L2緩存是不共享的)。額外級别的緩存是必要的，因為高速緩存和頻繁使用的緩存不能在多個核心之間共享，性能會受到影響。很高的結合性還需要非常大的緩存。兩個數字，即緩存大小和結合度，都必須随着和共享緩存的數量的增加而增加。使用大的L3緩存和大小合理的L2緩存是一種合理的選擇。L3緩存速度較慢，但在理想情況下，它的使用頻率不如L2緩存。對于程式員來說，所有這些不同的設計意味着做排程決策時的複雜性。為了獲得最佳性能，必須了解工作負載和機器架構的細節。幸運的是，我們有确定的機器架構的支援。這些接口将在後面幾節中介紹。
3.5.4 FSB影響
FSB在機器的性能中起着核心作用。緩存内容隻能與記憶體連接配接的總線一樣的速度進行讀取和寫入。我們可以通過在兩台機器上運作一個程式來說明這一點，這兩台機器上的記憶體子產品的速度各不相同。圖3.32顯示了在64位機器上對NPAD=7進行Addnext0測試(将下一個元素pad[0]元素的内容添加到自己的pad[0]元素中)的結果。兩台機器都使用Intel Core 2處理器，第一個使用667MHz DDR2子產品，第二個使用800MHz子產品(增加了20%)。
圖3.32 FSB速率的影響
資料顯示，當FSB在大規模工作集下壓力很大時，我們确實看到了大帶寬的好處。該測試中測量到的最大性能增長為18.2%，接近理論最大值。這表明，更快的FSB确實能帶來巨大的回報。當工作集在緩存的範圍内時，FSB的速率并不重要(這些處理器有4MB L2)。必須記住，我們在這裡測量的隻是一個程式。系統的工作集包括所有并發運作的程序所需的記憶體。通過這種方式，使用更小的程式很容易超過4MB或更多的記憶體。
今天，一些英特爾的處理器支援的FSB速度高達1333MHZ，這将意味着另一個60%的增長。未來将會看到更高的速度。如果速度很重要，并且工作集的大小很大時花大價錢擁有快速RAM和高FSB速度肯定是值得的。不過，人們必須小心，因為即使處理器可能支援更高的FSB速度，主機闆/北橋可能不支援。檢查規格是很重要的。
純屬個人學習翻譯有翻譯不準确的地方請指出。