第六章 存儲器層次結構
第一節 存儲技術
- 三種常見存儲技術：RAM、ROM、磁盤
一、随機通路存儲器RAM
随機存取
所謂“随機存取”，指的是當存儲器中的資料被讀取或寫入時，所需要的時間與這段資訊所在的位置或所寫入的位置無關。相對的，讀取或寫入順序通路（Sequential Access）儲存設備中的資訊時，其所需要的時間與位置就會有關系。它主要用來存放作業系統、各種應用程式、資料等。[1]
易失性
當電源關閉時RAM不能保留資料。如果需要儲存資料，就必須把它們寫入一個長期的儲存設備中（例如硬碟）。RAM和ROM相比，兩者的最大差別
靜态随機存取存儲器
是RAM在斷電以後儲存在上面的資料會自動消失，而ROM不會自動消失，可以長時間斷電儲存。
對靜電敏感
正如其他精細的內建電路，随機存取存儲器對環境的靜電荷非常敏感。靜電會幹擾存儲器内電容器的電荷，引緻資料流失，甚至燒壞電路。故此觸碰随機存取存儲器前，應先用手觸摸金屬接地。
通路速度
現代的随機存取存儲器幾乎是所有通路裝置中寫入和讀取速度最快的，存取延遲
筆記本電腦記憶體
和其他涉及機械運作的儲存設備相比，也顯得微不足道。
需要重新整理（再生）
現代的随機存取存儲器依賴電容器存儲資料。電容器充滿電後代表1(二進制)，未充電的代表0。由于電容器或多或少有漏電的情形，若不作特别處理，資料會漸漸随時間流失。重新整理是指定期讀取電容器的狀态，然後按照原來的狀态重新為電容器充電，彌補流失了的電荷。需要重新整理正好解釋了随機存取存儲器的易失性。
2.動态DRAM（DRAM）：将每個位存儲為對電容的充電。電容約為30×10-15F。
動态RAM的工作原理 動态RAM也是由許多基本存儲元按照行和列位址引腳複用來組成的。
3管動态RAM的工作原理3管動态RAM的基本存儲電路如右圖所示。在這個電路中，讀選擇線和寫選擇線是分開的，讀資料線和寫資料線也是分開的。
寫操作時，寫選擇線為"1"，是以Q1導通，要寫入的資料通過Q1送到Q2的栅極，并通過栅極電容在一定時間内保持資訊。
讀操作時，先通過公用的預充電管Q4使讀資料線上的分布電容CD充電，當讀選擇線為高電平有效時,Q3處于可導通的狀态。若原來存有"1",則Q2導通，讀資料線的分布電容CD通過Q3、Q2放電,此時讀得的資訊為"0"，正好和原存資訊相反；若原存資訊為"0",則Q3盡管具備導通條件，但因為Q2截止，是以，CD上的電壓保持不變，因而，讀得的資訊為"1"。可見，對這樣的存儲電路，讀得的資訊和原來存入的資訊正好相反,是以要通過讀出放大器進行反相再送往 資料總線。
二、非易失性存儲器（ROM）
- 區分：能被重程式設計的次數和對他們進行重程式設計所用的機制
PROM：隻能被程式設計一次。
EPROM：可擦寫可程式設計ROM，紫外線光照清除單元内容，可擦寫次數數量級1000。
E2PROM：電子可擦除PROM，可以直接在印制電路卡上程式設計，可擦寫次數數量級10^5。
FLASH：閃存，基于EEPROM。（固态硬碟SSD基于閃存）
三、通路主存
1.總線：一組并行的導線，能攜帶位址、資料的控制信号。
2.讀事務：從主存傳送資料到CPU
彙編語句：movl A,%eax
3.寫事務：從CPU傳送資料到主存
彙編語句：movl %eax，A
四、磁盤存儲
1.磁盤構造
2.磁盤容量：一個磁盤上可以記錄的最大位數稱為它的最大容量/容量。決定因素：
記錄密度：磁道一英寸的段可以放入的位數。
磁道密度：從盤片中心出發半徑上一英寸的段内可以有的磁道數。
面密度：記錄密度與磁道密度的乘積。
公式：磁盤容量=位元組數/扇區*平均盤區數/磁道*磁道數/表面*表面數/盤片*盤片數/磁盤
3.磁盤操作
磁盤用讀寫頭來讀寫存儲在磁性表面的位，而讀寫頭連接配接到一個轉動臂一端。尋道就是通過沿着半徑軸前後移動這個轉動臂，使得驅動器可以将讀寫頭定位在盤面上的任何磁道上。
（1）動态特性
任何時刻，所有的讀寫頭都位于同一柱面上。
磁盤以扇區大小的塊來讀寫資料。
（2）通路時間 =尋道時間+旋轉時間+傳送時間
a.尋道時間：為了讀取某個目标扇區的内容，傳動臂把讀/寫頭首先定位到包含目标扇區的磁道上，所需時間即為尋道時間，約等于最大旋轉時間。
尋道時間Tseek依賴于讀寫頭以前的位置和轉動臂在盤面上移動的速度。
b.旋轉時間：定位到期望的磁道後，驅動器等待目标扇區的第一個位旋轉到讀/寫頭下。依賴于當讀寫頭到達目标扇區時盤面的位置和磁盤旋轉速度。
定位到期望的磁道後，驅動器等待目标扇區的第一個位旋轉到讀/寫頭下。
最大旋轉時間 = 1/最大旋轉數率
平均旋轉時間 = (1/2) * 最大旋轉時間。
c.傳送時間：當目标扇區的第一個位位于讀寫頭下時，驅動器就可以開始讀或者寫該扇區的内容。依賴于旋轉速度和每條磁道的扇區數目。
平均傳送時間 = (1/最大旋轉數率) * （1/每磁道的平均扇區數）
五、邏輯磁盤塊
記憶體可以看成位元組數組、磁盤可以看成塊數組
- 現代磁盤構造複雜，有多個盤面，這些盤面上有不同的記憶區。為了對作業系統隐藏這樣的複雜性，現代磁盤将他們的構造呈現為一個簡單的試圖，一個B個扇區大小的邏輯塊的序列，編号為0，1，...，B-1。
- 磁盤中有一個小的硬體/固件裝置，稱為磁盤控制器，維護着邏輯塊号和實際（實體）扇區之間的映射關系。
- 控制器上的固件執行一個快速表查找，将一個邏輯塊号翻譯一個（盤面、磁道、扇區）的三元組，這個三原則唯一地表示了對應的實體扇區。控制器上的硬體解釋這個三元組，将讀寫頭移動到适當的煮面，等待扇區移動到讀寫頭下，将讀寫頭感覺到的位放在控制器上的一個小緩沖區中，然後将他們拷貝到主存中。
六、連接配接到I/O裝置
圖形卡、螢幕、滑鼠、鍵盤和磁盤這樣的輸入輸出裝置，都是通過I/O總線連接配接到CPU和主存的。
系統總線和存儲器總線是與CPU相關的，I/O總線設計成與底層CPU無關。
I/O總線比系統總線比存儲器總線慢，但是它可以容納種類繁多的第三方I/O裝置。
- 三個裝置連接配接到總線：
通用串行總線USB：2.0最大帶寬60MB/S，3.0最大帶寬600MB/S
圖形卡（擴充卡）
主機總線擴充卡
七、通路磁盤
CPU使用一種存儲器映射I/O技術來向I/O裝置發出指令，在使用存儲器映射I/O的系統中，位址空間中有一塊位址是為與I/O裝置通信保留的，稱為I/O端口。當一個裝置連接配接到總線時，它與一個或多個端口相連。
直接存儲器通路：裝置可以自己執行讀或者寫總線事務，而不需要CPU幹涉的過程。這種資料傳送稱為DMA傳送。
八、固體磁盤：基于閃存的存儲技術
一個SSD包由一個或多個閃存晶片和閃存翻譯層組成，閃存晶片替代傳統旋轉磁盤中機械驅動器；閃存翻譯層（一個硬體/固件裝置）替代磁盤控制器，将對邏輯塊的請求翻譯成對底層實體裝置的通路。
1.性能特性
順序讀和寫（CPU按順序通路邏輯磁盤塊）性能相當，順序讀比順序寫稍快一點。
随機順序通路邏輯塊時，寫比讀慢一個數量級。
讀寫性能差别是由底層閃存基本屬性決定的。
2.優點
由半導體構成，沒有移動的部件
随機通路時間比旋轉磁盤要快、能耗低、結實
3.缺點：易磨損、更貴
第二節 局部性
一、局部性原理：一個編寫良好的計算機程式常常具有良好的局部性，即傾向于引用臨近于其他最近引用過的資料項的資料項，或者最近引用過的資料項本身。
(1)兩種形式：空間局部性和時間局部性
(2)有良好局部性的程式比局部性差的程式運作得更快
硬體層：局部性原理允許計算機設計者通過引入高速緩存存儲器來儲存最近被引用的指令和資料項，進而提高對主存的通路速度。
作業系統級：局部性原理允許系統使用主存作為虛拟位址空間最近被引用塊的高速緩存，用主存來緩存磁盤檔案系統中最近被使用的磁盤塊。
應用程式中：例如，Web浏覽器将最近被引用的文檔放在本地磁盤上。
二、對程式資料引用的影響
1.步長為k的引用模式
定義：一個連續變量中，每隔k個元素進行通路。
步長為1的引用模式：就是順序通路一個向量的每個元素，有時也被稱為順序引用模式，是程式中空間局部性常見和重要的來源。
一般來說，随着步長增加，空間局部性下降。
2.多元數組程式
C語言中數組在存儲器中是按照行順序存放的，是以按照行優先順序執行的代碼的局部性要好于按列優先順序的代碼。
三、取指令的局部性
程式指令是存放在存儲器中的，CPU必須取出（讀出）這些指令。
代碼差別于程式資料的一個重要屬性是在運作時它是不能被修改的。當程式正在執行時，CPU隻從存儲器中讀出它的指令，CPU絕不會重寫或修改這些指令。
四、量化評價一個程式中局部性的簡單原則
重複引用同一個變量的程式有良好的時間局部性
對于具有步長為k的引用模式的程式，步長越小，空間局部性越好
對于取指令來說，循環有好的時間和空間局部性。循環體越小，循環疊代次數越多，局部性越好。
第三節 存儲器層次結構
一、存儲技術和計算機軟體
存儲技術：不同的存儲技術的通路時間差異很大，速度較快的技術每位元組的成本要比速度較慢的技術高，而且容量較小，CPU和主存之間的速度差距在增大。
計算機軟體：一個編寫良好的程式傾向于展示出良好的局部性。
高層往底層走，儲存設備變的更慢、更便宜、更大。每一層儲存設備都是下一層的緩存。
二、緩存
高速緩存與緩存：高速緩存cash是一個小而快速的儲存設備，它作為存儲在更大、更慢的裝置中的資料對象的緩沖區域。使用高速緩存的過程稱為緩存。
存儲器層次結構的中心思想：對于每個k，位于k層的更快更小的儲存設備作為位于k+1層的更大更慢的儲存設備的緩存。即每層儲存設備都是下一層的“緩存”
資料總是以塊大小為傳送單元在第k層與第k+1層之間來回拷貝。任一對相鄰的層次之間塊大小是固定的，但是其他的層次對之間可以有不同的塊大小。
1.緩存命中
當程式需要第k+1層的某個資料對象d時，首先在目前存儲在第k層的一個塊中查找d，如果d剛好緩存在第k層中，就稱為緩存命中。
該程式直接從第k層讀取d，比從第k+1層中讀取d更快。
2.緩存不命中
即第k層中沒有緩存資料對象d。
這時第k層緩存會從第k+1層緩存中取出包含d的那個塊。如果第k層緩存已滿，就可能會覆寫現存的一個塊.覆寫一個現存的塊的過程稱為替換/驅逐這個塊；被驅逐的塊有時也稱為犧牲塊。
替換政策：決定替換哪個塊
- 随機替換政策：随機選擇一個犧牲塊
- 最近最少被使用替換政策（LRU）：選擇最後被通路的時間距現在最遠的塊
種類：
強制性不命中/冷不命中：即第k層的緩存是空的（稱為冷緩存），對任何資料對象的通路都不會命中。通常是短暫事件，不會在反複通路存儲器使得緩存暖身之後的穩定狀态中出現。
沖突不命中：由于一個放置政策：将第k+1層的某個塊限制放置在第k層塊的一個小的子集中，這就會導緻緩存沒有滿，但是那個對應的塊滿了，就會不命中。
容量不命中：當工作集的大小超過緩存的大小時，緩存會經曆容量不命中，就是說緩存太小了，不能處理這個工作集。
三、緩存管理：某種形式的邏輯必須管理緩存，而管理緩存的邏輯可以是硬體、軟體，或者兩者的集合。
第四節 高速緩存存儲器
一、簡介
1.早期的計算機系統的存儲器層次結構：CPU寄存器、DRAM主存儲器和磁盤存儲
2.CPU與主存之間插入
L1高速緩存：位于CPU寄存器檔案和主存之間，通路速度2-4個時鐘周期
L2高速緩存：位于L1高速緩存和主存之間，通路速度10個時鐘周期
L3高速緩存：位于L2高速緩存和主存之間，通路速度30或40個時鐘周期
3.高速緩存存儲器的典型總線結構
二、通用的高速緩存存儲器結構
高速緩存是一個高速緩存組的數組，高速緩存的結構将m個位址劃分成了t個标記位，s個組索引位和b個塊偏移位。它的結構可以用元組（S,E,B,m）來描述
| m | 每個存儲器位址有m位，形成M=2^m個不同的位址 |
| S | 這個數組中有S=2^s個高速緩存組 |
| E | 每個組包含E個高速緩存行 |
| B | 每個行是由一個B=2^b位元組的資料塊組成的 |
| 标記位 | t=m-(b+s)個，唯一的辨別存儲在這個高速緩存行中的塊 |
| 有效位 | 每個行有一個有效位，指明這個行是否包含有意義的資訊 |
| 高速緩存的大小/容量C | C=S*E*B。指所有塊的大小的和，不包括标記位和有效位。 |
三、直接映射高速緩存
1.根據E（每個組的高速緩存行數）劃分高速緩存為不同的類，E=1的稱為直接映射高速緩存。
高速緩存确定一個請求是否命中，然後取出被請求的字的過程，分為三步： 組選擇、行比對、字抽取
組選擇
高速緩存從w的位址中間抽取出s個組索引位
組索引位：一個對應于一個組号的無符号整數。
行比對
判斷緩存命中的兩個充分必要條件：
該行設定了有效位
高速緩存行中的标記和w的位址中的标記相比對
字選擇
确定所需要的字在塊中是從哪裡開始的。
2.緩存不命中時的行替換：用新取出的行替換目前的行。
3.後運作中的直接映射高速緩存
标記位和索引位連起來唯一的辨別了存儲器中的每個塊。
因為有8個存儲塊，4個高速緩存組，多個塊映射到同一個高速緩存組（因為他們有相同的組索引）。
映射到同一個高速緩存組的塊由标記位唯一地辨別。
4.CPU執行一系列讀的步驟：
用索引位，确定針對的是哪個組
然後看對應的組是否有效：
如果無效則緩存不命中，高速緩存從存儲器或低一層中取出要找的塊，存儲在對應的組中，再把有效位置1，傳回需要的值
如果有效，再根據标記找是否有比對的标記：如果有，則緩存命中，傳回需要的值；如果沒有，則替換行，傳回。
5.直接映射高速緩存中的沖突不命中
原因：在塊之間抖動，即這些塊被映射到了同一個高速緩存組。
解決方法：在每個數組的結尾放B位元組的填充（B位元組是一個塊的長度，一行是一個塊，相當于分開了行）進而使得他們映射到不同的組。
四、組相連高速緩存
1.組選擇：與直接映射高速緩存中的組選擇一樣，組索引位辨別組。
2.行比對和字選擇
把每個組看做一個小的相關聯存儲器，是一個（key，value）對的數組，以key為輸入，傳回對應數組中的value值。高速緩存必須搜尋組中的每一行，尋找有效的行其标記與位址中的相比對。
形式是(key, value)，用key作為标記和有效位去比對，比對上了之後傳回value。
組中的任意一行都可以包含任何映射到這個組的存儲器塊，是以告訴緩存必須搜尋組中的每一行。
3.組相連高速緩存中不命中時的行替換：随機替換
最不常使用政策LFU：替換在過去某個時間視窗内引用次數最少的那一行。
最近最少使用政策LRU：替換最後一次通路時間最久遠的那一行。
五、全相連高速緩存
1.組選擇：隻有一個組，沒有組索引位。
2.行比對和字選擇：與組相連高速緩存是一樣的，但規模大很多，是以隻适合做小的高速緩存，例如虛拟存儲系統中的翻譯備用緩沖器。
六、寫
1.寫命中時，更新低一層中的拷貝的方法
直寫：立即将w的高速緩存塊協會到緊接着的低一層中
缺點：每次寫都會引起總線流量。
寫回：隻有當替換算法要驅逐更新過的塊時，才寫到緊接着的低一層中。
優點：符合局部性原理，顯著的減少總線流量
缺點：增加了複雜性，必須為每個高速緩存行維護一個額外的修改位
2.寫不命中的處理方法
寫配置設定（對應寫回）：加載相應的低一層中的塊到高速緩存中，然後更新這個高速緩存塊。
非寫配置設定（對應直寫）：避開高速緩存，直接把這個字寫在低一層中。
七、高速緩存參數的性能影響
1.性能
不命中率 = 不命中數量/引用數量
命中率 = 1 - 不命中率
命中時間：從高速緩存傳送一個字到CPU所需的時間，包括組選擇，行比對，字抽取的時間。
不命中處罰：因為不命中所需要的額外的時間
2.具體影響
高速緩存大小：較大的高速緩存可能會提高命中率，但使大存儲器運作的更快是更難一些的。
塊大小：較大的塊能利用程式中可能存在的空間局部性，幫助提高命中率；但塊越大意味着高速緩存行較少，損害時間局部性。
相聯度：相聯度較大（E值較大）優點是降低了高速緩存由于沖突不命中出現抖動的可能性，但成本較高。
寫政策：直寫高速緩存易實作，而且能使用獨立于高速緩存的寫緩沖區，用來更新存儲器，不命中開銷小。寫回高速緩存引起的傳送比較少，允許更多的到存儲器的寬帶用于執行DMA的I/O裝置。越下層，越可能用寫回而不是直寫。
第五節 編寫高速緩存友好的代碼
1.確定代碼高速緩存友好的基本方法：
讓最常見的情況運作的快。
在每個循環内部緩存不命中數量最小。
兩種局限性：空間、時間
1.對局部變量的反複引用是好的，因為編譯器能夠将他們緩存在寄存器檔案中
2.步長為1的引用模式是好的，因為存儲器層次結構中所有層次上的緩存都是将資料存儲為連續的塊
參考資料：1.《深入了解計算機系統》第六章
2.實驗樓課程-深入了解計算機系統 實驗七
好文要頂 關注我 收藏該文聯系我
