https://www.cs.cmu.edu/~213/lectures/11-memory-hierarchy.pdf

隨機存取存儲器

了解存儲設備所用的技術以及發(fā)展趨勢月幌，對我們理解內存層級背后的原因很有幫助杀赢。

隨機存取存儲器(RAM, Random-Access Memory) 有兩種類型：SRAM(Static RAM) 和 DRAM(Dynamic RAM)筒愚，SRAM 非常快阶祭，也不需要定期刷新，通常用在處理器做緩存缘挽，但是比較貴北发；DRAM 稍慢一點（大概是 SRAM 速度的十分之一），需要刷新盔腔，通常用作主內存杠茬，相比來說很便宜（是 SRAM 價格的百分之一）月褥。

無論是 DRAM 還是 SRAM，一旦不通電瓢喉，所有的信息都會丟失宁赤。如果想要讓數據持久化，可以考慮 ROM, PROM, EPROM, EEPROM 等介質栓票。固件程序會存儲在 ROM 中（比如 BIOS决左，磁盤控制器，網卡走贪，圖形加速器佛猛，安全子系統等等）。另外一個趨勢就是 SSD 固態(tài)硬盤坠狡，取消了機械結構继找，更穩(wěn)定速度更快更省電。

傳統機械硬盤

雖然現在越來越多電腦已經改為使用固態(tài)硬盤擦秽，但是還是有必要了解一下硬盤的組成的码荔。傳統的機械硬盤有許多不同的部件：

image

機械硬盤有許多片磁盤(platter)組成，每一片磁盤有兩面感挥；每一面由一圈圈的磁道(track)組成缩搅，而每個磁道會被分隔成不同的扇區(qū)(sector)。這里概念層層遞進触幼，可以結合下圖仔細辨析清楚硼瓣。

image

上圖是一個磁盤的視圖，多個磁盤組合起來是這樣的：

image

硬盤的容量指的是最大能存儲的比特數置谦，通常用 GB 來做單位堂鲤。1 GB 相當于 10 的 9 次方個 Byte。與硬盤的結構分層類似媒峡，容量取決于下面三個方面：

• 記錄密度(bits/in)：track 中 1 英寸能保存的字節(jié)數
• 磁道密度(tracks/in)：1 英寸直徑能保存多少條 track
• Areal 密度(bits/in 的平方)：上面兩個數值的乘積

現在硬盤會把相鄰的若干個磁道切分成小塊瘟栖，每一塊叫做記錄區(qū)(recording zone)。記錄區(qū)中的每條磁道都包含同樣數量的扇區(qū)(sector)谅阿；但是每個記錄區(qū)中包含的扇區(qū)和磁道的數目是不一樣的半哟，外層的更多，內層的更少签餐；正因為如此寓涨，我們計算容量是，用的是平均的數值氯檐。

容量 Capacity = 每個扇區(qū)的字節(jié)數(bytes/sector) x 磁道上的平均扇區(qū)數(avg sectors/track) x 磁盤一面的磁道數(tracks/surface) x 磁盤的面數(surfaces/platter) x 硬盤包含的磁盤數(platters/disk)

舉個例子戒良，假如一個硬盤有：

• 512 bytes/sector
• 300 sectors/track (平均)
• 20000 tracks/surface
• 2 surfaces/platter
• 5 platters/disk

總的容量為 = 512 x 300 x 20000 x 2 x 5 = 30,720,000,000 = 30.72 GB

image

假設我們現在已經從藍色區(qū)域讀取完了數據，接下來需要從紅色區(qū)域讀冠摄，首先需要尋址糯崎，把讀取的指針放到紅色區(qū)域所在的磁道几缭，然后等待磁盤旋轉，旋轉到紅色區(qū)域之后拇颅，才可以開始真正的數據傳輸過程奏司。

總的訪問時間 Taccess = 尋址時間 Tavg seek + 旋轉時間 Tavg rotation + 傳輸時間 Tavg transfer

• 尋址時間 Tavg seek 因為物理規(guī)律的限制，一般是 3-9 ms
• 旋轉延遲 Tavg rotation 取決于硬盤具體的轉速樟插，一般來說是 7200 RPM
• 傳輸時間 Tavg tranfer 就是需要讀取的扇區(qū)數目

