4 4Storage System V1210

1、,四、存儲系統(tǒng),譚志虎,本章主要內(nèi)容,存儲器概述 主存儲器 高速緩沖存儲器 虛擬存儲器 外存儲器,花樣繁多的存儲器,4.1 存儲器概述,存儲器分類 存儲器分級結(jié)構(gòu) 存儲器的性能指標,存儲器分類,按存儲介質(zhì)分 按存取方式分 按讀寫功能分 按信息的可保存性分 按在計算機系統(tǒng)中的作用分,按存儲介質(zhì)分,半導體存儲器 雙極型存儲器 MOS存儲器 速度快、功耗低 磁存儲器 磁芯、磁帶、磁盤 容量大，速度慢、體積大 激光存儲器 CD-ROM CD-RW CD-R DVD-ROM DVD-RW DVD-R 便于攜帶，廉價，易于保存,按存取方式分,隨機存儲器 存取時間與物理位置無關(guān) 磁芯、半導體存儲器 順序存儲

2、器 存取時間與物理位置有關(guān) 磁盤、磁帶、激光存儲器,按讀/寫功能分,只讀存儲器 (ROM) 存儲器內(nèi)容是預置的，固定的，無法改寫 讀/寫存儲器 既能讀出也能寫入的存儲器 隨機存儲器RAM,按信息的可保存性分,易失性存儲器 Volatile Memories 斷電后信息消失 SRAM DRAM 非易失性存儲器Non-Volatile Memories 斷電后仍能保存信息 磁存儲器、激光存儲器、NVRAM,按在計算機系統(tǒng)中的作用分,主存儲器 輔助存儲器 高速緩沖存儲器 Cache 控制存儲器,存儲系統(tǒng)主要技術(shù)指標,存儲時間 接受到讀寫命令到從存儲器中讀出或?qū)懭胄畔⑺?jīng)歷的時間 存儲周期 連續(xù)兩次訪

3、問存儲器所需要的最小時間間隔 存儲器帶寬 單位時間內(nèi)存儲器存取的信息量 Byte/s,存儲系統(tǒng)分層結(jié)構(gòu),存儲速度 訪問頻率 單位成本,存儲容量,外存/輔存,內(nèi)存,本章主要內(nèi)容,存儲器概述 主存儲器 高速緩沖存儲器 虛擬存儲器 外存儲器,主存儲器,基本概念 隨機存儲器 只讀存儲器 主存儲器與CPU的連接 新型存儲器,主存儲器特征,由半導體MOS存儲器組成 存儲單元：字存儲單元，字節(jié)存儲單元 按地址進行訪問 字地址，字節(jié)地址 主存空間包含讀/寫存儲空間和只讀存儲空間 屬于隨機訪問存儲器,主存儲器,基本概念 隨機存儲器 只讀存儲器 主存儲器與CPU的連接 高速主存儲器,半導體存儲器如何存儲數(shù)據(jù)？,S

4、RAM（CPU緩存）,DRAM 內(nèi)存條,二者為什么存在性能、容量、價格差異?,隨機存取存儲器（Random Access Memory）,靜態(tài)MOS存儲器 SRAM 動態(tài)MOS存儲器 DRAM,六管SRAM存儲器 (SRAM Cell),工作管T1 T2 存儲數(shù)據(jù) 負載管T3 T4 補充電荷 門控管T5 T6 T7 T8 開關(guān)作用,Vss(0V),VDD(5V),I/O,O/I,Y地址譯碼線,X地址譯碼線,MOS管的特性,放大狀態(tài) 截止狀態(tài) 導通狀態(tài),MOS管等效開關(guān)電路,截止狀態(tài),Rb,B,E,C,Ucc,導通狀態(tài),六管SRAM存儲器兩種狀態(tài),T4,T3,Vss(0V),T1,T2,T5,T

5、7,T8,T6,VDD(5V),Y地址譯碼線,I/O,A,B,X地址譯碼線,鐘擺三種狀態(tài),六管SRAM存儲器讀操作,X地址選通 T5、T6管導通 A點與位線相連 Y地址選通 T7、T8管導通 A點電位輸出到I/O端,T4,T3,Vss(0V),T1,T2,T5,T7,T8,T6,VDD(5V),Y,X地址譯碼線,I/O,A,B,D,六管SRAM存儲器寫操作,T4,T3,Vss(0V),T1,T2,T5,T7,T8,T6,VDD(5V),Y,X地址譯碼線,I/O,A,B,D,SRAM缺陷 MOS管過多，存儲密度低 功耗太大，單位容量成本高,位存儲體封裝與擴展,輸入：X 行選擇線 輸出：D 數(shù)據(jù)輸

6、出口 行選線選中方能讀寫數(shù)據(jù),X0,X1,X2,X3,64x64 存儲矩陣,I/O電路,一次讀出一行,0,63,1,63,63,63,給出行選，一行上所有存儲體均給行緩沖提供數(shù)據(jù),I/O電路,0,0,1,0,63,0,I/O電路,0,1,1,1,63,1,I/O電路,4k*4位存儲體,地址譯碼器,Y0 = A2A1A0OE,Y1 = A2A1A0OE,Y2 = A2A1A0OE,Y3 = A2A1A0OE,Y4 = A2A1A0OE,Y5 = A2A1A0OE,Y6 = A2A1A0OE,Y7 = A2A1A0OE,Logisim中的譯碼器,Logisim中的多路選擇器,Logisim中的解復

