資訊安全系統設計基礎第七周學習總結

第七周（10.19-10.25）:

學習計時：共12小時

讀書：4

代碼：1

作業：3

部落格：4

第6章 存儲器層次結構

• 實際上，存儲器系統是一個具有不同容量、成本和通路時間的儲存設備的層次結構。cPU寄存器儲存着最常用的資料。靠近CPU的小的、快速的高速緩存存儲器作為一部分存儲在相對慢速的主存儲器中資料和指令的緩沖區域。主存暫時存放存儲在容量較大的、慢速磁盤上的資料，而這些磁盤常常又作為存儲在通過網絡連接配接的其他機器的磁盤或錄音帶上的資料的緩沖區域。
• 如果你的程式需要的資料是存儲在CPU寄存器中的，那麼在執行期間，在零個周期内就能通路到它們。如果存儲在高速緩沖中，需要1～30個周期。如果存儲在主存中，需要50～200個周期。如果存儲在磁盤上，需要約幾千萬個周期。

6.1 存儲技術

6.1.1随機通路存儲器

随機通路存儲器（RAM，Random-access memory）分為兩類－靜态和動态的。靜态RAM（SRAM）比動态RAM（DRAM）更快，但也貴很多。SRAM用來作為高速緩存存儲器，即可以在CPU晶片上，也可以不在CPU晶片上。DRAM用來作為主存以及圖形系統的幀緩沖區。

• 靜态RAM

  （1）SRAM将每個位存儲在一個雙穩态（bistable）存儲器單元（cell）中。每個單元是用一個六半導體電路來實作的。這個電路的一個屬性是：它可以無限制地保持在兩個不同的電壓配置（configuration）或狀态（state）之一。其他任何狀态都是不穩定的。

  （2）由于SRAM的雙穩态特性，隻要有電，它就會永遠地保持它的值，即使有幹擾，如電子噪音，當幹擾消除，電路也能恢複到穩定值。

• 動态RAM

  （1）DRAM将每個位存儲為對電容的充電。電容約為30×10-15F。

  （2）洩露電流的各種因素會導緻DRAM單元在10~100毫秒内失去電荷。計算機運作的時鐘周期是以納秒來衡量的。

• 傳統的DRAM

  計算機界，傾向于把DRAM的陣列單元稱為單元（cell），電路設計者傾向于稱之為字（word）。這裡稱為supercell。

• 存儲器子產品

  常見的包裝包括168個管腳的雙列直插存儲器子產品（Dual Inline Memory Module,DIMM），它以64位為塊傳送資料到存儲控制器和從存儲控制器傳出資料；72個管腳的單列直插存儲器子產品（Single Inline Memory Module,SIMM），它以32位為塊傳送資料。

• 增強的DRAM

  （1）同步DRAM：SDRAM用與驅動存儲器相同的外部時鐘信号的上升沿來代替許多這樣的控制信号。

  （2）雙倍資料數率同步DRAM：DDR SDARM是對SDRAM的一種增加，它通過使用時鐘的兩個邊沿作為控制信号，進而使DRAM的速度翻倍。

• 非易失性存儲器

  （1）EEPROM，電子可擦除PROM：類似于DPROM，但是它不需要一個實體上獨立的程式設計裝置，是以可以直接在印制電路卡上程式設計。EEPROM能夠程式設計的次數量級可達10e5次。

  （2）閃存是一個類小的非易失性存儲器，基于EEPROM，支援插撥。

  （3）存儲在ROM裝置中的程式通常稱為固件。

• 通路主存

  （1）讀事務（read transaction）從主存傳送資料到CPU；寫事務（write transcation）從CPU傳送資料到主存。

  （2）總線是一組并行的導線，能攜帶位址，資料，的控制信号。

6.1.2磁盤存儲

• 磁盤制造

  每個表面是由一組稱為磁道（track）的同心圓組成；每個磁道被劃分成一組扇區（sector）；每個扇區包含相等數量的資料位（通常是512位元組）；這些資料編碼在扇區上的磁性材料中。扇區之間由一些間隙（gap）分隔開，這些間隙中不存在資料位。間隙存儲用來辨別扇區的格式化位。

• 磁盤容量

  磁盤容量是由以下技術因素決定的：

記錄密度

磁道密度

面密度

旁注：對于與DRAM和SRAM容量相關的機關，通常K ＝ 210，M ＝ 220，G ＝ 230，對于磁盤和網絡這樣的I/O裝置容量相關的機關，通常K ＝ 103，M ＝ 106，G ＝ 109。

• 磁盤操作

