摘要：為了保證緩存的一致性，緩存控制器跟蹤每一個緩存行的狀態，這些狀態的數量是有限的。用來表示在體系中響應其他緩存的特定緩存。如今，內存控制器的流量使用一個多帶帶的總線來傳輸。用于緩存段的緩存控制器記錄了哪個核心可能改變自己的緩存行。

即使是資深的技術人員，我經常聽到他們談論某些操作是如何導致一個CPU緩存的刷新?？磥磉@是關于CPU緩存如何工作和緩存子系統如何與執行核心交互的一個常見誤區。本文將致力于解釋CPU緩存的功能以及執行程序指令的CPU核心如何與緩存交互。我將以最新的Intel x86 CPU為例進行說明，其他CPU也使用相似技術以達到相同目的。

絕大部分常見的現代系統都被設計成在多處理器上共享內存。共享內存的系統都有一個多帶帶的內存資源，它會被兩個或者更多的獨立CPU核心同時訪問。核心到主存的延遲變化范圍很大，大約在10-100納秒。在100ns內，一個3GH的CPU可以處理多達1200條指令。每一個Sandy Bridge的CPU核心，在每個CPU時鐘內可以并行處理4條指令。CPU使用緩存子系統避免了處理核心直接訪問主存的延遲，這樣能使CPU更高效的處理指令。一些緩存很小、非常快速并且集成在每個核心之內；而另一些則慢一些、更大、在各個核心間共享。這些緩存與寄存器和主內存一起構成了非持久性的內存體系。

當你在設計一個重要算法時要記住，緩存不命中所導致的延遲，可能會使你失去執行500條指令時間！這還僅是在單插槽（single-socket）系統上，如果是多插槽(multi-socket)系統，由于內存訪問需要跨槽交互，可能會導致雙倍的性能損失。

圖1.對于2012 Sandy Bridge核心來說，內存模型可以大致按照如下進行分解：

寄存器：在每個核心上，有160個用于整數和144個用于浮點的寄存器單元。訪問這些寄存器只需要一個時鐘周期，這構成了對執行核心來說最快的內存。編譯器會將本地變量和函數參數分配到這些寄存器上。當使用超線程技術（ hyperthreading
）時，這些寄存器可以在超線程協同下共享。

內存排序緩沖（Memory Ordering Buffers MOB）：MOB由一個64長度的load緩沖和36長度的store緩沖組成。這些緩沖用于記錄等待緩存子系統時正在執行的操作。store緩沖是一個完全的相關性隊列，可以用于搜索已經存在store操作，這些store操作在等待L1緩存的時候被隊列化。在數據與緩存子系統傳輸時， 緩沖可以讓處理器異步運轉。當處理器異步讀或者異步寫的時候，結果可以亂序返回。為了使之與已發布的內存模型（?memory model?）一致，MOB用于消除load和store的順序。

Level 1 緩存： L1是一個本地核心內的緩存，被分成獨立的32K數據緩存和32K指令緩存。訪問需要3個時鐘周期，并且當指令被核心流水化時， 如果數據已經在L1緩存中的話，訪問時間可以忽略。

L2緩存： L2緩存是一個本地核心內的緩存，被設計為L1緩存與共享的L3緩存之間的緩沖。L2緩存大小為256K，主要作用是作為L1和L3之間的高效內存訪問隊列。L2緩存同時包含數據和指令。L2緩存的延遲為12個時鐘周期。

L3緩存： 在同插槽的所有核心都共享L3緩存。L3緩存被分為數個2MB的段，每一個段都連接到槽上的環形網絡。每一個核心也連接到這個環形網絡上。地址通過hash的方式映射到段上以達到更大的吞吐量。根據緩存大小，延遲有可能高達38個時鐘周期。在環上每增加一個節點將消耗一個額外的時鐘周期。緩存大小根據段的數量最大可以達到20MB。L3緩存包括了在同一個槽上的所有L1和L2緩存中的數據。這種設計消耗了空間，但是使L3緩存可以攔截對L1和L2緩存的請求，減輕了各核心私有的L1和L2緩存的負擔。