7、用器,譯碼方式,n位地址，尋址2n個存儲單元，2n根譯碼線,n位地址，尋址2n個存儲單元，2*2n/2根譯碼線,靜態(tài)存儲器芯片結(jié)構(gòu),n位X向地址,DBUS,驅(qū)動器與I/O電路,驅(qū)動器 一條選擇線帶很多存儲位時負載過大 在地址譯碼器輸出端增加驅(qū)動電路 保證每一個存儲位都能正常工作 I/O電路 存儲體與數(shù)據(jù)總線之間的電路 讀出時具有放大信號的作用,2114引腳圖,地址線 數(shù)據(jù)線（雙向） 讀寫控制線 片選線（chip select） 電源線 地線,SRAM內(nèi)部結(jié)構(gòu),行 選 擇,輸入 數(shù)據(jù) 控制,A3,A4,A5,A6,A7,A8,I/O1,I/O2,I/O3,I/O4,A0,A1,A2,A9,CS,

8、WE,存儲矩陣,如何提高存儲密度,Vss(0V),T1,T2,T5,T7,T8,T6,I/O,A,B,D,X地址譯碼線,Y地址譯碼線,去掉兩個負載管 提升存儲密度 減少功耗 降低成本 增加兩個電容緩存電荷 電容不能永久保存電荷 增加額外電路補充,四管DRAM存儲器,Vss(0V),T1,T2,T5,T7,T8,T6,I/O,O/I,Vss(0V),X地址譯碼線,Y地址譯碼線,A,B,C1,C2,D,DRAM存儲原理 利用電容電荷存儲數(shù)據(jù) 電容不能永久保存電荷 必須增加額外電路補充,T9、T10、T7、T8共享電路,四管DRAM存儲器寫操作,Vss(0V),T1,T2,T5,T7,T8,T6,I

9、/O,O/I,Vss(0V),Vss(0V),預充,T10,T9,ED,X地址譯碼線,Y地址譯碼線,A,B,C1,C2,CD,CD,D,ED,Y地址選通 T7、T8管導通 I/O端數(shù)據(jù)寫入到位線 X地址選通 T5、T6管導通 位線相連與C2相連,四管DRAM存儲器讀操作,Vss(0V),T1,T2,T5,T7,T8,T6,I/O,O/I,Vss(0V),Vss(0V),預充,T10,T9,ED,X地址譯碼線,Y地址譯碼線,A,B,C1,C2,CD,CD,D,ED,給出預充信號 T9、T10導通 充電電壓給CD充電 撤除預充信號 X地址選通 T5、T6管導通 位線相連與C2相連 CD給C2充電

10、補充電荷 Y地址選通 T7、T8管導通 C2數(shù)據(jù)讀出到I/O 讀過程比寫復雜、速度慢,四管DRAM存儲器刷新,Vss(0V),T1,T2,T5,T7,T8,T6,I/O,O/I,Vss(0V),Vss(0V),預充,T10,T9,ED,X地址譯碼線,Y地址譯碼線,A,B,C1,C2,CD,CD,D,ED,進一步提高存儲密度,T8,T6,O/I,Vss(0V),X地址譯碼線,Y地址譯碼線,C1,B,進一步提高存儲密度 核心是電容 裁剪冗余電路,單管DRAM存儲器,Vss(0V),T1,D,X地址譯碼線,C,電容用于存儲電荷，有電荷代表1，否則代表0,I/O,Y地址譯碼線,T2,DRAM 刷新,刷

11、新：定期補充電荷以避免電荷泄露引起的信息丟失 電容存在泄露電流 刷新周期: 存儲器兩次完整刷新之間的時間間隔 信息存儲到泄漏之間必須完成刷新，稱為最大刷新周期 按行刷新 存儲體采用雙譯碼結(jié)構(gòu)，刷新地址計數(shù)器給出刷新行地址 刷新方式 CPU與刷新控制器對DRAM的爭用問題 集中式、分散式、異步式,集中刷新方式,最大刷新周期：2ms 在數(shù)據(jù)丟失之前集中刷新所有行 存在死區(qū)，用在實時要求不高的場合,分散刷新方式,最大刷新周期：2ms 存儲周期：讀寫+刷新 各刷新周期分散安排在存取周期中 刷新次數(shù) 2ms/100ns=20000次 較浪費，用在低速系統(tǒng)中,異步刷新方式,刷新周期：2ms，各刷新周期分散

12、安排在2ms內(nèi) 每隔2ms/128=15.5微秒刷新一行,將128次刷新分散 最常用,2116引腳圖,地址線 數(shù)據(jù)線 讀寫控制線 RAS CAS 電源線 地線,主存儲器,基本概念 隨機存儲器 只讀存儲器 新型存儲器 主存儲器與CPU的連接,只讀存儲器(ROM),掩模式只讀存儲器 一次編程只讀存儲器（PROM） 多次編程只讀存儲器（EPROM, EEPROM）,只讀存儲器,只讀存儲器陣列,行地址譯碼器,輸出,片選,VCC,列地址譯碼器,5,-55-,熔絲式ROM(PROM),可擦寫ROMEPROM,MOS管與EPROM的兩種狀態(tài),EPROM,高壓寫入 紫外線光照擦除,編程器,紫外線擦除器,電可擦

13、寫ROMEEPROM E2PROM,ElectricallyErasableProgrammableROM,易失性半導體存儲器 VOLATILE,DRAM FPM DRAM (Fast Page Mode RAM) EDO DRAM (Enhanced Data Out DRAM) SDRAM (Synchronous DRAM) PC66 PC100 PC133 168 pin DDR SDRAM (double data rate synch. DRAM) PC1600 PC2100 PC2700 PC3200 184 pin DDR200 DDR266 DDR333 DDR400 DDR

14、600 RDRAM (Rambus DRAM) SRAM,非易失性半導體存儲器 NON-VOLATILE,ROM (read only memory) PROM (Programmable ROM) EPROM (Erasable PROM) EEPROM (Electrically Erasable PROM) NVRAM (Non-volatileRAM) BRAM (Battery-backup RAM) FERAM (FerroelectricRAM) MRAM (Magnetoresistive RAM) PCRAM (Phase changed RAM),閃速存儲器 Flash M