（1）任何時刻，所有的讀寫頭都位于同一柱面上。

（2）在傳動臂末端的讀/寫頭在磁盤表面高度約0.1微米處一層薄薄的氣墊上飛翔，速度大約為80km/h。磁盤以扇區大小的塊來讀寫資料。

（3）對扇區的通路時間有三個主要部分組成：

1.尋道時間（seek time):為了讀取某個目标扇區的内容，傳動臂把讀/寫頭首先定位到包含目标扇區的磁道上。所需時間即為尋道時間，約等于最大旋轉時間。

2.旋轉時間（rotational latency):定位到期望的磁道後，驅動器等待目标扇區的第一個位旋轉到讀/寫頭下。

Tmax rotation = 1/最大旋轉數率

Tavg rotation = (1/2) × Tmax rotation

3.傳送時間（transfer time）:Tavg transfer = (1/最大旋轉數率) × （1/每磁道的平均扇區數）

• 邏輯磁盤塊

  現代磁盤構造複雜，有多個盤面，這些盤面上有不同的記錄區。為了對作業系統隐藏這樣的複雜性，現代磁盤将它們的構造簡化為一個b個扇區大小的邏輯塊的序列，編号為0,1,2,...b-1。磁盤中有一個小的硬體/固件裝置，稱為磁盤控制器，維護着邏輯塊号的和實際（實體）磁盤扇區之間的映射關系。

• 連接配接到I/O裝置
• 通路磁盤
• 商用磁盤的剖析

6.1.3固态硬碟

固态硬碟是一種基于閃存的存儲技術，在某些情況下是傳統旋轉磁盤的極有吸引力的替代産品。

6.1.4存儲技術趨勢

• 從我們對存儲技術的讨論中，可以總結出幾個很重要的思想。
• 不同的存儲技術有不同的價格和性能折中。SRAM比DRAM快一點，而DRAM比磁盤要快很多。另一方面，快速存儲總是比慢速存儲要貴的。SRAM每位元組的造價比DRAM高，DRAM的造價又比磁盤高得多。SSD位于DRAM和旋轉磁盤之間。
• 不同存儲技術的價格和性能屬性以截然不同的速率變化着。

6.2 局部性

局部性有兩種形式：時間局部性（temporal locality）和空間局部性（spatial locality）。在一個具有良好時間局部性的程式中，被引用過一次的存儲器位置很可能在不遠的将來再被多次引用；在一個具有良好空間局部性的程式中，如果一個存儲器位置被引用了一次，那麼程式很可能在不遠的将來引用附近的一個存儲器位置。

6.2.1對程式資料引用的局部性

根據書上例子進行了解：

• 一維數組

  對于sum來說，有很好的時間局部性，因為sum是标量，對于sum來說，沒有空間局部性；對于變量v，有很好的控件局部性，但是因為每個向量元素隻被通路一次，是以時間局部性很差。是以，總體來說，sumvec函數有很好的局部性。

• 二維數組

  局部性好：

  

局部性不好：

6.2.2取指令的局部性

因為程式指令是存放在存儲器中的，CPU必須取出這些指令，是以我們也能評價一個程式關于取指令的局部性。例如，上述一維數組示例中，for循環中的指令是按照連續的存儲器順序執行的，是以循環有良好的空間局部性。因為循環體會被執行多次，是以也有很好的時間局部性。

6.2.3局部性小結

一些量化評價一個程式中局部性的簡單原則：

1.重複引用同一個變量的程式有良好的時間局部性。

2.對于具有步長為k的引用模式的程式，步長越小，空間局部性越好；在存儲器中以大步長跳來跳去的程式空間局部性會很差。

3.對于取指令來說，循環有很好的時間和空間局部性。循環體越小，循環疊代次數越多，局部性越好。

6.3 存儲器層次結構

存儲器層次結構示例如下圖所示：

6.3.1存儲器層次結構中的緩存

存儲器層次結構的中心思想是，對于每個k，位于k層的更快更小的儲存設備作為位于k+1層的更大更慢的儲存設備的緩存。資料總是以塊大小作為傳送單元在第k層和k+1層之間來回拷貝的。

• 緩存命中
• 緩存不命中
• 緩存不命中的種類
• 緩存管理

6.3.2存儲器層次結構概念小結

概括來說，基于緩存的存儲器層次結構行之有效，是因為較慢的儲存設備比較快的儲存設備更便宜，還因為程式往往展示局部性：