舉個例子韵洋，假設轉速是 7200 RPM，平均尋址時間 9ms黄锤，平均每個磁道的 sector 數目是 400搪缨，那么我們有：

• Tavg rotation = 1/2 x (60 secs / 7200 RPM) x 1000 ms/sec = 4 ms
• Tavg transfer = 60 / 7200 RPM x 1/400 secs/track x 1000 ms/sec = 0.02 ms
• Taccess = 9 ms + 4 ms + 0.02 ms

從這里可以看出，主要決定訪問時間的是尋址時間和旋轉延遲鸵熟；讀取一個扇區(qū)的第一個比特是非常耗時的副编，之后的都幾乎可以忽略不計；硬盤比 SRAM 慢 40,000 倍流强，比 DRAM 慢 2500 倍痹届。

最后需要知道的就是邏輯分區(qū)和實際的物理分區(qū)的區(qū)別，為了使用方便打月，會用連續(xù)的數字來標志所有可用的扇區(qū)队腐，具體的映射工作由磁盤控制器完成。

固態(tài)硬盤

接下來介紹一下固態(tài)硬盤奏篙，內部結構如下

image

固態(tài)硬盤中分成很多的塊(Block)柴淘，每個塊又有很多頁(Page)，大約 32-128 個秘通，每個頁可以存放一定數據（大概 4-512KB）为严，頁是進行數據讀寫的最小單位。但是有一點需要注意肺稀，對一個頁進行寫入操作的時候第股，需要先把整個塊清空（設計限制），而一個塊大概在 100,000 次寫入之后就會報廢话原。

與傳統的機械硬盤相比炸茧，固態(tài)硬盤在讀寫速度上有很大的優(yōu)勢。但是因為設計本身的約束稿静，連續(xù)訪問會比隨機訪問快，而且如果需要寫入 Page辕狰，那么需要移動其他 Page改备，擦除整個 Block，然后才能寫入÷叮現在固態(tài)硬盤的讀寫速度差距已經沒有以前那么大了悬钳，但是仍然有一些差距盐捷。

不過與機械硬盤相比，固態(tài)硬盤存在一個具體的壽命限制默勾，價格也比較貴碉渡，但是因為速度上的優(yōu)勢，越來越多設備開始使用固態(tài)硬盤母剥。

總線

總線是用來傳輸地址滞诺、數據和控制信號的一組平行的電線，通常來說由多個設備共享环疼，類似于不同城市之間的高速公路习霹，可以傳輸各類數據。CPU 通過總線和對應的接口來從不同的設備中獲得所需要的數據炫隶，放入寄存器中等待運算淋叶，像下面這樣：

image

假設 CPU 需要從硬盤中讀取一些數據，會給定指令伪阶，邏輯塊編號和目標地址煞檩，并發(fā)送給磁盤控制器。然后磁盤控制器會讀取對應的數據栅贴，并通過 DMA(direct memory access)把數據傳輸到內存中斟湃；傳輸完成后，磁盤控制器通過中斷的方式通知 CPU筹误，然后 CPU 完成之后的工作桐早。

總線上連接的各個設備，其訪問速度有天壤之別厨剪，不同的技術發(fā)展速度不同哄酝，更加劇了這個情況

image

比方說磁盤的讀寫速度，30 年大概只提高了一個數量級多一點祷膳，所以固態(tài)硬盤的出現陶衅，以下拯救了勞苦大眾（提高了兩個數量級），DRAM 的發(fā)展直晨，一路從 DDR12345 發(fā)展來搀军，速度大概提高了一個數量級，不過 SRAM 則是在同一個起點愣是多跑了一個數量級勇皇，總體來說是跟著 CPU 的發(fā)展走的罩句。不過 CPU 的發(fā)展在 2003 年也遇到了問題（單個核心基本到極限），不過多核的出現以及技術優(yōu)化敛摘，總體來說還是使得執(zhí)行速度越來越快门烂。

那么這么大的時間差距，怎么辦呢？難道根據木桶理論屯远，都要取決于最慢的那個嗎蔓姚？不一定！局部性原理(Locality)可以在一定程度上拯救世界慨丐。

