背景

• Read the fucking source code!  --By 魯迅

• A picture is worth a thousand words. --By 高爾基

說明：

1. Kernel 版本：4.14

2. ARM64 處理器，Contex-A53，雙核

3. 使用工具：Source Insight 3.5， Visio

1. 概述

先來看一下經典的存儲器層次結構圖：

• 不同存儲器技術的訪問時間差異很大，CPU 和主存的速度差距在增大，如果直接從主存進行數據的 load/store，CPU 的大部分時間將會處在等待的狀態；

• cache 的作用就是來解決 CPU 與主存的速度不匹配問題；

以 ARMv8 的 CPU 架構爲例：

• ARMv 架構的 CPU 通常包含兩級或多級 cache；

• L1 cache 爲 Core 所獨享的，通常包含 Instruction cache 和 Data cache；

• L2 cache 爲同一個 Cluster 中的多個 Core 進行共享；

• L3 cache 通常實現爲外部的硬件模塊，可以在 Cluster 之間進行共享，或者與其他 IP 進行共享；

接下來讓我們對 cache 一探究竟。

2. cache

2.1 cache 結構

先看一下 cache 的內部結構圖：

• cache line：cache 按行來組織，它是訪問 cache 的最小單位，通常爲 16、32、64 或 128 字節，cache line的大小通常在架構設計階段確定；

• 64-bit address：CPU 訪問 cache 的地址編碼，分成三部分：Tag、Index、Offset；

• Index：地址編碼中的 index 域，用於索引cache line；

• Offset：地址編碼中的 offset 域，cache line中的偏移量，可按word和byte來尋址；

• Tag：Tag在 cache 中佔用實際的物理空間，用於存儲緩存地址的高位部分，通過與地址編碼中的Tag域進行比較來確定是否cache hit；

• Way：cache 分成大小相同的子塊，每個子塊以相同的方式進行索引；

• Set：所有Way中相同的索引對應的cache line組成的集合；

2.2 cache 映射

2.2.1 direct mapped

直接映射的方式如下：

• 圖中的示例 cache 只有四個緩存行，內存中index域相同的地址，都會映射到 cache 中的同一行上；

• 圖中所示，0x00,0x40,0x80三個地址會映射到 cache 的第一行，而同一時刻只能允許 1 行；

• 如果有程序訪問區域覆蓋了這三個地址，可能造成 cache line 的頻繁換入換出，從而導致cache thrashing（顛簸）問題；

• 優點是硬件設計簡單，成本低，缺點是 cache 顛簸造成性能問題；

2.2.2 set associative

組相連的映射方式如下：

• 組相聯方式在現代處理器中得到廣泛的使用；

• 圖中示例有兩路 cache，因此每組有兩個緩存行；

• 每個內存地址在映射時，有兩個緩存行可以選擇，替換出去的概率降低了，這也就有效的降低了 cache 顛簸；

• 優點是減少了 cache 顛簸，缺點是成本和複雜度增大；

2.2.3 fully associative

全相連的映射方式如下：

• 內存地址不需要index域，全相連緩存相當是 N 路集中的所有緩存行，因此需要大量的比較器；

• 優點是最大程度降低 cache 顛簸，缺點依然是複雜度和成本問題；

2.3 cache 策略

• Read allocation(RA) 當讀操作cache miss時默認進行分配cache line；

• Write allocation(WA) 當寫操作cache miss時，會觸發一個 burst 讀，通過讀的方式來分配cache line，然後再將數據寫入 cache；

• Write-back(WB) WB 方式下，數據只寫入 cache，並標記爲 dirty，當cache line被換出或者顯式的 clean 操作纔會更新到外部內存中，如下圖：

• Write-through(WT) WT 方式下，數據同時寫入 cache 和外部內存，不會將cache line標記爲 dirty，如下圖：

2.4 cache 分類

先來看看 cache 中的重名 (aliasing) 問題和同名 (homonyms) 問題：

• aliasing：多個不同的虛擬地址可能映射到相同的物理地址；