15、emory,在不加電時仍可長期保持信息 本質(zhì)上屬于EEPROM，存儲速度快 易于擦除和重寫，功耗很小 存放BIOS，升級方便，CIH病毒 NOR for (i = 0; i n; i+) sum += ai.x + ai.y; return sum;,程序局部性舉例,哪個程序具有更好的局部性,int aMN; for (i = 0; i M; i+) for (j = 0; j N; j+) sum += aij;,int aMN; for (j = 0; j N; j+) for (i = 0; i M; i+) sum += aij;,圖書館與Cache的類比,Main Memory,Of

16、f-chip cache,on-chip cache,DISK,反復看同一本書、同一章節(jié)，概率隨時間變低 看第n章，可能會看n+1章,cache基本思想,在處理器附近增加一個隱藏的小容量快速存儲器 對程序員透明 將經(jīng)常訪問的熱數(shù)據(jù)的副本存放在cache中 提高命中率優(yōu)化讀性能 預讀處理 - 空間局部性 淘汰算法 - 時間局部性,Cache,讀請求,寫請求,I/O響應(yīng),cache讀操作流程,讀請求,命中（HIT）,缺失（MISS）,讀請求,Cache,Cache,缺失造成訪問速度急劇下降,cache寫操作流程,寫請求,寫響應(yīng),Cache,Cache,寫穿策略 WriteThrough,寫回策略

17、Write Back,寫請求,寫響應(yīng),無臟數(shù)據(jù)，無丟失數(shù)據(jù)風險，寫速度慢,存在臟數(shù)據(jù)，有丟失數(shù)據(jù)風險，突發(fā)寫速度快, 持續(xù)寫性能？,U盤使用中的一些誤區(qū),下列情況是否需要安全刪除U盤 僅僅將U盤數(shù)據(jù)拷貝到硬盤 不涉及寫操作，無臟數(shù)據(jù)，無數(shù)據(jù)不一致性 將文件拷貝到U盤后2分鐘 后臺程序已經(jīng)將臟數(shù)據(jù)寫入到U盤 緩存數(shù)據(jù)與U盤數(shù)據(jù)一致 拷貝過程中,U盤免安全刪除的方法,采用寫穿策略 為快速刪除而優(yōu)化 寫入到U盤才能返回 寫性能略微降低,Multi-level caches,size: speed: $/Mbyte: line size:,200 B 3 ns 8 B,8-64 KB 3 ns 32

18、B,128 MB DRAM 60 ns $1.50/MB 8 KB,30 GB 8 ms $0.05/MB,larger, slower, cheaper,Memory,TLB,L1 Icache,L1 Dcache,regs,L2 Cache,Processor,1-4MB SRAM 6 ns $100/MB 32 B,larger line size, higher associativity, more likely to write back,Options: separate data and instruction caches, or a unified cache,disk,c

19、ache 術(shù)語,命中 hit: CPU訪問數(shù)據(jù)在cache中（上層存儲器） 缺失 miss: CPU訪問數(shù)據(jù)不在cache中 塊 block: cache與主存交換最小單位 塊大小多少合適？ 實現(xiàn)預讀 行/槽 Line/Slot 標記、標志位、數(shù)據(jù)塊容器 有效位、查找標記、臟標志位、置換標志、數(shù)據(jù)塊副本 Cold Cache、Warm Cache,cache 術(shù)語,命中率 （ hit rate ） 主存訪問中cache命中比例 缺失率 （miss rate） 1 命中率 命中訪問時間: （hit time） 數(shù)據(jù)查找時間、cache訪問時間、總線傳輸時間 缺失損失 （miss penalty）

20、 主存塊調(diào)入cache，數(shù)據(jù)傳輸?shù)教幚砥鞯臅r間 遠大于命中時間，所以一些相對較小的時間可忽略,cache關(guān)鍵技術(shù),數(shù)據(jù)查找 Data Identification 如何判斷數(shù)據(jù)在cache中 地址映射 Address Mapping 主存數(shù)據(jù)如何放置到cache行/槽中 替換策略 Placement Policy cache滿后如何處理 寫入策略 Write Policy 如何保證cache與memory的一致性,如何查找,查找關(guān)鍵字 (主存地址) 主存地址 Cache 地址 程序員軟件思路 查找表 - 如何快速查找 架構(gòu)師硬件思路 相聯(lián)存儲器 - 硬件并發(fā)查找,相聯(lián)存儲器 associati