局部性原理 Locality

局部性的思路很簡單[2]：

• 時間局部性(Temporal Locality): 如果一個信息項正在被訪問坡脐，那么在近期它很可能還會被再次訪問。程序循環(huán)房揭、堆棧等是產生時間局部性的原因备闲。
• 空間局部性(Spatial Locality): 在最近的將來將用到的信息很可能與現在正在使用的信息在空間地址上是臨近的
• 順序局部性(Order Locality): 在典型程序中，除轉移類指令外崩溪，大部分指令是順序進行的浅役。順序執(zhí)行和非順序執(zhí)行的比例大致是5:1。此外伶唯，對大型數組訪問也是順序的觉既。指令的順序執(zhí)行、數組的連續(xù)存放等是產生順序局部性的原因乳幸。

舉個例子：

sum = 0;

for (i = 0; i < n; i++){

    sum += a[i];

}

return sum;

這里每次循環(huán)都會訪問 sum 是滿足時間局部性的瞪讼；數組的訪問是連續(xù)的，屬于空間局部性粹断。

根據這個特性符欠，在寫遍歷數組的時候（尤其是高維），尤其要注意按照內存排列順序來訪問瓶埋，不然性能會慘不忍睹希柿。

存儲體系 Memory Hierarchy

一種介質的速度越快就會越貴，同時也消耗更多的電量养筒，所以一般容量比較小曾撤。而 CPU 和內存之間的速度差距越來越大，所以好的程序都會盡可能利用局部性晕粪。而根據這些特性挤悉，引申出了安排存儲的方式，稱為金字塔式存儲體系(Memory Hierarch)巫湘。

image

這里就涉及到一個技術：緩存装悲。緩存可以看作是把大且緩慢的設備中的數據的一部分拿出來存儲到其中的更快的存儲設備。在金字塔式存儲體系[3]中尚氛，每一層都可以看作是下一層的緩存诀诊。利用局部性原理，程序會更傾向于訪問第 k 層的數據阅嘶，而非第 k+1 層属瓣，這樣就減少了訪問時間。

通過下表我們可以了解更多細節(jié)：

存儲體系的設計，可以說是利用最便宜的存儲的價格奠涌，提供了最快速的存儲的性能。在我看來真的是做到了『又要馬兒跑磷杏，又要馬兒不吃草』溜畅！在各種限制條件下能夠找到如此優(yōu)美的解決方案，真可謂『帶著鐐銬跳舞』的最高境界极祸！

這里我們舉一個具體的例子來感受一下存儲體系的設計慈格。假設我們有一個包含 20 個元素的數組，而目前在高速緩存中保存著前 10 個元素遥金，那么在訪問數組元素的時候浴捆，如果我們只用到前 5 個，那么都可以從高速緩存中獲取稿械，這種情況就叫做『緩存命中』选泻，要比內存的訪問快得多。而如果訪問了緩存中沒有的元素美莫，就需要從內存中獲取了页眯，由于高速緩存大小的限制，還需要對其中的元素進行替換（具體之后會介紹）厢呵。

緩存未命中的類型

https://www.cs.cmu.edu/~213/lectures/12-cache-memories.pdf
緩存未命中有三種窝撵，這里進行簡要介紹

• 強制性失效(Cold/compulsory Miss): CPU 第一次訪問相應緩存塊，緩存中肯定沒有對應數據襟铭，這是不可避免的
• 沖突失效(Confilict Miss): 在直接相聯或組相聯的緩存中碌奉，不同的緩存塊由于索引相同相互替換，引起的失效叫做沖突失效
  • 假設這里有 32KB 直接相聯的緩存
  • 如果有兩個 8KB 的數據需要來回訪問寒砖，但是這兩個數組都映射到相同的地址赐劣，緩存大小足夠存儲全部的數據，但是因為相同地址發(fā)生了沖突需要來回替換入撒，發(fā)生的失效則全都是沖突失效（第一次訪問失效依舊是強制性失效）隆豹，這時緩存并沒有存滿