• 引入的問題包括：1）浪費 cache 的空間，造成性能下降；2）寫操作時可能造成 cache 數據更新不一致，造成物理地址在 cache 中維護多個不同的數據；

• homonyms：相同的虛擬地址映射到不同的物理地址；

• 引入的問題：比如進程切換時，上一個進程的相同虛擬地址在 cache 中的數據，對於本進程無用，需要額外的invalidate操作；

2.4.1 VIVT(Virtually-Indexed Virtually-Tagged)

• VIVT：處理器使用虛擬地址來進行 cache 的尋址操作，使用虛擬地址的Tag域和Index域進行判斷是否 hit；

• 導致 cache 重名問題（Index 域導致）與同名問題（Tag 域導致），當改變虛擬地址到物理地址映射時，需要flush和invalidate操作，導致性能下降；

2.4.2 PIPT(Physically-Indexed Physically-Tagged)

• PIPT：處理器使用物理地址進行 cache 的尋址操作，使用物理地址的Tag域和Index域進行判斷是否 hit；

• 處理器在查詢 cache 時，需要先查詢 MMU/TLB 後才能訪問，增加了 pipeline 的時間；

• 能有效避免重名和同名問題，但是硬件的設計複雜度和成本更高；

2.4.3 VIPT(Virtually-Indexed Physically-Tagged)

• VIPT：使用虛擬地址的Index域和物理地址的Tag域進行判斷是否 cache hit；

• 使用物理地址的Tag域(物理 Tag 唯一)，能有效的避免同名問題；

• VIPT 也可能存在重名問題，以 Linux 爲例，Linux 內核以 4KB 的頁面大小進行管理，虛擬地址和物理地址的 [11:0] 是相同的，重名問題下多個虛擬地址的 [11:0] 是一樣的。當 index 索引域在 [11:0] 之內時，不會發生重名問題，因爲該範圍屬於一個頁面內；

3. mesi

先來看問題的引入：

• 圖中的 cluster，不同 CPU core 的 cache 和 DDR 中可能維護了同一個數據的多個副本；

• 維護 cache 的一致性，需要跟蹤 cache 行的狀態，ARM 採用 MESI 協議（snooping protocol）來維護 cache 的一致性；

MESI 協議的名字來源於 cache line 的四個狀態：

• Modified（M）：cache line 數據有效，cache line 數據被修改，與內存中的數據不一致，修改的數據只存在本 cache 中；

• Exclusive（E）：cache line 數據有效，cache line 數據和內存中一致，數據只存在本 cache 中；

• Shared（S）：cache line 數據有效，cache line 數據和內存中一致，數據存在於多個 cache 中；

• Invalid（I）：cache line 數據無效；

狀態說明如下：

1. M 和 E 狀態，數據都是本地獨有的，不同點在於 M 狀態的數據是髒的，而 E 狀態的數據是乾淨的，M 狀態的 cache line 寫回內存後，狀態變成了 S；

2. S 狀態的 cache line，數據和其他 cache 共享，只有乾淨的數據才能被多個 cache 共享；

MESI 協議在總線上的操作分爲兩大類：CPU 請求和總線請求，如下圖：

MESI 協議中涉及到各個狀態的轉換：

1. 本地 CPU 操作，狀態轉換如下圖：

• 操作爲本地 CPU 讀寫

2. 總線監聽到其他 CPU 的操作請求，狀態轉換如下圖：

• 操作類型爲總線讀寫，來自其他 CPU 的請求，或者 DMA 的操作等；

當多個 cpu 訪問同一個 cache line 中的不同數據時，根據 MESI 協議，容易造成 cache 的僞共享問題，解決方式是讓多線程操作的數據處在不同的 cache line 中。

收工了。

參考

《 ARM Cortex-A Series  Programmer's Guide for ARMv8-A》

《ARMv8-A CPU Architecture Overview》

《奔跑吧Linux內核》

Lecture 8. Memory Hierarchy Design II

TEACHING THE CACHE MEMORY COHERENCE WITH THE MESI PROTOCOL SIMULATOR

Cache 組織方式

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/NlWvs_fjWSSvW2S1FcpgkQ