Cache的基本概念與工作原理

1.背景知識(shí)

隨著 CPU 技術(shù)的飛速發(fā)展，常用的處理器飛奔在越來(lái)越高的頻率之上，雖然處理器的速度越來(lái)越快，但是與之相匹配的存儲(chǔ)器的速度卻沒(méi)有獲得相應(yīng)的提升，這大大限制了 CPU 的處理性能。而我們本系列文檔所介紹的主角 Cache 技術(shù)就是用來(lái)解決這個(gè)難題的。

在 ARM 發(fā)布 Cortex-M7 架構(gòu)之后，微控制器領(lǐng)域也出現(xiàn)了頻率高達(dá)數(shù)百兆的芯片，如 ST 的 STM32F7 系列和 NXP 的 i.MX RT 系列芯片，這些芯片內(nèi)的處理器都自帶 cache，在合理配置下可以表現(xiàn)出十分強(qiáng)悍的數(shù)據(jù)處理性能。那么什么是 cache？如何利用這一新特性編寫(xiě)高性能的程序？又有什么要注意的地方嗎？你可能會(huì)有上述這些疑問(wèn)，別擔(dān)心，本系列文章將會(huì)為你一一解答。

本系列文章分為三篇，第一篇為 《cache 的基本概念與工作原理》，講解 cache 相關(guān)的基礎(chǔ)知識(shí)。第二篇為《STM32F7 Cache 介紹與實(shí)戰(zhàn)》，講解如何在 STM32F7 系列芯片上使用 cache，并編寫(xiě)程序進(jìn)行性能測(cè)試。第三篇為《Cache 的一致性問(wèn)題與使用技巧》，將會(huì)介紹 cache 的數(shù)據(jù)一致性問(wèn)題和使用 cache 過(guò)程中的一些技巧。下面我們從 cache 的基礎(chǔ)知識(shí)開(kāi)始，了解這一強(qiáng)大的特性吧。

2. 計(jì)算機(jī)的層次結(jié)構(gòu)存儲(chǔ)系統(tǒng)

想要理解 cache 的工作原理，就必須要了解計(jì)算機(jī)系統(tǒng)中數(shù)據(jù)的存儲(chǔ)方式。

在計(jì)算機(jī)中程序執(zhí)行時(shí)所有的指令和數(shù)據(jù)都是從存儲(chǔ)器中取出來(lái)執(zhí)行的。存儲(chǔ)器是計(jì)算機(jī)系統(tǒng)中的重要組成部分，相當(dāng)于計(jì)算機(jī)的倉(cāng)庫(kù)，用來(lái)存放各類程序及其處理的數(shù)據(jù)。因此存儲(chǔ)器的容量和性能應(yīng)當(dāng)隨著處理器的速度和性能的提高而通過(guò)提高，以保持系統(tǒng)性能的平衡。

然而在過(guò)去的 20 多年中，隨著時(shí)間的推移，處理器和存儲(chǔ)器在性能發(fā)展上的差異越來(lái)越大，存儲(chǔ)器在容量尤其是訪問(wèn)延時(shí)方面的性能增長(zhǎng)越來(lái)越跟不上處理器性能發(fā)展的需要。為了縮小存儲(chǔ)器和處理器兩者之間在性能方面的差距，通常在計(jì)算機(jī)內(nèi)部采用層次化的存儲(chǔ)器體系結(jié)構(gòu)。

從上圖可以看到，速度越快則容量越小、越靠近 CPU。CPU 可以直接訪問(wèn)內(nèi)部存儲(chǔ)器。而外部存儲(chǔ)器的信息則要先取到主存，然后才能被 CPU 訪問(wèn)。CPU 執(zhí)行指令時(shí)，需要的操作數(shù)大部分來(lái)自寄存器，當(dāng)需要對(duì)存儲(chǔ)器進(jìn)行讀寫(xiě)操作時(shí)，先訪問(wèn) cache ，如果不在 cache 中，則訪問(wèn)主存，如果不在主存中，則訪問(wèn)硬盤(pán)。此時(shí)，操作數(shù)從硬盤(pán)中讀出送到主存，然后從主存送到 cache。