• 容量失效(Capacity Miss): 有限的緩存容量導致緩存放不下而被替換，被替換出去的緩存塊再被訪問茅逮，引起的失效叫做容量失效
  • 假設這里有 32KB 直接相聯的緩存
  • 如果有一個 64KB 的數組需要重復訪問璃赡，數組的大小遠遠大于緩存大小，沒辦法全部放入緩存献雅。第一次訪問數組發(fā)生的失效全都是強制性失效碉考。之后再訪問數組，再發(fā)生的失效則全都是容量失效挺身，這時緩存已經存滿侯谁，容量不足以存儲全部數據

深入理解高速緩沖存儲器 Cache Memory

高速緩存存儲器(Cache Memory)是 CPU 緩存系統甚至是金字塔式存儲體系中最有代表性的緩存機制，前面我們了解了許多概念，這一節(jié)我們具體來看看高速緩存存儲器是如何工作的墙贱。

首先要知道的是热芹，高速緩存存儲器是由硬件自動管理的 SRAM 內存，CPU 會首先從這里找數據惨撇，其所處的位置如下（藍色部分）：

image

然后我們需要關注高速緩沖存儲器的三個關鍵組成部分（注意區(qū)分大小寫）：

• S 表示集合(set)數量
• E 表示數據行(line)的數量
• B 表示每個緩存塊(block)保存的字節(jié)數目

在圖上表示出來就是

image

所以緩存中存放數據的空間大小為：

C=S×E×B

實際上可以理解為三種層級關系伊脓，對應不同的索引，這樣分層的好處在于魁衙，通過層級關系簡化搜索需要的時間报腔，并且和字節(jié)的排布也是一一對應的（之后介紹緩存的時候就體現得更加明顯）。

當處理器需要訪問一個地址時剖淀，會先在高速緩沖存儲器中進行查找纯蛾，查找過程中我們首先在概念上把這個地址劃分成三個部分：

image

讀取

具體在從緩存中讀取一個地址時，首先我們通過 set index 確定要在哪個 set 中尋找纵隔，確定后利用 tag 和同一個 set 中的每個 line 進行比對翻诉，找到 tag 相同的那個 line，最后再根據 block offset 確定要從 line 的哪個位置讀起（這里的而 line 和 block 是一個意思）巨朦。

當 E=1 時米丘，也就是每個 set 只有 1 個 line 的時候，稱之為直接映射緩存(Direct Mapped Cache)糊啡，如下圖所示

image

這種情況下拄查，因為每個 set 對應 1 個 line，反過來看棚蓄，1 個 line 就需要一個 set堕扶，所以 set index 的位數就會較多（和之后的多路映射對比）。具體的檢索過程就是先通過 set index 確定哪個 set梭依，然后看是否 valid稍算，然后比較那個 set 里唯一 line 的 tag 和地址的 t bits 是否一致，就可以確定是否緩存命中役拴。

命中之后根據 block offset 確定偏移量糊探，因為需要讀入一個 int，所以會讀入 4 5 6 7 這四個字節(jié)（假設緩存是 8 個字節(jié)）河闰。如果 tag 不匹配的話科平，這行會被扔掉并放新的數據進來。

然后我們來看一個具體的例子姜性，假設我們的尋址空間是 M=16 字節(jié)瞪慧，也就是 4 位的地址，對應 B=2, S=4, E=1部念，我們按照如下順序進行數據讀绕谩：

• 0 00 0, miss
• 0 00 1, hit
• 0 11 1, miss
• 1 00 0, miss
• 0 00 0, miss

緩存中的具體情況是氨菇，這里 x 表示沒有任何內容

       v  Tag   Block

Set 0  1   0    M[0-1]

Set 1  x   x      x

Set 2  x   x      x

Set 3  1   0    M[6-7]

緩存的大小如圖所示，對應就是有 4 個 set妓湘，所以需要 2 位的 set index查蓉，所以進行讀入的時候，會根據中間兩位來確定在哪個 set 中查找榜贴，其中 8 和 0奶是，因為中間兩位相同，會產生沖突竣灌，導致連續(xù) miss，這個問題可以用多路映射來解決秆麸。