21、ve memory,按內(nèi)容進行訪問的存儲器,（Key,Value）,用關(guān)鍵字去檢索存儲器中部分字段，對包含關(guān)鍵字的存儲單元進行讀寫，以內(nèi)容作為地址訪問的存儲器稱為相聯(lián)存儲器,相聯(lián)存儲器邏輯框圖,1,相聯(lián)存儲器 讀邏輯實現(xiàn),檢索關(guān)鍵字,輸出value,相聯(lián)存儲器,按內(nèi)容進行訪問（Key，Value） 以關(guān)鍵字作全局并發(fā)比較 硬件成本高 ( 比較器多 ) 存放查找表 (獨立硬件，不在緩存中) 存儲容量 = 查找表容量 = cache塊數(shù) * 表項大小 cache中用于存放塊表，虛擬存儲器中存放段表、頁表 （valid, Key， Value ） ( 有效位, 主存塊地址 ， Cache塊地址） 注

22、：value不一定是必要的,CPU cache基本組織方式,CPU cache由較快的SRAM構(gòu)成 cache與主存均分為固定大小的數(shù)據(jù)塊，以塊為單位交換數(shù)據(jù) 相聯(lián)存儲器存放查找表 表項：(有效位，調(diào)入cache的主存塊地址，cache塊地址） 容量 = cache塊數(shù) * 表項大小 CPU給出的塊地址與查找表中某單元相同且有效位為1表示命中 全相聯(lián)：硬件多路并發(fā)比較提升查找速度 軟件cache如何優(yōu)化查找速度？,塊地址與塊內(nèi)地址,11位,4位,主存,8位,4位,Cache,A11 A10,塊地址,A14 A13,A3 A2 A1 A0,塊地址,A5 A4,A3 A2 A1 A0,A5 A4,

23、塊內(nèi)地址,塊內(nèi)地址,相聯(lián)存儲器容量？,查找表表項內(nèi)容（valid，主存塊地址，Cache塊地址） 查找表表項數(shù)目 = Cache塊數(shù) 總?cè)萘?=（1+11+8）*28,CPU cache系統(tǒng)讀過程,CPU給出主存地址（塊地址，塊內(nèi)地址） 主存塊地址為關(guān)鍵字查找相聯(lián)存儲器中的查找表 如相符表示副本在cache中，命中，訪問cache 否則數(shù)據(jù)缺失，訪問主存 將數(shù)據(jù)所在塊副本調(diào)入cache（塊交換-局部性） 載入副本過程可能引起替換 更新查找表，記錄當前數(shù)據(jù)塊地址 cache缺失時系統(tǒng)等待數(shù)據(jù)調(diào)入,結(jié)束,CPU cache 讀操作,RA塊地址 cache查找？,CPU接收到 讀地址RA,開始,為主

24、存塊 分配Cache行,CPU cache系統(tǒng)寫過程,CPU給出主存地址 主存塊地址為關(guān)鍵字查找相聯(lián)存儲器中查找表 相符則表示命中，數(shù)據(jù)副本在cache中 缺失根據(jù)寫分配策略決定是否將該主存地址對應(yīng)數(shù)據(jù)塊調(diào)入 寫入數(shù)據(jù)到cache 根據(jù)寫策略決定是否寫入主存,結(jié)束,寫入WA數(shù)據(jù) 到主存中,CPU cache 寫操作,寫策略,No,寫回,寫穿,缺失,不一致性,寫分配,裝載主存塊 到Cache行,寫入WA數(shù)據(jù) 到Cache行,命中,查找,由CPU接收到 寫地址WA,開始,cache關(guān)鍵技術(shù),數(shù)據(jù)查找 Data Identification 如何判斷數(shù)據(jù)在cache中 地址映射 Address Ma

25、pping 主存數(shù)據(jù)如何放置到Cache行/槽中 替換策略 Placement Policy Cache滿后如何處理 寫入策略 Write Policy 如何保證cache與memory的一致性,主存與cache地址映射關(guān)系,利用某種方法或規(guī)則將主存塊定位到cache稱為地址映射 直接相聯(lián) (direct mapped) 全相聯(lián) (fully-associated) 組相聯(lián) (set-associated),第0塊,第0塊,第1塊,第n-1塊,第m-1塊,Cache,主存,如何進行地址映射?,全相聯(lián)映射,L0,L1,Ln-1,Bn,Bn+1,B2n-1,Bmn,Bmn+1,B2n,B2n+1,

26、B3n-1,Bmn+n-1,B0,B1,Bn-1,B0,B1,Bn-1,主存（DRAM）,cache副本(SRAM),主存塊可放置在任意cache行,查找表（CAM）,Hit,全相聯(lián)映射邏輯實現(xiàn) (工程觀),比較結(jié)果,1,多路并發(fā)比較電路,L0,2,Hit/miss,全相聯(lián)存儲器硬件開銷,SRAM 存放數(shù)據(jù)塊副本 相聯(lián)存儲器 CAM ，Content Addressed Memory 存放查找表，按內(nèi)容進行訪問（Key，Value） 有效位，key，value，標志位（Dirty bit），置換標記（訪問頻率等） 查找表總?cè)萘?cache行數(shù) *（1+主存塊地址位寬+cache地址位寬+1+置

27、換標記長度） 如果查找表和緩存都在CPU內(nèi)部，可以不需要cache塊地址,全相聯(lián)映射動態(tài)載入過程,有效位,TAG,數(shù)據(jù)塊副本緩沖區(qū),0,0,0,0,0,0,0,0,1,1F,20,24,1E,48,54,107,訪問序列,miss,Cache 8行，塊大小4W，主存29 W Cache總?cè)萘?（valid+標記位+標志位+副本容量）*總行數(shù),比較結(jié)果,Hit,1F,L0,L1,L2,L3,L4,L5,L6,L7,字輸出,SlotData,主存地址,W0,W1,W2,W3,八路并發(fā)比較電路,miss,Hit,miss,OE,全相聯(lián)應(yīng)用場合,塊映射靈活，一對多映射 cache全部裝滿后才會出現(xiàn)塊沖

28、突 塊沖突的概率低，cache利用率高 淘汰算法復雜 命中率高,直接相聯(lián)映射,B0,B1,Bn-1,Cache SRAM,Cache塊號i, 共n塊，主存塊號j，i=j mod n,Hit,=？,Bn,Bn+1,B2n-1,Wmn,Wmn+1,B2n,B2n+1,B3n-1,Wmn+n-1,B0,B1,Bn-1,主存DRAM,n=2s，m=2t,直接相聯(lián)映射邏輯實現(xiàn) (工程觀),TAG,數(shù)據(jù)塊副本緩沖區(qū),有效位,Hit/miss,Hit,L1,有效位+TAG,=？,直接相聯(lián)映射載入過程,Hit/miss,miss,Hit,1F,20,24,1E,48,54,107,Cache 8行，塊大小4W