數(shù)據(jù)使用時(shí)，一般只在相鄰兩層之間復(fù)制傳送，而且總是從慢速存儲(chǔ)器復(fù)制到快速存儲(chǔ)器。傳送的單位是一個(gè)定長(zhǎng)塊，因此需要確定定長(zhǎng)塊的大小，并且在相鄰兩層間建立塊之間的映射關(guān)系。

在我們接觸的嵌入式系統(tǒng)中，具體的存取時(shí)間和存儲(chǔ)容量的大小可能和上圖不符，但是不同層級(jí)之間的量級(jí)對(duì)比還是一致的。

3. 為什么需要 Cache?

由于 CPU 和主存所使用的半導(dǎo)體器件工藝不同，兩者速度上的差異導(dǎo)致快速的 CPU 等待慢速的存儲(chǔ)器，為此需要想辦法提高 CPU 訪問(wèn)主存的速度。除了提高 DRAM 芯片本身的速度和采用并行結(jié)構(gòu)技術(shù)以外，加快 CPU 訪存速度的主要方式之一是在 CPU 和主存之間增加高速緩沖器，也就是我們主角 Cache。

Cache 位于 CPU 和內(nèi)存之間，可以節(jié)省 CPU 從外部存儲(chǔ)器讀取指令和數(shù)據(jù)的時(shí)間。

4. 基本概念

程序訪問(wèn)的局部性

對(duì)大量典型程序運(yùn)行情況分析的結(jié)果表明，在較短的時(shí)間間隔內(nèi)，程序產(chǎn)生的地址往往集中在存儲(chǔ)空間的一個(gè)很小范圍，這種現(xiàn)象稱為程序訪問(wèn)的局部性。這種局部性可細(xì)分為時(shí)間局部性和空間局部性。時(shí)間局部性是指被訪問(wèn)的某個(gè)存儲(chǔ)單元在一個(gè)較短的時(shí)間間隔很可能又被訪問(wèn)?？臻g的局部性是指訪問(wèn)的某個(gè)存儲(chǔ)單元的臨近單元在一個(gè)較短的時(shí)間間隔內(nèi)很可能也被訪問(wèn)。

Instruction Cache

指令 cache 只被用于緩存指令，從外部存儲(chǔ)器讀取指令需要很長(zhǎng)時(shí)間，如果外部存儲(chǔ)器是 flash，那么 CPU 可能需要 50-100ns 才能獲得指令。

Data Cache

數(shù)據(jù) cache 只被用于緩存數(shù)據(jù)，和指令 cache 類似，CPU 要花費(fèi)很長(zhǎng)時(shí)間才能從外部的 SRAM 或者 SDRAM 取回?cái)?shù)據(jù)。

5. 工作原理

cache 是一種小容量高速緩沖存儲(chǔ)器，由快速的 SRAM 組成，直接制作在 CPU 芯片內(nèi)，速度較快，幾乎與 CPU 處于同一個(gè)量級(jí)。在 CPU 和主存之間設(shè)置 cache，總是把主存中被頻繁訪問(wèn)的活躍程序塊和數(shù)據(jù)塊復(fù)制到 cache 中。由于程序訪問(wèn)的局部性，大多數(shù)情況下，CPU 可以直接從 cache 中直接取得指令和數(shù)據(jù)，而不必訪問(wèn)慢速的主存。

為了方便 cache 和主存間交換信息，cache 和主存空間都被劃分為相等的區(qū)域。例如將主存中一個(gè) 512 個(gè)字節(jié)的區(qū)域稱作一個(gè)塊（block），cache 中存放一個(gè)主存塊的區(qū)域稱作行（line）。

cache 的行有效位

系統(tǒng)啟動(dòng)時(shí)，每個(gè) cache 行都為空，其中的信息無(wú)效，只有 cache 行中裝入了主存塊之后才有效。為了說(shuō)明 cache 行中的信息是否有效，某一個(gè)行都有一個(gè)有效位。通過(guò)將一行的有效位清零來(lái)淘汰這一行中所存儲(chǔ)的主存快的操作稱為沖刷，也就是我們常說(shuō)的刷 cache。