當 E 大于 1 時初嘹，也就是每個 set 有 E 個 line 的時候，稱之為 E 路聯結緩存沮趣。這里每個 set 有兩個 line屯烦，所以就沒有那么多 set，也就是說 set index 可以少一位（集合數量少一倍）房铭。

再簡述一下整個過程驻龟，先從 set index 確定那個 set，然后看 valid 位缸匪，接著利用 t bits 分別和每個 line 的 tag 進行比較翁狐，如果匹配則命中，那么返回 4 5 位置的數據凌蔬，如果不匹配露懒，就需要替換，可以隨機替換砂心，也可以用 least recently used(LRU) 來進行替換懈词。

我們再用剛才的例子來看看是否會增加命中率，這里假設我們的尋址空間是 M=16 字節(jié)辩诞，也就是 4 位的地址坎弯，對應 B=2, S=2, E=2，我們按照如下順序進行數據讀纫朐荨：

• 0 00 0, miss
• 0 00 1, hit
• 0 11 1, miss
• 1 00 0, miss
• 0 00 0, hit

緩存中的具體情況是抠忘，這里 x 表示沒有任何內容

       v   Tag   Block

Set 0  1   00    M[0-1]

Set 0  1   10    M[8-9]

Set 1  1   01    M[6-7]

Set 1  0   x     x

可以看到因為每個 set 有 2 個 line，所以只有 2 個 set秧秉，set index 也只需要 1 位了褐桌，這個情況下即使 8 和 0 的 set index 一致，因為一個 set 可以容納兩個數據象迎，所以最后一次訪問 0荧嵌，就不會 miss 了呛踊。

寫入

image.png

在整個存儲層級中，不同的層級可能會存放同一個數據的不同拷貝（如 L1, L2, L3, 主內存, 硬盤）啦撮。如果發(fā)生寫入命中的時候（也就是要寫入的地址在緩存中有）谭网，有兩種策略：

• Write-through: 命中后更新緩存，同時寫入到內存中
• Write-back: 直到這個緩存需要被置換出去赃春，才寫入到內存中（需要額外的 dirty bit 來表示緩存中的數據是否和內存中相同愉择，因為可能在其他的時候內存中對應地址的數據已經更新，那么重復寫入就會導致原有數據丟失）

在寫入 miss 的時候织中，同樣有兩種方式：

• Write-allocate: 載入到緩存中锥涕，并更新緩存（如果之后還需要對其操作，這個方式就比較好）
• No-write-allocate: 直接寫入到內存中狭吼，不載入到緩存

這四種策略通常的搭配是：

• Write-through + No-write-allocate
• Write-back + Write-allocate

其中第一種可以保證絕對的數據一致性层坠，第二種效率會比較高（通常情況下）。

緩存實例

image.png

使用tt ss bb刁笙，可以更好的利用空間局不行破花。

image.png

首先64byte 一個block，得到b 占6位疲吸，8路set座每，e占3位（2^3 = 8)那么s有多少個呢？ 因為緩存一共32KB 大摘悴， 32 * 1024/8/64 = 64 b
所以s占6位（2^6 = 64)

47-7-7 = 35 tag 占35位

image.png

緩存命中的話峭梳，一般l1 需要4個clock cycles. l2 需要10個clock cycles.
如果緩存miss的話，去內存拿需要50-200cycles

差異非常大蹂喻，當cache hit 和 cache miss的時候
Consider this simplified example:

• cache hit time of 1 cycle
• miss penalty of 100 cycles

Average access time:

• 97% hits: 1 cycle + 0.03 x 100 cycles = 4 cycles
• 99% hits: 1 cycle + 0.01 x 100 cycles = 2 cycles

寫緩存友好的代碼

1.把注意力放在核心方法的內部循環(huán)上延赌，找到一些優(yōu)化
2.減少緩存miss在內層循環(huán)，利用空間和時間局部性叉橱。

內存山（memory mountain)

內存山使用了測算讀寫吞吐率和時間空間局部性的方法
下面來看下一段內存山的代碼挫以，

image.png

image.png

重新安排循環(huán)去利用時間局部性

用矩陣乘法作為例子

image.png

image.png

image.png

image.png

使用模塊化（blocking) 來提高空間局部性

image.png

image.png