29、，主存29 W Cache總?cè)萘?（valid+標記位+標志位+副本容量）*總行數(shù),訪問序列,Hit,miss,直接相聯(lián)映射,Cache容量 = 行大小*行數(shù) =（標記位+標志位+數(shù)據(jù)塊+置換標記）* 行數(shù) 標記位=區(qū)地址 標志位（有效標志位，臟數(shù)據(jù)位） 無相聯(lián)存儲器，所有信息均存放在SRAM,直接相聯(lián)應(yīng)用場合,塊映射速度快，一對一映射，無須查表 利用索引字段直接對比相應(yīng)標記位即可 查找表可以和副本一起存放，無需相聯(lián)存儲器 cache容易沖突，cache利用率低 淘汰算法簡單 命中率低，適合大容量cache,組相聯(lián)映射,L1,Bn,Bn+1,B2n-1,B2n,B2n+1,B0,B1,Bn-1

30、,高速緩存B0,高速緩存B1,標記,標記,V,V,D,D,主存,Cache,L1,高速緩存B0,高速緩存B1,標記,標記,V,V,D,D,L1,高速緩存B0,高速緩存B1,標記,標記,V,V,D,D,Cache分n組，n=2s 每組k塊，k路組相聯(lián),Hit,組索引譯碼輸出,組相聯(lián)映射邏輯實現(xiàn) (工程觀),數(shù)據(jù)塊副本緩沖區(qū),Hit/miss,1,k路并發(fā)比較,行譯碼 信號邏輯,查找表,組相聯(lián)存儲器硬件開銷,SRAM 存放數(shù)據(jù)副本 多個相聯(lián)存儲器共享一個多路比較器 相對于全相聯(lián) 多路比較器復雜度低 查找表表項內(nèi)容（valid位，標記，dirty位，置換標記位） 相聯(lián)存儲器總?cè)萘?cache行數(shù)*（

31、1+標記寬度+1+置換標記位） 片外緩存如果查找表在CPU內(nèi)部？ 查找表中必須增加cache行地址？ why,組相聯(lián)映射動態(tài)載入過程,有效位,數(shù)據(jù)塊副本緩沖區(qū),1,主存地址,Hit/miss,TAG,1F,20,24,1E,48,54,107,訪問序列,組索引譯碼輸出,行譯碼 信號邏輯,Cache 8行，分4組，塊大小4W，主存29 W Cache總?cè)萘?（valid+標記位+標志位+副本容量）*總行數(shù),K0,K1,Hit,2路并發(fā)比較,Miss,不同映射方式主存地址劃分,全相聯(lián),直接相聯(lián),組相聯(lián),組相聯(lián)應(yīng)用場合,容量小的cache可采用全相聯(lián)映射或組相聯(lián)映射 Pentium CPU L1 L

32、2 cache 容量大的可采用直接映射方式 查找速度快，命中率相對低 但cache容量大可提高命中率 塊設(shè)備緩存,例題1,某計算機字長32位，采用直接映射Cache,主存容量4MB，Cache數(shù)據(jù)存儲體容量為4KB，字塊長度為8個字。 畫出直接映射方式下主存地址劃分情況。 設(shè)cache初始狀態(tài)為空，若CPU順序訪問0-99號單元，并從中讀出100個字，假設(shè)主存一次讀一個字，并重復此順序10次，請計算cache命中率。 如果cache的存取時間是2ns，主存訪問時間是20ns，平均訪問時間是多少。 Cache-主存系統(tǒng)訪問效率。,例題2,主存地址空間大小為256MB，按字節(jié)編址。指令數(shù)據(jù)Cach

33、e，均有8行，Cache行大小為64B，數(shù)據(jù)Cache直接相聯(lián)?，F(xiàn)有兩功能相同的程序A，B，其偽代碼如下所示： 假定int型數(shù)據(jù)為32位補碼，程序編譯時i,j,sum均分配在寄存器中，數(shù)組a按行優(yōu)先方式存放，首地址為320（十進制）。 1）若不考慮用于Cache一致性維護和替換算法的控制位，數(shù)據(jù)cache的總?cè)萘渴嵌嗌伲?2）數(shù)組元素a031,a11所在主存塊對應(yīng)的cache行分別是多少，行號從零開始。 (3)程序A，B的數(shù)據(jù)訪問命中率各是多少？那個程序的執(zhí)行時間更短?,int a256256; for (i = 0; i 256; i+) for (j = 0; j 256; j+) sum

34、 += aij;,int a256256; for (j = 0; j 256; j+) for (i = 0; i 256; i+) sum += aij;,程序A,程序B,高速緩沖存儲器,Cache基本原理 相聯(lián)存儲器 主存與Cache的地址映射 替換策略與寫操作策略 Cache實際應(yīng)用,替換策略與寫操作策略,替換策略 先進先出法 最近最不經(jīng)常使用方法-LFU 近期最少使用法- LRU 隨機替換法,Cache先進先出替換策略(FIFO),載入,載入,命中,載入,載入,替換,替換,替換,220,110,70,160,222,190,40,30,Cache最不經(jīng)常使用算法(LFU),載入,載入

35、,命中,載入,命中,載入,替換,替換,220,11,111,16,221,19,4,3,命中,222,Cache近期最久未使用算法(LRU),載入,載入,命中,載入,載入,替換,替換,替換,220,110,70,160,220,190,40,30,LRU算法軟件實現(xiàn),FIFIO LFU LRU 隨機調(diào)度 硬件實現(xiàn) 成本？ LRU算法軟件實現(xiàn)？ 查找效率如何優(yōu)化？,先進先出策略下的替換顛簸,載入,載入,載入,載入,替換,替換,替換,替換,22*,11,16,22,19,7,11,19,寫入策略,寫回法(write back) 寫穿法 (write through) 寫分配（write-alloc