• 利用時間局部性：由于時間局部性，同資料對象可能會被多次使用，一旦一個資料對象在第一次不命中時被拷貝到緩存中，我們就會期望後面該目标有一系列的通路命中。因為緩存比低層的儲存設備更快，對後面的命中的服務會比最開始的不命中快很多。
• 利用空間局部性：塊通常包含有多個資料對象。由于空間局部性，我們會期望後面對話中其他對家的通路能夠補償不命中後拷貝該塊的花費。

6.4 高速緩沖存儲器

6.4.1通用的高速緩存存儲器結構

6.4.2直接映射高速緩存

每個組隻有一行（E ＝ 1）的高速緩存被稱為直接映射高速緩存（direct-mapped cache）。

高速緩存确定一個請求是否命中，然後抽取出被請求的字的過程，分為三步

組選擇

行比對

字抽取

• 直接映射高速緩存中的組選擇

  如果把高速緩存看作一個關于組的一維數組，那麼這些組索引就是一個到這個數組的索引。如果我們把塊看作一個位元組的數組，而位元組偏移是這個數組的一個索引。

1. 直接映射高速緩存中的行比對

   當且僅當設定了有效位，而且告訴緩存行中的标記與w的位址中标記相比對時，這一行中包含w的一個拷貝。（有效位+标記）

2. 直接映射高速緩存中的字選擇

   塊偏移位提供了所需要的字的第一個位元組的偏移。

3. 直接映射高速緩存中不命中時的行替換
4. 綜合：運作中直接映射高速緩存
5. 直接映射高速緩存中的沖突不命中

6.4.3組相連高速緩存

• 1 < E < C/B
• 每個組都儲存有多于一個的高速緩存行。

6.4.4全相連高速緩存

• E = C/B
• 隻有一個組，這個組包含所有的高速緩存行。
• 因為全相聯高速緩存需要并行搜尋許多相比對的行，是以構造相對是困難的；是以隻适合做小的高速緩存；如虛拟存儲器系統中的TLB，它緩存頁表項。

6.4.5有關寫的問題

• 寫回，盡可能推遲存儲器更新，隻有當替換算法要驅逐已更新的塊時，才把它寫回存儲器。
• 處理不命中：寫配置設定（write-allocate），即加載相應的存儲器塊到高速緩存中，然後更新這個高速緩存器。

6.4.6一個真實的高速緩存層次結構的解剖

• 到目前為止，我們一直假設高速緩存隻儲存程式資料。不過實際上，也儲存指令。
• 隻儲存指令的高速緩存程式資料稱為i-cache。隻儲存程式資料的高速緩存稱為d-cache。既儲存指令又包括資料的高速緩存稱為統一的高速緩存。
• 現代處理器包括獨立的i-cahce和d-cache。這樣做有很多原因。有兩個獨立的高速緩存，處理器能夠同時讀一個指令字和一個資料字。i-caChe通常是隻讀的，是以比較簡單。通常會對不同的通路模式來優化這兩個高速緩存，它們可以有不同的塊大小、相聯度和容量。有不同的高速緩存也確定了資料通路不會與指令通路形成沖突不命中，反過來也是一樣，代價就是可能會引起容量不命中增加。

6.4.7高速緩存參數的性能影響

有許多名額來衡量高速緩存的性能：

• 不命中率：它是這樣計算的：不命中數量／引用數量
• 命中率：命中的存儲器引用比率
• 命中時間：命中時間的數量級是幾個時鐘周期
• 不命中處罰

6.5 編寫高速緩存友好的代碼

兩個關于編寫高速緩存友好的代碼的重要問題：

1.對局部變量的反複引用是好的，因為編譯器能夠将它們緩存在寄存器檔案中（時間局部性）。

2.步長為1的引用模式是好的，因為存儲器層次結構中所有層次上的緩存都是将資料存儲為連續的塊（空間局部性）。

6.6 綜合：高速緩存對程式性能的影響

6.6.1存儲器山

存儲器系統的性能不是一個數字就能描述的。相反，它是一座時間和空間局部性的山，這座山的上升高度差别可以超過一個數量級。要是程式運作在山峰而不是低谷。

6.6.2重新排列循環以提高空間局部性

一對nxn矩陣相乘問題：C=AxB。以下是矩陣乘法的六個版本：

6.6.3在程式中利用局部性

存儲系統被組織成一個儲存設備的層次結構，較小、較快的裝置靠近頂部，較大、較慢的裝置靠近底部。由于這種層次結構，程式通路存儲位置的有效速率不是一個數字能描述的。相反，它是個變化很大的程式局部性的函數（我們稱之為存儲器山），變化可以有幾個數量級，有良好局部性的程式從快速的高速緩存存儲器中通路它的大部分資料，局部性差的程式從相對慢速的DRAM主存中通路它的大部分資料。

