一個位址被允許坐在哪裡？
第 1 篇留給我們的是：一條 64 位元組的快取列作為記憶體與快取之間搬動的單位，以及一個比它所擋的記憶體小上數千倍的快取。那份「小」逼出本篇開場的一個硬問題：當一條列抵達時，它該進到快取的哪一個槽？數百萬個位址正在爭奪區區數千個槽，所以快取不能就「任意放哪都行、再寄望快速找回」。結合度就是回答這件事的規則——它釘死了「某個給定位址被允許佔據哪些槽」，而它正是那個決定「一個理論上夠大的快取究竟表現好不好」的單一設計選擇。
想像一間劇院的衣帽寄存處。最僵硬的設計給每件外套恰好一個編號掛鉤，直接從你的號碼牌算出來——這是直接對映（direct-mapped）快取。查找瞬間完成（只看那一個掛鉤），但若你整個冬天都在穿的兩件外套碰巧對映到同一個掛鉤，它們就永遠互相把對方擠掉，即使另外一百個掛鉤空著。相反的極端，讓你的外套可以掛在任何一個空掛鉤上——這是全結合（fully-associative）快取。沒有任何外套會因對映碰撞而被迫離開，但要找到你的外套，服務員得檢查每一個掛鉤，這慢到無法在每次記憶體存取時都做，因此只保留給極小的結構。真實的資料快取活在那個合理的中間地帶。
那個中間地帶就是組相聯（set-associative）快取，也是幾乎每一個 L1、L2、L3 實際上的樣子。快取被切成若干組（set）；每個位址恰好對映到一組（所以查找只檢查那一組，保持快速），但在那一組之內，列可以坐在 N 個路（way）中的任何一個——因此叫做 N 路組相聯快取，常見 4 路、8 路或 16 路。它就是那間衣帽寄存處：你的號碼牌把你送往某一排特定的掛鉤，而你的外套可以掛在那一排的任何一個掛鉤上。你以查找成本的一小部分，換得全結合大部分的抗碰撞能力。整個快取結合度這個主題，其實就只是替「你在這條從一路到全路的光譜上挑的那個點」命名而已。
硬體實際上如何安放一條列
機制在此，而它美妙地具體。為了安放或尋找一條列，硬體把位址剁成三個欄位。最低的幾個位元是偏移（offset）——指 64 位元組列裡的哪個位元組（一條 64 位元組的列需要 6 個位元，因為 2^6 = 64）。接下來的幾個位元是索引（index）——指這個位址屬於哪一組。其餘的高位元是標籤（tag），它被存在快取中該列的旁邊，好讓硬體能確認「共用這一組索引的眾多位址中，究竟是哪一個實際在場」。沒有除法、沒有橫掃整個快取的搜尋：幾次位元抽取就挑出那一組，接著那一組裡的少數幾個標籤被平行比對。
address = [ tag | index | offset ] (one 64-bit address)
high mid low
Example: 32 KiB, 8-way, 64-byte lines
sets = 32768 / 64 / 8 = 64 sets
offset = low 6 bits (byte within the 64-byte line, 2^6 = 64)
index = next 6 bits (selects 1 of 64 sets, 2^6 = 64)
tag = remaining high bits
0x10000 -> offset 0, index 0, tag ...01
0x20000 -> offset 0, index 0, tag ...10
same index -> both fall in set 0 -> they compete for its 8 ways現在危險顯露出來了。因為索引是位址中段位元的一個固定切片，相隔恰好等於組步距的那些位址會共用一個索引，於是在同一組裡互鬥。經典陷阱是以 2 的次方為步幅走訪記憶體：若你走訪一個陣列、每隔 4096 位元組碰一個元素，而 4096 碰巧是（組數 × 列大小）的倍數，那麼每一個被碰到的位址都對映到同一組，於是你把一個 8 路的組弄到抖動，而另外 63 組空著。這正是為何陣列步幅 1024 可能比步幅 1023 慢上一大截——差一個就打破了 2 的次方對齊造成的別名，把位址重新分散到各組。快取自始至終都夠大；是那條安放規則打敗了你。
一條列不在你想要之處的三種理由
一次快取失誤（cache miss），就只是中央處理器索取「它所查的快取並不持有的資料」的那一刻，於是它必須去更慢的一層、並在等待時停滯。但並非所有失誤都有相同的成因，而既然每個成因有不同的解藥，一個著名的分類——三個 C——便依根本成因把它們分類。知道哪個 C 在你的熱迴圈裡佔主導，就精準地告訴你該改什麼，而不必用猜的。這是快取失誤三個 C的精髓，也是從「理解硬體」通往「真正讓程式變快」的橋。
- 強制（冷）失誤——對一條列有史以來的第一次觸碰。資料根本從未被載入過，所以它當然不在。任何手段都阻止不了那最初的一次存取，但硬體預取能提早發出它、在你開口之前就發，藉以隱藏其延遲。
- 容量失誤——你的工作集（你正積極重用的所有資料）就是比快取大，於是較舊的列在你迴圈回頭用它們之前就被擠掉了，即使在一個理想的全結合快取裡也一樣。解藥是縮小工作集：以快取大小的磚塊（tile）或區塊（block）來處理資料。
- 衝突失誤——那些「本來放得進快取」的列，卻因為在快取有限的結合度下對映到同一組而互相擠掉。這就是上一節那個 2 的次方步幅陷阱。解藥是改變佈局或步幅，讓位址分散到更多組，或仰賴更高的結合度。
實務流程就由此自然導出。用硬體效能計數器量你的失誤率，再從存取模式去推斷哪個 C 佔主導——因為真實的計數器只回報總失誤率，而非那是哪個 C；三個 C 是一個用來思考的模型，而非硬體回報的細目。強制失誤偏多的程式要的是預取。容量失誤偏多的要的是分塊與更小的資料（課本例子是把矩陣相乘分塊成放得進 L1 的 B×B 區塊，把串流式的容量失誤轉成重用命中）。衝突失誤偏多的要的是填充與步幅調整。診斷出成因，解法就自己報上名來。
當你寫入時發生什麼事？
我們一直在談讀取。寫入帶出它自己的一對問題，而答案——快取寫入策略——即使你很少親自選擇，仍能解釋真實的效能行為。第一個問題是何時把改動往下推到記憶體。一個寫透（write-through）快取把每一次寫入立刻轉送到下一層：記憶體永遠是最新的，但寫入流量沉重。一個寫回（write-back）快取——幾乎每一個現代 L1、L2、L3 所用的——則只更新被快取的列並把它標記為髒（dirty），要到該列被擠出時才懶惰地把它寫回記憶體。這把對同一列的許多次寫入收攏成最終單一的一次記憶體寫入，正是寫回成為效能預設值的原因。
第二個問題是當你寫一個根本還沒被快取的位址時該怎麼辦。一個寫入配置（write-allocate）策略會先把該列拉進快取（讓這次寫入、以及它所預期附近的未來寫入，都變成快速的快取寫入）；一個非寫入配置（no-write-allocate）策略則直接越過、寫到記憶體而不快取。常見的搭配——除非另有說明、否則你可以假設的那一個——是寫回加寫入配置。由此導出兩個真實後果。第一，因為寫回快取握著髒資料，DRAM 可能落後於中央處理器實際算出的結果，直到擠出為止，這正是為何記憶體映射的裝置暫存器與 DMA 緩衝區必須小心處理（常被標記為不可快取、或被明確清刷）。第二，當你寫一個永遠不會讀回的全新緩衝區時，寫入配置很浪費：硬體盡責地把每一列的舊內容載入進來，只為了把它們覆寫掉——這正是為何存在非暫存（串流）儲存指令，好在你明知短期內不會把資料讀回時繞過快取。
多個快取，一個真相：MESI 協定
至此一切都假設只有一個快取。但每個核心都有自己的 L1（且通常有 L2），所以同一條記憶體列可能同時被複製進好幾個快取裡。想像四位同事各自握著同一份試算表的影印本：其中一人一改某格，其他每一份影本就悄悄地錯了。快取一致性協定的工作，就是防止這件事的帳務——它保證沒有任何核心會在另一核心改動某列之後，還讀到那一列的過時副本。MESI 是達成此事的經典協定，它的名字就只是一條被快取的列所能處於的四種狀態而已。
每個快取裡的每一條列都帶著四種狀態之一。Modified（M，已修改）：本核心握著唯一的副本且它已被改動（髒）；記憶體是過時的，本核心必須在別人能讀它之前先寫回。Exclusive（E，獨佔）：本核心握著唯一副本且它與記憶體相符（乾淨）；它可以被悄悄寫入、直接滑進 M，無需通知任何人。Shared（S，共享）：本核心握著一份乾淨副本，其他核心也可能握著乾淨副本；讀取免費，但寫入前必須先把其他份作廢。Invalid（I，無效）：這個項目是空的或已過時，必須重新抓取。各核心透過互連匯流排交談：要寫一個其他核心以 S 持有的列，某核心會廣播一個作廢（invalidate）訊息並等待對方把副本降為 I——之後它才能把該列移到 M 並寫入。讀取另一核心以 M 持有的列，會迫使那個核心寫回並降級。（變體微調了這套：MESIF 多了一個 Forward 狀態，讓一個共享者來回應請求；MOESI 多了一個 Owned 狀態，讓一條髒的列可以被共享而不必先寫回。）這就是 MESI 一致性協定的完整樣貌。
這個協定是每個並行程式設計師遲早會遇到的兩種代價背後的隱藏機制。第一個是偽共享：兩個核心各自寫兩個不同、卻碰巧共用同一條 64 位元組列的變數，會讓那條列在它們的 M 狀態之間不斷彈跳，在互連匯流排上彼此作廢——即使它們從未碰到同一個位元組。一個看起來乾淨的迴圈被悄悄序列化成「作廢再重抓」，而光是一致性流量你就能看到百倍的拖慢。修法是把那些變數填充到分開的列上（每 64 位元組一個），讓兩個核心不再互鬥。第二個代價是原子讀-改-寫：按定義它必須以類獨佔的狀態取得那條列，好讓沒有其他核心能交錯插入，這正是為何「無競爭的原子操作」便宜、而「高度競爭的原子操作」會在一致性上序列化——每個核心都排隊去獨佔同一條列。那條列，又一次，成了競爭的單位。