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

即使是資深的技術(shù)人員，我經(jīng)常聽到他們談?wù)撃承┎僮魇侨绾螌?dǎo)致一個(gè)CPU緩存的刷新?？磥?lái)這是關(guān)于CPU緩存如何工作和緩存子系統(tǒng)如何與執(zhí)行核心交互的一個(gè)常見誤區(qū)。本文將致力于解釋CPU緩存的功能以及執(zhí)行程序指令的CPU核心如何與緩存交互。我將以最新的Intel x86 CPU為例進(jìn)行說(shuō)明，其他CPU也使用相似技術(shù)以達(dá)到相同目的。

絕大部分常見的現(xiàn)代系統(tǒng)都被設(shè)計(jì)成在多處理器上共享內(nèi)存。共享內(nèi)存的系統(tǒng)都有一個(gè)多帶帶的內(nèi)存資源，它會(huì)被兩個(gè)或者更多的獨(dú)立CPU核心同時(shí)訪問(wèn)。核心到主存的延遲變化范圍很大，大約在10-100納秒。在100ns內(nèi)，一個(gè)3GH的CPU可以處理多達(dá)1200條指令。每一個(gè)Sandy Bridge的CPU核心，在每個(gè)CPU時(shí)鐘內(nèi)可以并行處理4條指令。CPU使用緩存子系統(tǒng)避免了處理核心直接訪問(wèn)主存的延遲，這樣能使CPU更高效的處理指令。一些緩存很小、非?？焖俨⑶壹稍诿總€(gè)核心之內(nèi)；而另一些則慢一些、更大、在各個(gè)核心間共享。這些緩存與寄存器和主內(nèi)存一起構(gòu)成了非持久性的內(nèi)存體系。

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

圖1.對(duì)于2012 Sandy Bridge核心來(lái)說(shuō)，內(nèi)存模型可以大致按照如下進(jìn)行分解：

寄存器：在每個(gè)核心上，有160個(gè)用于整數(shù)和144個(gè)用于浮點(diǎn)的寄存器單元。訪問(wèn)這些寄存器只需要一個(gè)時(shí)鐘周期，這構(gòu)成了對(duì)執(zhí)行核心來(lái)說(shuō)最快的內(nèi)存。編譯器會(huì)將本地變量和函數(shù)參數(shù)分配到這些寄存器上。當(dāng)使用超線程技術(shù)（ hyperthreading
）時(shí)，這些寄存器可以在超線程協(xié)同下共享。

內(nèi)存排序緩沖（Memory Ordering Buffers MOB）：MOB由一個(gè)64長(zhǎng)度的load緩沖和36長(zhǎng)度的store緩沖組成。這些緩沖用于記錄等待緩存子系統(tǒng)時(shí)正在執(zhí)行的操作。store緩沖是一個(gè)完全的相關(guān)性隊(duì)列，可以用于搜索已經(jīng)存在store操作，這些store操作在等待L1緩存的時(shí)候被隊(duì)列化。在數(shù)據(jù)與緩存子系統(tǒng)傳輸時(shí)， 緩沖可以讓處理器異步運(yùn)轉(zhuǎn)。當(dāng)處理器異步讀或者異步寫的時(shí)候，結(jié)果可以亂序返回。為了使之與已發(fā)布的內(nèi)存模型（?memory model?）一致，MOB用于消除load和store的順序。

Level 1 緩存： L1是一個(gè)本地核心內(nèi)的緩存，被分成獨(dú)立的32K數(shù)據(jù)緩存和32K指令緩存。訪問(wèn)需要3個(gè)時(shí)鐘周期，并且當(dāng)指令被核心流水化時(shí)， 如果數(shù)據(jù)已經(jīng)在L1緩存中的話，訪問(wèn)時(shí)間可以忽略。

L2緩存： L2緩存是一個(gè)本地核心內(nèi)的緩存，被設(shè)計(jì)為L(zhǎng)1緩存與共享的L3緩存之間的緩沖。L2緩存大小為256K，主要作用是作為L(zhǎng)1和L3之間的高效內(nèi)存訪問(wèn)隊(duì)列。L2緩存同時(shí)包含數(shù)據(jù)和指令。L2緩存的延遲為12個(gè)時(shí)鐘周期。

L3緩存： 在同插槽的所有核心都共享L3緩存。L3緩存被分為數(shù)個(gè)2MB的段，每一個(gè)段都連接到槽上的環(huán)形網(wǎng)絡(luò)。每一個(gè)核心也連接到這個(gè)環(huán)形網(wǎng)絡(luò)上。地址通過(guò)hash的方式映射到段上以達(dá)到更大的吞吐量。根據(jù)緩存大小，延遲有可能高達(dá)38個(gè)時(shí)鐘周期。在環(huán)上每增加一個(gè)節(jié)點(diǎn)將消耗一個(gè)額外的時(shí)鐘周期。緩存大小根據(jù)段的數(shù)量最大可以達(dá)到20MB。L3緩存包括了在同一個(gè)槽上的所有L1和L2緩存中的數(shù)據(jù)。這種設(shè)計(jì)消耗了空間，但是使L3緩存可以攔截對(duì)L1和L2緩存的請(qǐng)求，減輕了各核心私有的L1和L2緩存的負(fù)擔(dān)。

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

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

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

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

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

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

被修改（Modified）：表明緩存行已經(jīng)過(guò)期，在接下來(lái)的場(chǎng)景中要寫回主內(nèi)存。當(dāng)寫回主內(nèi)存后狀態(tài)將轉(zhuǎn)變?yōu)榕潘?Exclusive ）。