36、ate） 寫不分配（not-write-allocate）,cache對存儲系統(tǒng)性能的影響,讀優(yōu)化 時間局部性 將剛訪問的數(shù)據(jù)調(diào)度到cache中、利用淘汰算法將不經(jīng)常使用的數(shù)據(jù)淘汰 空間局部性 大塊預讀，相鄰的數(shù)據(jù)被調(diào)度到cache中 寫優(yōu)化 寫回策略提升突發(fā)寫性能 負面影響 寫回策略引起不一致性 緩沖區(qū)滿后，寫性能降低,cache命中率,命中率 Nc表示cache完成存取訪問的總次數(shù) Nm表示主存完成存取訪問的總次數(shù) ta平均訪問時間 tc表示命中cache時的訪問時間 tm表示命中主存時的訪問時間 訪問效率=tc/ ta 影響命中率的幾個因素 程序行為（局部性） cache容量 組織方式

37、塊大小,= + , = +() ,cache的命中率與cache容量的關(guān)系,塊容量與命中率 Is bigger always better?,塊越大，塊數(shù)量越少 空間局部性越好 時間局部性不佳 缺失率提升 極端例子 一個cache只有一塊,地址映射與命中率,高速緩沖存儲器,Cache基本原理 相聯(lián)存儲器 主存與Cache的地址映射 替換策略與寫操作策略 Cache實際應(yīng)用 塊設(shè)備緩存、硬盤緩存、web cache,塊設(shè)備緩存,OS為優(yōu)化磁盤等慢速塊設(shè)備在內(nèi)存中設(shè)置緩存 將常用數(shù)據(jù)存放在高速緩存中，提高磁盤訪問速度 通過預讀等提高命中率的方式可減少讀訪問時間 通過寫回策略減少寫訪問時間 CPU將

38、數(shù)據(jù)寫入cache即完成寫操作 提升突發(fā)寫性能 僅寫入cache的數(shù)據(jù)稱為臟數(shù)據(jù) 操作系統(tǒng)定時將臟數(shù)據(jù)寫入磁盤保證數(shù)據(jù)一致性 當系統(tǒng)中存在臟數(shù)據(jù)，磁盤斷電?,硬盤緩存,硬盤緩存是硬盤上內(nèi)存芯片 預讀硬盤數(shù)據(jù)，寫緩沖CPU數(shù)據(jù) 臨時存儲最近訪問的硬盤數(shù)據(jù) 緩解硬盤與CPU、內(nèi)存的速度不匹配 緩存容量越大，硬盤訪問速度越快 副作用？,WEB cache, :3128 將用戶常訪問的web內(nèi)容暫存在離用戶近的地方 其他用戶再次訪問這些內(nèi)容時可以快速獲得信息，縮短了響應(yīng)時間，從而提高訪問速度和降低國際通信費用。 應(yīng)有機制保障用戶每次訪問的數(shù)據(jù)不會過時,Intel Pentium cache hiera

39、rchy,Processor Chip,L1 Data 1 cycle latency 16KB 4-way assoc Write-through 32B lines,L1 Instruction 16KB, 4-way 32B lines,Regs.,L2 Unified 128KB-2 MB 4-way assoc Write-back Write allocate 32B lines,Main Memory Up to 4GB,Intel Itanium 3級Cache,IBM Power4 , 1999,But What About More “Typical” Processors

40、,Intel 90 nm Pentium M Processor (2 MB cache) Toms Hardware,Intel Pentium 4, 2.2 GHz Processor,Examples of caching in the hierarchy,本章主要內(nèi)容,存儲器概述 主存儲器 高速緩沖存儲器 虛擬存儲器 外存儲器,虛擬存儲器,比爾蓋茨(1981) “ 無論對誰來說,640K內(nèi)存都足夠了” 如何在有限的主存空間運行較多的較大的用戶程序？ 初衷： 采用虛存來擴大尋址空間 現(xiàn)在： 主要用于存儲保護，程序共享 主存、輔存在OS和硬件的管理之下，提供比實際大得多的存儲空間 虛存空間

41、是靠輔存（磁盤）來支持的 虛擬存儲采用與Cache類似原理，提高速度，降低成本 用戶感覺到的是一個速度接近主存而容量極大的存儲器,虛擬內(nèi)存實例,Linux 交換分區(qū)swap Windows 頁面文件,頁式虛擬地址空間,第0塊,第0頁,第1頁,第n-1頁,0頁,1,N-1,主存空間,虛擬空間,磁盤,部分磁盤,Page table（頁表，查找表）,頁表大?。宽摫泶娣拍睦?？ 頁表有多少個？,頁式虛擬存儲器結(jié)構(gòu),頁表基地址寄存器 PTBR,實地址計算機系統(tǒng),CPU給出的地址直接訪問物理內(nèi)存 大多數(shù)Cray計算機，早期PC，大多數(shù)嵌入式系統(tǒng),虛地址計算機系統(tǒng),CPU地址需要虛實變換 硬件通過OS維護的頁

42、表將虛擬地址轉(zhuǎn)換為物理地址 工作站，服務(wù)器，現(xiàn)代PC,Memory,0:,1:,P-1:,Page Table,Virtual Addresses,Physical Addresses,Part Disk,缺頁 Page Faults,頁表指示虛擬地址不在內(nèi)存中 操作系統(tǒng)負責將數(shù)據(jù)從磁盤遷移到內(nèi)存中 當前進程掛起 操作系統(tǒng)負責所有的替換策略 喚醒掛起進程,CPU,Memory,Page Table,Virtual Addresses,Physical Addresses,Before fault,Part Disk,層次性結(jié)構(gòu),CPU,Cache,主存,輔助存儲器,DMA傳送,物理地址,物理地

43、址,虛擬地址,數(shù)據(jù),數(shù)據(jù),虛擬存儲器本質(zhì),程序員在比實際主存大得多的邏輯地址空間中編程 程序執(zhí)行時，按需載入代碼和數(shù)據(jù)，無需全部載入 硬件將邏輯地址（虛擬地址）轉(zhuǎn)化為物理地址（實地址） 缺頁時，由OS進行主存和磁盤之間的信息交換 虛存機制由硬件與操作系統(tǒng)協(xié)作實現(xiàn) 進程及進程上下文切換、存儲器分配 虛擬地址空間管理、缺頁處理 存儲器保護,與CPU cache的相似之處,將程序中常用的部分駐留在高速存儲器 程序載入按需載入（不是全部載入） 高速存儲器分塊或者分頁（粒度問題） 主存空間滿，將不常用程序或數(shù)據(jù)淘汰或交換到輔存中 數(shù)據(jù)的換入換出由硬件或操作系統(tǒng)完成，對用戶透明 利用程序局部性，使存儲系統(tǒng)