CPU 在 cache 中的訪問(wèn)過(guò)程

在 CPU 執(zhí)行程序過(guò)程中，需要從主存取指令或?qū)憯?shù)據(jù)時(shí)，先檢查 cache 中有沒(méi)有要訪問(wèn)的信息，若有，就直接在 cache 中讀寫(xiě)，而不用訪問(wèn)主存儲(chǔ)器。若沒(méi)有，再?gòu)闹鞔嬷邪旬?dāng)前訪問(wèn)信息所在的一個(gè)一個(gè)主存塊復(fù)制到 cache 中。因此，cache 中的內(nèi)容是主存中部分內(nèi)容的副本。下圖展示了帶 cache 的 CPU 執(zhí)行一次訪存操作的過(guò)程。

cache 與主存的平均訪問(wèn)時(shí)間

如上圖所示的訪存過(guò)程中，需要判斷所訪問(wèn)的信息是否在 cache 中。若 CPU 訪問(wèn)單元的主存塊在 cache 中，則稱cache 命中（hit），命中的概率稱為命中率 p(hit rate)。若不在 cache 中，則為不命中（miss），其概率為缺失率（miss rate）。命中時(shí)，CPU 在 cache 中直接存取信息，所用的時(shí)間開(kāi)銷就是cache 的訪問(wèn)時(shí)間 Tc，稱為命中時(shí)間。缺失時(shí)，需要從主存讀取一個(gè)主存塊送 cache，并同時(shí)將所需信息送 CPU，因此所用時(shí)間為主存訪問(wèn)時(shí)間 Tm，和cache 訪問(wèn)時(shí)間 Tc之和。通常把從主存讀入一個(gè)主存塊到 cache 的時(shí)間Tm 稱為缺頁(yè)損失。

CPU 在 cache 和主存層次的平均訪問(wèn)時(shí)間為：

Ta = p * Tc + (1 - p) * (Tm + Tc) = Tc + (1 - p) * Tm

由于程序訪問(wèn)的局部性特點(diǎn)，cache 的命中率可以達(dá)到很高，接近于 1。因此，雖然缺頁(yè)損失所耗費(fèi)的時(shí)間遠(yuǎn)遠(yuǎn)大于命中時(shí)間，但最終的平均訪問(wèn)時(shí)間仍可接近 cache 的訪問(wèn)時(shí)間。

cache 的映射方式

cache 行中的信息取自主存中的某個(gè)塊。將主存塊復(fù)制到 cache 行時(shí)，主存塊和 cache 行之間必須遵循一定的映射規(guī)則。這樣 CPU 在要訪問(wèn)某個(gè)主存單元時(shí)，可以依據(jù)映射規(guī)則到 cache 對(duì)應(yīng)的行中查找要訪問(wèn)的信息，而不用在整個(gè) cache 中查找。

根據(jù)不同的映射規(guī)則，主存塊和 cache 行之間有以下三種映射方式。

目前我們常見(jiàn)的 CPU 一般都采用的組相連的映射方式，組相連的映射方式將前兩種映射方式取長(zhǎng)補(bǔ)短，獲得了優(yōu)異的性能和較低的硬件實(shí)現(xiàn)難度。在這里不再展開(kāi)仔細(xì)描述，感興趣的小伙伴可以通過(guò)搜索閱讀相關(guān)內(nèi)容來(lái)了解其中的細(xì)節(jié)。

直接映射（direct）：每個(gè)主存塊映射到 cache 的固定行中。

全相連映射（full associate）：每個(gè)主存塊映射到 cache 的任意行中。

組相連映射（set associate）：每個(gè)主存塊映射到 cache 的固定組的任意行中。

值得注意的是，cache 對(duì)程序員在編寫(xiě)高級(jí)或低級(jí)語(yǔ)言程序時(shí)是透明的，因此程序員無(wú)需了解 cache 是否存在或者如何設(shè)置，感覺(jué)不到 cache 的存在。但是對(duì) cahche 的深入了解有助于編寫(xiě)出高效的程序！