獨(dú)享（Exclusive）：表明緩存行被當(dāng)前核心多帶帶持有，并且與主內(nèi)存中一致。當(dāng)被寫入時(shí)，狀態(tài)將轉(zhuǎn)變?yōu)樾薷模∕odified）。要進(jìn)入這個(gè)狀態(tài)，需要發(fā)送一個(gè) Request-For-Ownership (RFO)消息，這包含一個(gè)讀操作再加上廣播通知其他拷貝失效。

共享（Shared）： 表明緩存行是一個(gè)與主內(nèi)存一致的拷貝。

失效（Invalid）： 表明是一個(gè)無(wú)效的緩存行。

向前（ Forward ）： 一個(gè)特殊的共享狀態(tài)。用來(lái)表示在NUMA體系中響應(yīng)其他緩存的特定緩存。

為了從一個(gè)狀態(tài)轉(zhuǎn)變?yōu)榱硪粋€(gè)狀態(tài)，在緩存之間，需要發(fā)送一系列的消息使?fàn)顟B(tài)改變生效。對(duì)于上一代（或之前）的 Nehalem核心的Intel CPU和 Opteron核心的AMD CPU，插槽之間確保緩存一致性的流量需要通過(guò)內(nèi)存總線共享，這極大地限制了可擴(kuò)展性。如今，內(nèi)存控制器的流量使用一個(gè)多帶帶的總線來(lái)傳輸。例如，Intel的QPI和AMD的HyperTransport就用于插槽間的緩存一致性通訊。

緩存控制器作為L(zhǎng)3緩存段的一個(gè)模塊連接到插槽上的環(huán)行總線網(wǎng)絡(luò)。每一個(gè)核心，L3緩存段，QPI控制器，內(nèi)存控制器和集成圖形子系統(tǒng)都連接到這個(gè)環(huán)行總線上。環(huán)由四個(gè)獨(dú)立的通道構(gòu)成，用于：在每個(gè)時(shí)鐘內(nèi)完成請(qǐng)求、嗅探、確認(rèn)和傳輸32-bytes的數(shù)據(jù)。L3緩存包含所有L1和L2緩存中的緩存行，這有助于幫助核心在嗅探變化時(shí)快速確認(rèn)改變的行。用于L3緩存段的緩存控制器記錄了哪個(gè)核心可能改變自己的緩存行。

如果一個(gè)核心想要讀取一些數(shù)據(jù)，并且這些數(shù)據(jù)在緩存中并不處于共享、獨(dú)占或者被修改狀態(tài)；那么它就需要在環(huán)形總線上做一個(gè)讀操作。它要么從主內(nèi)存中讀?。ň彺鏇](méi)命中），要么從L3緩存讀?。ㄈ绻麤](méi)過(guò)期或者被其他核心嗅探到改變）。在任何情況下，一致性協(xié)議都能保證，讀操作永遠(yuǎn)不會(huì)從緩存子系統(tǒng)返回一份過(guò)期拷貝。

如果我們的緩存總是保證一致性，那么為什么我們?cè)趯懖l(fā)程序時(shí)要擔(dān)心可見性？這是因?yàn)楹诵臑榱说玫礁玫男阅埽瑢?duì)于其它線程來(lái)說(shuō)，可能會(huì)出現(xiàn)數(shù)據(jù)修改的亂序。這么做主要有兩個(gè)理由。

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

排序的第二個(gè)主要問(wèn)題是，一個(gè)線程寫了一個(gè)變量，然后很快讀取，有可能從讀緩沖中獲得比緩存子系統(tǒng)中最新值要舊的值。這對(duì)于遵循單寫入者原則（Single Writer Principle）的程序來(lái)說(shuō)沒(méi)有任何問(wèn)題，但是對(duì)于
Dekker 和Peterson鎖算法就是個(gè)很大問(wèn)題。為了克服這一點(diǎn)，并且確保最新值可見，線程不能從本地讀緩沖中讀取值?？梢允褂闷琳现噶?，防止下一個(gè)讀操作在另一線程的寫操作之前發(fā)生。在Java中對(duì)一個(gè)volatile變量進(jìn)行寫操作，除了永遠(yuǎn)不會(huì)在寄存器中分配之外，還會(huì)伴隨一個(gè)完全的屏障指令。在x86架構(gòu)上，屏障指令在讀緩沖排空之前，會(huì)顯著影響放置屏障的線程的運(yùn)行。在其它處理器上，屏障有更有效率的實(shí)現(xiàn)，例如 Azul Vega在讀緩沖上放置一個(gè)標(biāo)志用于邊界搜索。

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

回到作為并發(fā)算法中的一部分的“刷新緩存”誤區(qū)上，我想，可以說(shuō)我們永遠(yuǎn)不會(huì)在用戶空間的程序上“刷新”CPU緩存。我相信這個(gè)誤區(qū)的來(lái)源是由于在某些并發(fā)算法需要刷新、標(biāo)記或者清空store緩沖以使下一個(gè)讀操作可以看到最新值。為了達(dá)到這點(diǎn)，我們需要內(nèi)存屏障而非刷新緩存。

這個(gè)誤解的另一個(gè)可能來(lái)源是，L1緩存，或者 TLB，在上下文切換的時(shí)候可能需要根據(jù)地址索引策略進(jìn)行刷新。ARM，在ARMv6之前，沒(méi)有在TLB條目上使用地址空間標(biāo)簽，因此在上下文切換的時(shí)候需要刷新整個(gè)L1緩存。許多處理器因?yàn)轭愃频睦碛尚枰狶1指令緩存刷新，在許多場(chǎng)景下，僅僅是因?yàn)橹噶罹彺鏇](méi)有必要保持一致。上下文切換消耗很大，除了污染L2緩存之外，上下文切換還會(huì)導(dǎo)致TLB和/或者L1緩存刷新。Intel x86處理器在上下文切換時(shí)僅僅需要TLB刷新。

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

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