主內存：在緩存完全沒命中的情況下，DRAM通道到每個槽的延遲平均為65ns。具體延遲多少取決于很多因素，比如，下一次對同一緩存行中數據的訪問將極大降低延遲，而當隊列化效果和內存刷新周期沖突時將顯著增加延遲。每個槽使用4個內存通道聚合起來增加吞吐量，并通過在獨立內存通道上流水線化（ pipelining ）將隱藏這種延遲。

NUMA：在一個多插槽的服務器上，會使用非一致性內存訪問（ non-uniform memory access ）。所謂的非一致性是指，需要訪問的內存可能在另一個插槽上，并且通過 QPI 總線訪問需要額外花費40ns。 Sandy Bridge對于以往的兼容系統來說，在2插槽系統上是一個巨大的進步。在 Sandy Bridge上，QPI總線的能力從6.4GT/s提升到8.0GT/s，并且可以使用兩條線路，消除了以前系統的瓶頸。對于 Nehalem and Westmere 來說，QPI只能使用內存控制器為一個多帶帶插槽分配的帶寬中的40%，這使訪問遠程內存成為一個瓶頸。另外，現在QPI鏈接可以使用預讀取請求，而前一代系統不行。

緩存是一個依賴于hash表的高效硬件。使用hash函數常常只是將地址中低位bit 進行映射 ，以實現緩存索引。hash表需要有解決對于同一位置沖突的機制。 關聯度就是hash表中槽（slot）的數量，也被稱為組（ways）和集合（sets），可以用來存儲一個內存地址的hash版本。關聯度的多少需要在存儲數據的容量，耗電量和查詢時間之間尋找平衡。（校對注：關聯度越高，槽的數量越多，hash沖突越小，查詢速度越快）

對于Sandy Bridge，L1和L2是8路組相連 ，L3是12路組相連 。

由于一些緩存在內核本地，我們需要一些方法保證一致性，使所有核心的內存視圖一致。對于主流系統來說，內存子系統需要考慮“真實的來源（source of truth）”。如果數據只從緩存中來，那么它永遠不會過期；當數據同時在緩存和主內存中存在時，緩存中存的是主拷貝（master copy）。這種內存管理被稱為寫-回（write-back），在此方式下，當新的緩存行占用舊行，導致舊行被驅逐時，緩存數據只會被寫回主內存中。x86架構的每個緩存塊的大小為64 bytes，稱為緩存行（
cache-line）。其它種類的處理器的緩存行大小可能不同。更大的緩存行容量降低延遲，但是需要更大的帶寬*（**校對*注：數據總線帶寬）。

為了保證緩存的一致性，緩存控制器跟蹤每一個緩存行的狀態，這些狀態的數量是有限的。Intel使用MESIF協議，AMD使用 MOESI。在MESIF協議下，緩存行處于以下5個狀態中的1個。

被修改（Modified）：表明緩存行已經過期，在接下來的場景中要寫回主內存。當寫回主內存后狀態將轉變為排它（ Exclusive ）。

獨享（Exclusive）：表明緩存行被當前核心多帶帶持有，并且與主內存中一致。當被寫入時，狀態將轉變為修改（Modified）。要進入這個狀態，需要發送一個 Request-For-Ownership (RFO)消息，這包含一個讀操作再加上廣播通知其他拷貝失效。

共享（Shared）： 表明緩存行是一個與主內存一致的拷貝。

失效（Invalid）： 表明是一個無效的緩存行。

向前（ Forward ）： 一個特殊的共享狀態。用來表示在NUMA體系中響應其他緩存的特定緩存。

為了從一個狀態轉變為另一個狀態，在緩存之間，需要發送一系列的消息使狀態改變生效。對于上一代（或之前）的 Nehalem核心的Intel CPU和 Opteron核心的AMD CPU，插槽之間確保緩存一致性的流量需要通過內存總線共享，這極大地限制了可擴展性。如今，內存控制器的流量使用一個多帶帶的總線來傳輸。例如，Intel的QPI和AMD的HyperTransport就用于插槽間的緩存一致性通訊。