了解存儲器層次結構本質的程式員能夠利用這些知識編寫出更有效的程式，無論具體的存儲系統結構是怎樣的。特别地，我們推薦下列技術：

• 将你的注意力集中在内循環上，大部分計算和存儲器通路都發生在這裡。
• 通過按照資料對象存儲在存儲器中的順序、以步長為1的來讀資料，進而使得你程式中的空間局部性最大。
• 一旦從存儲器中讀入了一個資料對象，就盡可能多地使用它，進而使得程式中的時間局部性最大。

6.7 小結

• 基本存儲技術包括随機存儲器（RAM）、非易失性存儲器（ROM）和磁盤。RAM有兩種基本類型。靜态RAM（SRAM）快一些，但是價格高，它即可以用做CPU晶片上的高速緩存，也可以用做晶片下的高速緩存。動态RAM（DRAM）慢一些，但價格低，用做主存和圖形幀緩沖區。非易失性存儲器，也稱為隻讀存儲器（ROM），即使是關電的時候，也能保持它們的資訊，它們用于存儲固件。旋轉磁盤是機械的非易失性儲存設備，以每個位很低的成本儲存大量的資料，但是通路時間比RAM更長。固态硬碟（SSD）基于非易失性的閃存，越來越變成旋轉磁盤對某些應用 的具有吸引力的替代産品。
• 一般而言，較快的存儲技術每個位的價格會更高，而且容量較小。這些技術的價格和性能屬性正在以顯著不同的速度變化着。特别地，DRAM和磁盤通路時間遠遠大于CPU周期時間。系統通過 将存儲組織馬儲存設備的層次結構來彌補這些差異，在這個層次結構中，較小、較快的裝置在頂部，較大、較慢的裝置在底部。因為編寫良好的程式有好的局部性，大多數資料都可以從較高層的服務，結果就是存儲系統能以較高層的速度運作，但卻有較底層的成本和容量。
• 程式員要以通過編寫有良好空間和時間局部性的程式來顯著地改程序式的運作時間。利用基于SRAM的高速緩存存儲器特别重要。主要從高速緩存取資料的程式性能比從存儲器取資料的程式運作得快得多。

重點

重點練習題：6.2，6.3，6.4，6.8，6.9，6.10，6.11，6.12, 6.13

• 6.1 節

  了解三種常見存儲技術：RAM/ROM/磁盤；

  RAM有SRAM和DRAM，特點和應用；

  ROM有PROM，EPROM，E2PROM，FLASH；

  磁盤是重點，涉及到後面的i/o和檔案系統，做好相關練習

  磁盤結構：盤片、磁道、扇區、間隙、柱面；磁盤驅動器

  通路時間：尋道、旋轉、傳送

  邏輯磁盤塊：這個很重要，記憶體可以看成位元組數組、磁盤可以看成塊數組

  總線

  資料總線、控制總線、位址總線

  系統總線、存儲總線、I/O總線：p395圖要了解

  讀寫事務：P389圖要能了解

• 6.2 節

  局部性原理：時間局部性、空間局部性，有能力者了解一下p429最後一段“存儲器山”

  資料引用局部性

  取指令局部性

• 6.3 節

  存儲層次結構：系統觀(1+1>2)（舉一反三：對稱不對稱加密形成的混合加密系統，混合動力汽車...）

  中心思想：每層儲存設備都是下一層的“緩存”

  對照p408的表了解

• 6.4節

  高速緩存結構（S，E，B，m）：高速緩存組、高速緩存行、塊

  映射

  命中

參考資料

1.教材：第六章《處理器體系結構》，詳細學習指導：http://group.cnblogs.com/topic/73069.html

2.課程資料：https://www.shiyanlou.com/courses/413 實驗六，課程邀請碼：W7FQKW4Y

3.教材中代碼運作、思考一下，讀代碼的學習方法：http://www.cnblogs.com/rocedu/p/4837092.html。

4.此學習筆記中的部分圖檔來自：http://blog.csdn.net/zhanghaodx082/article/details/12099161

感悟

1.存儲器的三個方面不能同時達到最優，他們存在着以下關系：存取時間越快，每一個“位”的價格越高；容量越大，每一個“位”的價格越低；容量越大，存取速度越慢。要解決這個問題，不依賴于單一的存儲元件或技術，而是使用存儲器的層次結構。

2.想找通俗易懂或者有很多執行個體的書來讀。

3.好好複習。