702
魔獸
CPU緩存刷新的誤解
即使是資深的技術人員，我經常聽到他們談論某些操作是如何導致一個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核心來說，內存模型可以大致按照如下進行分解：
1.寄存器：在每個核心上，有160個用於整數和144個用於浮點的寄存器單元。訪問這些寄存器隻需要一個時鍾周期，這構成了對執行核心來說最快的內存。編譯器會將本地變量和函數參數分配到這些寄存器上。當使用超線程技術（ hyperthreading ）時，這些寄存器可以在超線程協同下共享。
2.內存排序緩衝（Memory Ordering Buffers (MOB) ）：MOB由 一個64長度的load緩衝和36長度的store緩衝組成。這些緩衝用於記錄等待緩存子係統時正在執行的操作。store緩衝是一個完全的相關性隊列， 可以用於搜索已經存在store操作，這些store操作在等待L1緩存的時候被隊列化。在數據與緩存子係統傳輸時， 緩衝可以讓處理器異步運轉。當處理器異步讀或者異步寫的時候，結果可以亂序返回。為了使之與已發布的內存模型（ memory model ）一致，MOB用於消除load和store的順序。
3.Level 1 緩存：L1是一個本地核心內的緩存，被分成獨立的32K數據緩存和32K指令緩存。訪問需要3個時鍾周期，並且當指令被核心流水化時， 如果數據已經在L1緩存中的話，訪問時間可以忽略。
4.L2緩存：L2緩存是一個本地核心內的緩存，被設計為L1緩存與共享的L3緩存之間的緩衝。L2緩存大小為256K，主要作用是作為L1和L3之間的高效內存訪問隊列。L2緩存同時包含數據和指令。L2緩存的延遲為12個時鍾周期。
5.L3緩存： 在同插槽的所有核心都共享L3緩存。L3緩存被分為數個2MB的段，每一個段都連接到槽上的環形網絡。每一個核心也連接到這個環形網絡上。地址通過 hash的方式映射到段上以達到更大的吞吐量。根據緩存大小，延遲有可能高達38個時鍾周期。在環上每增加一個節點將消耗一個額外的時鍾周期。緩存大小根 據段的數量最大可以達到20MB。L3緩存包括了在同一個槽上的所有L1和L2緩存中的數據。這種設計消耗了空間，但是使L3緩存可以攔截對L1和L2緩 存的請求，減輕了各核心私有的L1和L2緩存的負擔。
6.主內存：在緩存完全沒命中的情況下，DRAM通道到每個槽的延遲平均為65ns。具體延遲多少取決於很多因素，比如，下一次對同 一緩存 行中數據的訪問將極大降低延遲，而當隊列化效果和內存刷新周期衝突時將顯著增加延遲。每個槽使用4個內存通道聚合起來增加吞吐量，並通過在獨立內存通道上 流水線化（ pipelining ）將隱藏這種延遲。
7. 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鏈接可以使用預讀取請求，而前一代 係統不行。
關聯度（Associativity Levels）
緩存是一個依賴於hash表的高效硬件。使用hash函數常常隻是將地址中低位bit 進行映射 ，以實現緩存索引。hash表需要有解決對於同一位置衝突的機製。 關聯度就是hash表中槽（slot）的數量，也被稱為組（ways）和集合（sets），可以用來存儲一個內存地址的hash版本。關聯度的多少需要在 存儲數據的容量，耗電量和查詢時間之間尋找平衡。（校對注：關聯度越高，槽的數量越多，hash衝突越小，查詢速度越快）
對於Sandy Bridge，L1和L2是8路組相連 ，L3是12路組相連 。（For Sandy Bridge the L1D and L2 are 8-way associative, the L3 is 12-way associative.）
緩存一致性
由於一些緩存在內核本地，我們需要一些方法保證一致性，使所有核心的內存視圖一致。對於主流係統來說，內存子係統需要考慮“真實的來源 （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的數據（The ring is made up of 4 independent lanes for: request, snoop, acknowledge, and 32-bytesdata per cycle）。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。）
文章轉自 並發編程網-ifeve.com
最後更新：2017-05-22 20:03:10