緩存控制器作為L3緩存段的一個模塊連接到插槽上的環行總線網絡。每一個核心，L3緩存段，QPI控制器，內存控制器和集成圖形子系統都連接到這個環行總線上。環由四個獨立的通道構成，用于：在每個時鐘內完成請求、嗅探、確認和傳輸32-bytes的數據。L3緩存包含所有L1和L2緩存中的緩存行，這有助于幫助核心在嗅探變化時快速確認改變的行。用于L3緩存段的緩存控制器記錄了哪個核心可能改變自己的緩存行。

如果一個核心想要讀取一些數據，并且這些數據在緩存中并不處于共享、獨占或者被修改狀態；那么它就需要在環形總線上做一個讀操作。它要么從主內存中讀?。ň彺鏇]命中），要么從L3緩存讀?。ㄈ绻麤]過期或者被其他核心嗅探到改變）。在任何情況下，一致性協議都能保證，讀操作永遠不會從緩存子系統返回一份過期拷貝。

如果我們的緩存總是保證一致性，那么為什么我們在寫并發程序時要擔心可見性？這是因為核心為了得到更好的性能，對于其它線程來說，可能會出現數據修改的亂序。這么做主要有兩個理由。

首先，我們的編譯器在生成程序代碼時，為了性能，可能讓變量在寄存器中存在很長的時間，例如，變量在一個循環中重復使用。如果我們需要這些變量在核心之間可見，那么變量就不能在寄存器分配。在C語言中，可以添加“volatile”關鍵字達到這個目標。要記住，c/c++中volatile并不能保證讓編譯器不重排我們的指令。因此，需要使用內存屏障。

排序的第二個主要問題是，一個線程寫了一個變量，然后很快讀取，有可能從讀緩沖中獲得比緩存子系統中最新值要舊的值。這對于遵循單寫入者原則（Single Writer Principle）的程序來說沒有任何問題，但是對于
Dekker 和Peterson鎖算法就是個很大問題。為了克服這一點，并且確保最新值可見，線程不能從本地讀緩沖中讀取值。可以使用屏障指令，防止下一個讀操作在另一線程的寫操作之前發生。在Java中對一個volatile變量進行寫操作，除了永遠不會在寄存器中分配之外，還會伴隨一個完全的屏障指令。在x86架構上，屏障指令在讀緩沖排空之前，會顯著影響放置屏障的線程的運行。在其它處理器上，屏障有更有效率的實現，例如 Azul Vega在讀緩沖上放置一個標志用于邊界搜索。

當遵循單寫入者原則時，要確保Java線程之間的內存次序，避免store屏障，那么就使用j.u.c.Atomic(Int|Long|Reference).lazySet()方法，而非放置一個volatile變量。

回到作為并發算法中的一部分的“刷新緩存”誤區上，我想，可以說我們永遠不會在用戶空間的程序上“刷新”CPU緩存。我相信這個誤區的來源是由于在某些并發算法需要刷新、標記或者清空store緩沖以使下一個讀操作可以看到最新值。為了達到這點，我們需要內存屏障而非刷新緩存。

這個誤解的另一個可能來源是，L1緩存，或者 TLB，在上下文切換的時候可能需要根據地址索引策略進行刷新。ARM，在ARMv6之前，沒有在TLB條目上使用地址空間標簽，因此在上下文切換的時候需要刷新整個L1緩存。許多處理器因為類似的理由需要L1指令緩存刷新，在許多場景下，僅僅是因為指令緩存沒有必要保持一致。上下文切換消耗很大，除了污染L2緩存之外，上下文切換還會導致TLB和/或者L1緩存刷新。Intel x86處理器在上下文切換時僅僅需要TLB刷新。

（校對注：TLB是Translation lookaside buffer,即頁表緩沖；里面存放的是一些頁表文件，又稱為快表技術，由于“頁表”存儲在主存儲器中，查詢頁表所付出的代價很大，由此產生了TLB。）

原文 CPU Cache Flushing Fallacy
譯者：潘曦 ?校對：Simon-SZ?，方騰飛
via ifeve