44、的性能接近于高速存儲器；價格接近于低速存儲器，并擴充主存容量,與CPU cache的差異,虛存用于擴大主存容量，CACHE用于加速主存性能 虛存中未命中性能損失遠大于CACHE系統(tǒng) 全相聯(lián)提升命中率 更大的交換單位頁 近似LRU算法 (CLOCK算法) 虛存由硬件和OS聯(lián)合管理，CACHE由硬件管理,段式管理,段的分界與程序的自然分界相對應(yīng)，段長不固定，因程序而異 段的獨立性易于編譯、管理、修改和維護，也便于多道程序共享 各段的長度不同，給主存的分配帶來麻煩 段式管理容易產(chǎn)生碎塊，浪費主存空間,頁式管理,信息交換的單位是定長的頁。 主存與外存均劃分成等長的頁面。 便于維護，便于生成頁表，類似于

45、cache的塊表 不容易產(chǎn)生碎塊，存儲空間浪費小 頁不是獨立的實體，處理、保護和共享不方便,段頁式管理,程序按模塊分段 段再分成長度固定的頁。 程序調(diào)入調(diào)出按頁面來進行 程序共享保護按段進行 兼?zhèn)涠问?，頁式管理的?yōu)點 在地址映像中需要多次查表,虛擬地址物理地址 （頁命中）,Cache Memory (頁表),5)數(shù)據(jù),CPU,1) VA,3)PTE,4)PA,2)PTEA,處理器,MMU,5)調(diào)出頁,6)調(diào)入頁,虛擬地址物理地址（缺頁）,缺頁異常處理程序,4)異常,1)VA,7)返回產(chǎn)生缺頁異常的進程,2)PTEA,3)PTE,虛存，cache，主存層次,MMU,CPU,1) VA,4)PA,

46、2) PTEA,PTE塊,PTEA缺失 PTEA,PA缺失 PA,數(shù)據(jù)塊,存 儲 器 (頁表),高 速 緩 存 部分 頁表塊,處理器,快表提高頁式管理速度,頁表存放在主存，虛存空間即使命中也須先查頁表，再訪問主存，兩次訪存才能取出數(shù)據(jù)，速度慢 為提高頁表查找速度，采用cache的方法，引入一個體積小的快表，存放頁表中經(jīng)常被訪問的表項 快表與頁表交換的基本單位（頁表項？） 快表引入相聯(lián)存儲器機制，提高查找速度,經(jīng)快慢表實現(xiàn)內(nèi)部地址轉(zhuǎn)換,1) VA,TLB 命中,Cache Memory (頁表),2) VPN,3) PPN,4) PA,5) 數(shù)據(jù),OS維護TLB,1) VA,TLB 缺失,2)

47、VPN,3)TLB 訪問缺失,4) PA,7) 數(shù)據(jù),OS維護TLB,6) PA,5) PTE,Cache Memory (頁表),虛擬地址物理地址流程,開始,TLB提供 PPN,No,命中,PTEA在 Cache命中,PA=PPN+VPO,結(jié)束,PTE缺頁,TLB查找與Cache查找可以同步進行,TLB查找 (Key=VPN),MMU接收到 虛擬地址VA,更新TLB表,虛擬存儲器載入過程,程序按需載入，按頁面載入 載入頁面同時更新內(nèi)存中頁表 內(nèi)存滿時發(fā)生缺頁，完成數(shù)據(jù)交換 將不經(jīng)常使用頁面移到輔存 從輔存程序或數(shù)據(jù)調(diào)入新的頁面 頁面替換采用操作系統(tǒng)實現(xiàn)，cache數(shù)據(jù)替換由硬件實現(xiàn) 內(nèi)存滿后

48、系統(tǒng)性能？ 虛擬存儲器替換算法涉及磁盤操作，性能損失大于cache,存儲保護的基本概念,為避免多道程序相互干擾，防止某程序出錯而破壞其他程序的正確性或不合法地訪問其他程序或數(shù)據(jù)區(qū)，應(yīng)對每個程序進行存儲保護 操作系統(tǒng)程序和用戶程序都需要保護 以下情況發(fā)生存儲保護錯 地址越界（轉(zhuǎn)換得到的物理地址不屬于可訪問范圍） 訪問越權(quán)（訪問操作與所擁有的訪問權(quán)限不符） 頁表中設(shè)定訪問（存?。?quán)限 訪問屬性的設(shè)定 數(shù)據(jù)段可指定R/W或RO；程序段可指定R/E或RO,本章主要內(nèi)容,存儲器概述 主存儲器 高速緩沖存儲器 虛擬存儲器 外存儲器,外存儲器,磁表面存儲器原理 硬盤存儲器 光盤存儲器,磁表面存儲器原理,磁記

49、錄讀/寫原理 記錄方式,磁記錄原理,磁鼓、軟磁盤、硬磁盤、磁帶 將磁性材料薄薄的涂在金屬或塑料表面作載磁體存儲信息的方式稱為磁表面存儲 大多數(shù)外存儲器均采用磁記錄,磁記錄特點,容量大，位價格低 可重復使用 長期保存 非破壞性讀出 采用機械裝置，機械結(jié)構(gòu)復雜 速度慢 對工作環(huán)境要求高,磁記錄讀寫原理,磁頭：軟磁材料做鐵芯，繞有讀寫線圈的電磁鐵 磁性材料剩磁的兩種磁化方向 (S-N / N-S)表示0和1 寫入（電磁變換） 利用寫線圈中的脈沖電流，將數(shù)值轉(zhuǎn)換成磁存儲單元中的不同剩磁狀態(tài) 讀出（磁電變化） 通過讀線圈，將存儲單元的剩磁狀態(tài)轉(zhuǎn)換為電信號輸出,磁性材料物理特性,I-電流 B-磁感應(yīng)強度

