第六章存儲器層次結構
1、存儲器系統是一個具有不同容量、成本和通路時間的儲存設備的層次結構。
2、高速緩存存儲器：作為CPU和主存之間的緩存區域
3、具有良好局部性的程式傾向于一次又一次的通路相同的資料項集合，或是傾向于通路鄰近的資料項集合。具有良好局部性的程式比局部性差的程式更多的傾向于從存儲器層次結構中較高層次處通路資料項，是以運作的更快。
6.1 存儲技術
6.1.1 随機通路存儲器
一、随機通路存儲器(RAM)分為兩類：
靜态RAM（SRAM）：更快，更貴，用來作為高速緩存存儲器，既可以在CPU晶片上，也可以在片下。
動态ARM（DARM）：用來作為主存以及圖形系統的幀緩沖區。
二、靜态RAM:SRAM将每個位存儲在一個雙穩态的存儲器單元裡。
動态RAM：DRAM将每個位存儲為對一個電容的充電。
三、SRAM和DRAM存儲器的特性：隻要有供電，SRAM就會保持不變，與DRAM不同，它不需要重新整理。SRAM的存取比DRAM快，，SRAM對幹擾不敏感。代價是SRAM單元比DRAM單元使用更多的半導體，而且更貴，功耗更大。
四、傳統的DRAM
晶片中的單元位被分為d個超單元，每個超單元有w個DRAM單元組成，一個dxw的DRAM總共存儲了dw位資訊。超單元被組織成一個r行c列的長方形，即rc=d。每個超單元有形如(i, j)的位址，i表示行，j表示列。
五、存儲器子產品
DRAM晶片包裝在存儲器子產品中，是插在主機闆的擴充槽上的。168個引腳的雙列直插存儲器子產品以64位為塊傳送或傳出資料。72個引腳的單列直插存儲器子產品以32位為塊傳送資料。
六、增強的DRAM
有許多種DRAM存儲器，每種都是基于DRAM單元。
1、快頁模式-FPM DRAM
2、擴充資料輸出-EDO DRAM
3、同步-SDRAM
4、雙倍資料速率同步-DDR SDRAM
5、RDRAM
6、視訊-VRAM
七、非易失性存儲器ROM
1、RAM在斷電後會丢失資訊，ROM即使斷電也能儲存着資訊。ROM中有的類型既可以讀又可以寫，但整體上稱為隻讀存儲器。
2、ROM是以它們能夠被重程式設計的次數和進行重程式設計所用機制進行區分的：
3、PROM：可程式設計ROM，隻能被程式設計一次。
4、EPROM:可擦寫可程式設計ROM，能夠被擦寫和重程式設計的次數的數量級達到1000次。
5、EEPROM：電子可擦除PROM，不需要實體上獨立的程式設計裝置，可直接在印刷電路卡上程式設計。數量級達到10^5。
6、FLASH：閃存，基于EEPROM，為大量的電子裝置提供快速而持久的非易失性存儲
八、存儲在ROM裝置中的程式通常稱為固件，一個計算機系統通電後，會運作固件，一些系統在固件中提供了少量基本的輸入和輸出函數，如PC和BIOS。複雜的裝置也依賴固件翻譯來自CPU的I/O輸入輸出請求。
九、通路主存
總線是一組并行的導線，能攜帶位址、資料和控制信号。資料流通過總線在處理器和DRAM主存之間來回。每次CPU和主存之間的資料傳送是通過一系列步驟來完成的，稱為總線事務。
讀事務：從主存傳送資料到CPU
寫事務：從CPU傳送資料到主存
十、計算機系統的配置：主要部件是CPU晶片、I/O橋晶片組、組成主存的DRAM存儲器子產品。這些部件由一對總線連接配接起來，其中一條總線是系統總線，它連接配接CPU和I/O橋，另一條總線是存儲器總線，它連接配接I/O橋和主存。
I/O橋将系統總線的電子信号翻譯成存儲器總線的電子信号。
6.1.2 磁盤存儲
一、磁盤構造
磁盤有許多盤片構成，每個盤片有兩個表面，表面上覆寫着磁性記錄材料。盤片中央有一個可旋轉的主軸，盤片以固定旋轉速率旋轉。
每個表面由一組稱為磁道的同心圓組成。磁道被劃分為一組扇區，每個扇區包含相等數量的資料位。扇區之間由間隙分隔開，間隙不存儲資料。
磁盤由一個或多個疊放的盤片組成，被封裝在一個密封的包裝裡，整個裝置稱為磁盤驅動器，即磁盤，也稱旋轉磁盤，差別與基于閃存的固态磁盤SSD。柱面：描述多個盤片驅動器的構造，指所有盤片表面上到主軸中心的距離想等的磁道的組合。
二、磁盤容量
一個磁盤上可以記錄的最大位數稱為最大容量，即容量。由以下技術因素決定：
記錄密度：磁道一英寸的段中可以放入的位數
磁道密度：從盤片中心出發半徑上一英寸的段内可以有的磁道數
面密度：記錄密度與磁道密度的乘積
提高面密度即可提高容量。
三、計算磁盤容量的公式：
磁盤容量 = 位元組數/扇區 X 平均磁盤數/磁道 X 磁道數/表面 X 表面數/盤片 X 盤片數/磁盤
四、磁盤操作
磁盤用讀/寫頭來讀寫存儲在磁性表面的位，讀寫頭連接配接到傳動臂，通過沿着半徑軸前後移動傳動臂可以将讀/寫定位在盤面上的任何磁道上。這樣的機械運動稱為尋道。定位到了期望的磁道上，磁道旋轉每個位通過它的下面時就可讀寫該位。多個盤片針對每一個都有獨立的讀寫頭，且位于同一柱面上。
對扇區的通路時間有三個主要部分：
尋道時間：定位到包含目标扇區的磁道上，移動傳動臂所需時間。依賴于讀寫頭以前的位置和傳動臂移動速度。通常為3-9ms，最大可達20ms。
旋轉時間：目标扇區的第一個位旋轉到讀寫頭下，時間依賴于讀寫頭到目标磁道的位置和磁盤的旋轉速度。
最大旋轉延遲=1/RPM X 60secs/1min (s)
平均旋轉時間是最大值的一半。
傳送時間：讀寫該扇區的内容，時間依賴于旋轉速度和每條磁道的扇區數目（扇區大小）。平均傳送時間= 1/RPM x 1/(平均扇區數/磁道) x 60s/1min
通路一個磁盤扇區内容的平均時間為平均尋道時間，平均旋轉延遲和平均傳送時間之和。
五、邏輯磁盤塊
磁盤中有一個小的硬體/固件裝置，稱為磁盤控制器，維護這邏輯塊号和實際（實體）磁盤扇區之間的映射關系。
六、連接配接到I/O裝置
輸入輸出裝置都是通過I/O總線連接配接到CPU和主存的。與系統總線和存儲器總線不同，它可以設計成與CPU無關的。
I/O總線較慢，但可以容納種類繁多的第三方I/O裝置：
通用串行總線（USB）控制器是一個連接配接到USB總線的裝置的中轉機構。
圖形卡（或擴充卡）包含硬體和軟體邏輯，代表CPU在顯示器上畫像素。
主機總線擴充卡将一個或多個磁盤連接配接到I/O總線，使用特别的主機總線接口定義的通信協定。
兩個常用的磁盤接口SCSI/SATA，SCSI更快更貴，可支援多個磁盤驅動器。其他裝置，如網絡擴充卡，插入到主機闆上空的擴充槽，進而連接配接到I/O總線。
七、通路磁盤
CPU從磁盤讀資料，CPU使用存儲器映射I/O的技術向I/O裝置發出指令，過程中位址空間有一塊是為與I/O裝置通信保留的，稱為I/O端口。當裝置連接配接到總線時，它與一個或多個端口相關聯。
6.1.3 固體磁盤
一、固态硬碟是一種基于閃存的存儲技術，一個SSD包由一個或多個閃存晶片和閃存翻譯層組成，閃存晶片替代傳統旋轉磁盤中的機械驅動器，閃存翻譯層是一個硬體/固件裝置，與磁盤控制器相同，将對邏輯塊的請求翻譯成對底層實體裝置的通路。
二、SSD順序讀比順序寫稍微快一點，但随機寫比讀慢一個數量級。
三、SSD優點：随機通路時間比旋轉磁盤更快，能耗更低，更結實
SSD缺點：容易磨損，較貴，容量通常隻是旋轉磁盤的1%
6.1.4 存儲技術優勢
幾個重要思想：
不同的存儲技術有不同的價格和性能折中
不同存儲技術的價格和性能屬性以截然不同的速率變化着
增加密度進而降低成本比降低通路時間更容易
DRAM和磁盤的性能滞後于cpu的性能
6.2局部性
一、局部性原理：一個編寫良好的計算機程式，常常傾向于引用臨近于其他最近引用過的資料項的資料項，或者最近引用過的資料項本身。
二、兩種不同的形式：
時間局部性：被引用過一次的存儲器位置很可能在不遠的将來再被多次引用。
空間局部性：如果一個存儲器位置被引用了一次，那麼很可能在不遠的将來引用附近的一個存儲器位置。
6.2.1、對程式資料引用的局部性
步長為k的引用模式：一個連續變量中，每隔k個元素進行通路，就被稱為步長為k的引用模式。
步長為1的引用模式：就是順序通路一個向量的每個元素，有時也被稱為順序引用模式，它是程式中 空間局部性常見和重要的來源。一般來說，随着步長增加，空間局部性下降。
6.2.2、取指令的局部性
程式指令是存放在存儲器中的，CPU必須取出（讀出）這些指令。
代碼差別于程式資料的是在運作時是不能被修改的。
6.2.3、局部性小結
一個程式中局部性的簡單原則：
重複引用同一個變量的程式有良好的時間局部性
對于具有步長為k的引用模式的程式，步長越小，空間局部性越好
對于取指令來說，循環有好的時間和空間局部性。循環體越小，循環疊代次數越多，局部性越好。
6.3存儲器層次結構
用互相補充的性質想到的一種組織存儲器系統的方法：存儲器層次結構。一般而言，從高層往底層走，儲存設備變得更慢、更便宜和更大。
即：每層儲存設備都是下一層的“緩存”
6.3.1 存儲器層次結構中的緩存
一、高速緩存是一個小而快速的儲存設備，作為存儲在更大、也更慢的裝置中的資料對象的緩沖區域。使用高速緩存的過程稱為緩存。
二、存儲器層次結構的中心思想是：層次結構中的每一層都緩存來自較低一層的資料對象。
三、第k+1層的存儲器被劃分為連續的資料對象片，稱為塊。每個塊都有唯一的位址和名字。類似第k層也被劃分為較少的塊的集合，塊的大小與k+1層是一樣的，第k層的緩存包含第k+1層塊的一個子集的拷貝。
四、資料總是以塊大小為傳送單元在第k層與第k+1層之間來回拷貝。任一對相鄰的層次之間塊大小是固定的，但是其他的層次對之間可以有不同的塊大小。
五、緩存命中
當程式需要第k+1層的某個資料對象d時，首先在目前存儲在第k層的一個塊中查找d，如果d剛好緩存在第k層中，就稱為緩存命中。該程式直接從第k層讀取d，比從第k+1層中讀取d更快。
六、緩存不命中
即第k層中沒有緩存資料對象d。這時第k層緩存會從第k+1層緩存中取出包含d的那個塊。如果第k層緩存已滿，就可能會覆寫現存的一個塊。
決定該替換哪個塊又緩存的替換政策控制，如随機替換政策，最近最少被使用LRU替換政策。
七、緩存不命中的種類
1、強制性不命中/冷不命中
第k層的緩存為空（稱為冷緩存），任何通路都會不命中。這種通常是短暫的事件
2、沖突不命中
放置政策為将第k+1層的塊限制放置在第k層塊的一個小的子集中。
3、容量不命中
當工作集的大小超過緩存的大小時，緩存會經曆容量不命中，就是說緩存太小了，不能處理這個工作集。
八、緩存管理
存儲器層次結構的本質是每一層儲存設備都是較低一層的緩存。在每一層上，某種形式的邏輯必須管理緩存，而管理緩存的邏輯可以是硬體、軟體，或者兩者的結合。
6.3.2存儲器層次結構概念小結
基于緩存的存儲器層次結構行之有效，因為較慢的儲存設備更便宜。
利用時間局部性
利用空間局部性
6.4 高速緩存存儲器
CPU和主存之間差距太大，插入一個小的SRAM高速緩存存儲器，稱為L1高速緩存：2-4個時鐘周期。L2高速緩存：10個時鐘周期。L3高速緩存：30~40個時鐘周期
6.4.1通用的高速緩存存儲器結構
高速緩存的結構可以用元組（S,E,B,m）來描述：
S：這個數組中有S=2^s個高速緩存組
E：每個組包含E個高速緩存行
B：每個行是由一個B=2^b位元組的資料塊組成的
m：每個存儲器位址有m位，形成M=2^m個不同的位址
有效位：每個行有一個有效位，指明這個行是否包含有意義的資訊
标記位：t=m-(b+s)個，唯一的辨別存儲在這個高速緩存行中的塊
組索引位：s
塊偏移位：b
高速緩存的結構将m個位址劃分成了t個标記位，s個組索引位和b個塊偏移位。
高速緩存的大小/容量C指所有塊的大小的和，不包括标記位和有效位，是以：
C=S*E*B
6.4.2直接映射高速緩存
一、每個組隻有一行的高速緩存稱為直接映射高速緩存。
二、高速緩存确定一個請求是否命中，然後抽取出被請求的字的過程：1、組選擇2、行比對3、字抽取
三、直接映射高速緩存中的組選擇
從位址中抽取s個組索引位，解釋成一個對應于一個組号的無符号整數，選擇相應組。
四、直接映射高速緩存中的行比對
直接映射高速緩存每個組隻有一行，當設定了有效位并且行中的标記與位址中的标記相比對時，我們得到緩存命中。
五、直接映射高速緩存中的字選擇
塊偏移位b提供了所需要的字的第一個位元組的偏移。
六、直接映射高速緩存中不命中時的行替換
緩存不命中時，需要從下一層取出被請求的塊存儲在組索引位訓示的組中的高速緩存行中。若組中都是有效行時。需要替換，直接映射高速緩存每組隻有一行，就可直接替換。
七、綜合：運作中的直接映射高速緩存
八、直接映射高速緩存中的沖突不命中
當程式通路大小為2的幂的數組時，直接映射高速緩存中通常會發生沖突不命中。
6.4.3 組相聯高速緩存
一、一個 1<E<C/B 的高速緩存通常稱為E路組相聯高速緩存。
二、組相聯高速緩存中的組選擇
與直接映射高速緩存的組選擇一樣，組索引位辨別組
三、組相聯高速緩存中的行比對和字選擇
形式是(key, value)，用key作為标記和有效位去比對，比對上了之後傳回value。
重要思想：組中的任意一行都可以包含任何映射到這個組的存儲器塊，是以告訴緩存必須搜尋組中的每一行。
判斷比對的标準依舊是兩個充分必要條件：
1.有效
2.标記比對
四、組相聯高速緩存中不命中時的行替換
緩存不命中時，高速緩存從存儲器中取出包含這個字的塊，替換行時，如果沒有空行，按照替換政策替換。複雜的替換政策利用了局部性原理，以使在比較近的将來引用被替換的行的幾率最小。
6.4.4 全相聯高速緩存（E=C/B）
一個全相聯高速緩存由一個包含所有高速緩存行的組（即E=C/B）組成的。
1、全相聯高速緩存中的組選擇
隻有一個組，位址中沒有組索引位，位址隻被劃分成了一個标記和一個塊偏移。
2、全相聯高速緩存中的行比對和字選擇
與前面的一樣，差別主要是規模大小的問題
全相聯高速緩存隻适合做小的高速緩存，例如虛拟存儲器系統中的翻譯備用緩存器TLB。
6.4.5 有關寫的問題
一、更新低一層中的拷貝的方法：
（1）直寫：立即将w的高速緩存塊協會到緊接着的低一層中
缺點是每次寫都會引起總線流量。
（2）寫回：隻有當替換算法要驅逐更新過的塊時，才寫到緊接着的低一層中
優點：由于局部性，寫回能顯著的減少總線流量
缺點：增加了複雜性，必須為每個高速緩存行維護一個額外的修改位
二、寫不命中的處理方法
（1）寫配置設定：加載相應的低一層中的塊到高速緩存中，然後更新這個高速緩存塊。
（2）非寫配置設定：避開高速緩存，直接把這個字寫在低一層中。
6.4.6 真實的高速緩存層次結構：
既儲存指令又包括資料的高速緩存稱為統一的高速緩存。
6.4.7 高速緩存參數的性能影響
一、有許多名額來衡量高速緩存的性能：
不命中率
命中率
命中時間
不命中處罰
二、影響：
1、高速緩存大小的影響
2、塊大小的影響
3、相聯度的影響
4、寫政策的影響
參考資料
《深入了解計算機系統》
體會
認真看書，學習這一章的内容，使得我對存儲器層次結構有了進一步的了解。但是在做練習題的時候不是很順利，還是要進行翻書看例子，對知識的掌握不夠紮實。今後得要更加仔細閱讀課本。