50、H-外加磁場強度 磁性材料被磁化后， 工作點總在磁滯回線上。 剩磁狀態(tài)+Br , Br。 HC 矯頑磁力 矩形磁滯回線Br 較大容易讀出，矯頑力Hc較小容易磁化，易于寫入信息,記錄方式,一個剩磁磁化方向到底代表幾個數(shù)據(jù)？ 形成不同寫入電流的方式稱為記錄方式 不歸零制（NRZ0） 見“1”就翻不歸零制（NRZ1） 調(diào)相制（PM） 調(diào)頻制（FM） 改進調(diào)頻制（MFM）,不歸零制NRZ (Not Return Zero),數(shù)據(jù)序列,1,0,0,0,1,1,1,0,NRZ0,NRZ1,調(diào)相制、調(diào)頻制,數(shù)據(jù)序列,1,0,0,0,1,1,1,0,PM,FM,MFM,1,0,0,0,1,1,1,0,數(shù)據(jù)序列

51、,NRZ0,NRZ1,PM,FM,MFM,磁記錄方式,編碼效率： 每次磁化方向變化所存取的數(shù)據(jù)的多少 自同步能力：從讀出數(shù)據(jù)中自動提取同步信號的能力,硬盤存儲器,硬盤基本組成 硬盤數(shù)據(jù)信息分布 硬盤讀寫過程,硬盤基本組成,盤片組 主軸驅(qū)動機構(gòu) 磁頭 磁頭驅(qū)動定位機構(gòu) 讀寫電路 接口及控制電路 空氣過濾系統(tǒng),Disk operation (multi-platter view),磁盤數(shù)據(jù)分布,磁盤包括若干盤片，每個盤片兩個記錄面 每個記錄面包括若干同心圓-磁道 每個磁道被間隙gap分割為若干扇區(qū),spindle,surface,tracks,track k,sectors,gaps,Disk g

52、eometry (muliple-platter view),Aligned tracks form a cylinder.,surface 0,surface 1,surface 2,surface 3,surface 4,surface 5,cylinder k,spindle,platter 0,platter 1,platter 2,Disk operation (single-platter view),By moving radially, the arm can position the read/write head over any track.,The disk surfa

53、ce spins at a fixed rotational rate,The read/write head is attached to the end of the arm and flies over the disk surface on a thin cushion of air.,磁盤信息編址和記錄格式,盤面號區(qū)分要訪問哪個記錄面。 所有記錄面上半徑相等的磁道的集合稱為圓柱面Cylinder。 圓柱面數(shù)等于一個記錄面上的磁道數(shù)。 一臺主機如果配有幾臺磁盤驅(qū)動器，則還要給它們編號，以區(qū)分是哪臺磁盤機工作。因此磁盤地址格式為：,驅(qū)動器號,盤面號,柱面號,扇區(qū)號,Invention o

54、f HDD: 1956,5 Mbytes, 24 disks, 2kbits/in2,60 Years Later,硬盤最大容量10TB，單碟容量1.3-1.5TB，存儲密度約為1Tbpsi,計算機組成原理 Slide 234,-234-,50 Years and Still Going,Recording,硬盤發(fā)展,巨磁阻技術(shù) 垂直磁記錄 疊瓦記錄 shingled write recording,SSD超越，硬盤末日黃花,10TB SSD發(fā)布 3200MB/S,硬盤存儲器技術(shù)指標,存儲容量 (1GB=106byte) 存儲密度 平均存取時間,存儲密度,磁盤單位面積上所能存儲的二進制信息量

55、道密度是沿磁盤半徑方向單位長度上的磁道數(shù)，單位為道英寸 (TPI) 位密度是磁道單位長度上記錄的二進制代碼的位數(shù)，單位是位英寸 (BPI) 面密度：道密度位密度 ZONE,磁盤容量計算,Capacity = (# platters/disk) x (# surfaces/platter) x (#tracks/surface) x (avg. # sectors/track) x (# bytes/sector) 512 bytes/sector、300 sectors/track (on average)、20,000 tracks/surface 2 surfaces/platter、5

56、platters/disk 磁盤容量 = 512 x 300 x 20000 x 2 x 5 = 30,720,000,000 = 30.72 GB,數(shù)據(jù)傳輸率 byte/s,數(shù)據(jù)傳輸速率: 單位時間從磁盤讀/寫信息的數(shù)量 磁頭定位之后，傳輸速率與轉(zhuǎn)速、存儲密度相關(guān)。 位密度為M bits/英寸，轉(zhuǎn)速（線速度）為 V英寸/s ，則數(shù)傳率為MV bits/s。 轉(zhuǎn)速為m轉(zhuǎn)/s,單磁道容量為n字節(jié)，則數(shù)傳率為mn字節(jié)/s。,平均定位時間,定位時間 從發(fā)出磁盤讀寫命令起，磁頭從當前位置移動到目標位置，并開始讀寫操作所需時間 尋道時間 ts : 將磁頭定位到指定磁道上所需的時間 等待時間 tr （旋轉(zhuǎn)延時） : 找到指定道后至指定的記錄旋轉(zhuǎn)至磁頭下的時間， ts 和 tr 都是隨機變化的，所以往往用平均值表示。 Tavg rotation = 1/2 x 1/RPMs x 60 sec/1 min 平均定位時間 Tposition = Tavg seek + Tavg rotation,磁盤訪問時間,Ave