高級計算機系統(tǒng)結(jié)構(gòu)高速緩存.pptVIP

附：高速緩沖存儲器(Cache) 概述 Cache的起源和作用 MOS工藝半導體存儲器 雙極型高速存儲器 零等待時間 Cache與內(nèi)存的工作流程,CPU,Cache,命中,內(nèi)存,不命中, 程序特征與Cache的讀寫 怎樣判斷哪些數(shù)據(jù)和程序代碼是經(jīng)常被訪問的？ “程序執(zhí)行的局部性規(guī)律”,描述: 表現(xiàn)為那些最近被使用過的數(shù)據(jù)和指令被頻繁重新使用的規(guī)律。,統(tǒng)計值例:,統(tǒng)計表明: 在一個程序的執(zhí)行過程中, 執(zhí)行時間的90花在約10的程序代碼上。,對Gcc編譯器、Spice(CAD電路分析軟件)、以及TeX(文本處理軟件)三個典型測試程序的測試結(jié)果, 相應的比例分別為:13%、9.5、9.3,包括:時間局部性規(guī)律和空間局部性規(guī)律 時間局部性規(guī)律: 程序執(zhí)行過程中近期被訪問的信息可能很快將被再次訪問; 典型情況是程序中存在著大量的循環(huán)。 空間局部性規(guī)律: 那些與被訪問的地址相鄰近的信息可能很快被訪問; 典型情況是程序順序執(zhí)行。, 按照“局部性規(guī)律”, 數(shù)據(jù)或者代碼被訪問后, 該數(shù)據(jù)和代碼以及臨近的數(shù)據(jù)代碼近期被再次訪問的概率, 大于近期未被訪問的數(shù)據(jù)/代碼被訪問的概率。, 因此, 一個數(shù)據(jù)代碼被訪問后, 被認為是經(jīng)常被訪問的數(shù)據(jù)和代碼, 將其存入Cache , 使Cache有更高的命中率。,程序執(zhí)行的局部性規(guī)律具有普適性, 如: LRU淘汰算法 動態(tài)分支預測技術(shù) 內(nèi)存中存放近期被訪問的頁表, 大多數(shù)情況都能夠滿足應用需求 80386/486處理器的TLB表命中率超過90。, 命中率 Cache容量與命中率 Cache的結(jié)構(gòu)與命中率 與軟件以及所處理的數(shù)據(jù)量大小成反比 Cache的淘汰算法 先進先出算法 隨機淘汰 LRU(最近最久未使用淘汰)算法 LFU算法(訪問次數(shù)最少的內(nèi)容被淘汰) Cache命中與否的判斷 通過判斷該數(shù)據(jù)/代碼的地址是否在Cache中, 而不是判斷該數(shù)據(jù)/代碼本身。,一、高速緩存的結(jié)構(gòu)及工作原理 高速緩存的三種主要結(jié)構(gòu): 全關(guān)聯(lián)式高速緩存 直接對應式高速緩存 多組關(guān)聯(lián)式高速緩存,1、全關(guān)聯(lián)式高速緩存 高速緩存由兩部分組成, 即地址部分(稱為標簽)和數(shù)據(jù)部分, 如下圖所示(假設地址24位, 字長32位):,FFFFFC,000000,FFFFF4,16339C,FFFFF8,24682468,12345678,33332222,87654321,11223344,假設:,處理器讀取FFFFFC地址單元, 首先用該地址查找Cache, 不命中。,Cache,將數(shù)據(jù)24682468讀入處理器, 同時將地址FFFFFC寫入Cache標簽字段, 對應數(shù)據(jù)24682468寫入Cache數(shù)據(jù)字段。,處理器對存貯器的訪問過程:,讀操作:,CPU發(fā)出地址后, 首先查找Cache的標簽字段, 如果存在該地址(命中Cache), 讀取Cache中該地址對應的數(shù)據(jù)本分; 若不存在該地址(稱為不命中), 仍從主存單元中讀取數(shù)據(jù), 并同時將該地址和對應的數(shù)據(jù)分別寫入Cache的標簽字段和數(shù)據(jù)部分。,上述過程符合“程序?qū)嵭械臅r間局部性規(guī)律”, 如果下次再訪問該地址, 即可命中。,寫操作:,CPU寫數(shù)據(jù)時, 首先查找Cache , 有該地址則命中, 將該數(shù)據(jù)寫入Cache而不寫內(nèi)存。,全關(guān)聯(lián)式的優(yōu)缺點分別是:,優(yōu)點:,直觀、結(jié)構(gòu)簡單, Cache中數(shù)據(jù)的存放位置靈活。,缺點:,速度慢,Cache越大, 速度越慢。,平均查找次數(shù)為Cache容量的一半。,假設:,2、直接對應式高速緩存,主存容量16M(24位地址), Cache容量為64K, 字長32位。, 將16M內(nèi)存空間邏輯上分為每64K為一個頁面, 共計可分為16M64K=256(個頁面);, 將存儲空間的地址看作一個二維的地址, 即頁號和頁內(nèi)地址;, 與內(nèi)存二維地址相對應, Cache中的地址也分為頁號和頁內(nèi)地址, 分別稱為標簽字段 (即頁號)和索引字段(即頁內(nèi)地址) 。, 結(jié)構(gòu)及工作原理, 對于所有總共256頁, 需要8位地址作為標簽(即地址的高8位A23A16), 指明訪問哪一個頁面; 每頁64K。, 需要16位地址作為頁內(nèi)地址A15 A0 , 指明訪問一頁的哪個單元。如下圖所示:,指示某一單元,指示某一頁面,尋址過程: 以讀取01FFF8單元為例,譯碼地址的低16位FFF8, 找到索引位置, 取地址的高8位01與FFF8對應的標簽字段相比較, 相等則命中, 不相等則不命中。,FF頁,01頁,00頁,12345678,24682468,15891589,13452789,87654321,01,01,FF,32,12, 特征說明 所有頁面的相同頁內(nèi)地址競爭同一標簽字段 即只要索引值相同, 256個頁面的頁地址競爭該索引值對應的標簽字段; 索引不變, 只需修改標簽字段 索引字段保持不變, 變化的是標簽(即頁號)和數(shù)據(jù)部分。由于索引值不變, 因此索引值不需要比較, 一次譯碼即可找到。 只比較一次 用CPU給出地址的高8 (即頁號)與標簽字段比較, 相等則命中, 不相等則不命中。, 優(yōu)缺點說明 優(yōu)點 一次比較即可判斷命中與否, 速度快。 缺點 數(shù)據(jù)位置固定, 靈活性差; 由于“程序執(zhí)行的時間局部性規(guī)律” , 命中率可能很低。 比如: 反復且輪流讀取索引值相同但標簽不同的兩個或多個單元(比如01FFF8和12FFF8, 可能出現(xiàn)命中率為0 (如果采用全關(guān)聯(lián)式結(jié)構(gòu), 則每次都能命中)。,3、多組關(guān)聯(lián)式高速緩存 包括雙組關(guān)聯(lián)、四組關(guān)聯(lián)、八組關(guān)聯(lián)等。 結(jié)構(gòu)及工作原理 全關(guān)聯(lián)式與直接對應式的結(jié)合。 以雙組關(guān)聯(lián)為例, 假設: 內(nèi)存16M, Cache 64K。,將64K的頁面邏輯上再分為兩個32K。,對于32K頁面, 頁內(nèi)地址只需要15位, 共512個頁面，需要9位地址作標簽。,相對于直接對應式的一個64K的頁面來說, 雙組關(guān)聯(lián)的構(gòu)造形式下圖所示:,說明： 分為兩組后, 相當于同一索引字段競爭兩個標簽位置, 使競爭減少一半; 如果采用四組關(guān)聯(lián),則應將64K分為4個16K, 依此類推; 如果一直分下去到不能再分, 多組關(guān)聯(lián)式將演變?yōu)槿P(guān)聯(lián)式。, 優(yōu)缺點比較 優(yōu)點: 與直接對應相比, 由比較一次變?yōu)楸容^兩次，同一索引值由競爭同一標簽位置變?yōu)楦偁巸蓚€標簽位置, 競爭減少一半。因此, 命中率較直接對應式高。,缺點: 速度較直接對應式慢, 但比全關(guān)聯(lián)式快。 優(yōu)缺點都在前兩種結(jié)構(gòu)之間。,基本結(jié)構(gòu)的演進,將主存和Cache的存儲空間劃分為若干大小相同的頁(或稱塊)。,比如: 主存容量1MB, 分為2048頁, 每頁512B; Cache容量8KB, 分為16頁, 每頁512B。,1、全關(guān)聯(lián)式結(jié)構(gòu), 主存的每一頁(或塊)可以直接映像到Cache的任一頁(或塊)。 由于分頁, 主存分為兩個部分, 即頁標記(簡稱標記或標簽)和頁內(nèi)地址;共計2048個頁, 因此需要11位作為頁標記; 每一頁512個字節(jié), 需要9位頁內(nèi)地址。相應地, Cache也需要一個11位的標記作為頁號。 (共計20位地址對應主存的1M),如下圖所示:,2、直接對應式結(jié)構(gòu),每個主存頁只能復制到某個固定的Cache頁中。與前述基本的直接對應式結(jié)構(gòu)類似, 必須頁號(即標簽)相同, 頁內(nèi)地址(即索引)才有效 。,將共計2048個內(nèi)存頁面再分為128組, 每組16個頁面, 分別與Cache的16個頁對應。 其對應方式是: 內(nèi)存頁號做“模16”運算的結(jié)果對應Cache頁號。 因此, 內(nèi)存的0頁、16頁、32頁、48頁映射到Cache的0頁; 內(nèi)存的1頁、17頁、33頁、49頁. 映射到Cache的1頁.。,由于分組, 一個內(nèi)存地址邏輯上被分成三個部分:,主存頁號,組號,Cache地址,對Cache, 同樣設置一個7位的標記(對應內(nèi)存的組號)。訪存時, 將主存地址的高7位與Cache的7位標記做比較, 如果相同, 意味著主存高7位地址對應的組中的某個頁面在Cache中存在(命中),如下圖所示:,內(nèi)存頁號做“模16”運算的結(jié)果對應Cache頁號,3、組關(guān)聯(lián)式結(jié)構(gòu),以直接對應式為基礎, 將高速緩存的頁再分組。比如兩個頁面為一組(雙組關(guān)聯(lián))。 設內(nèi)存頁號j; Cache的組數(shù)量u, 則內(nèi)存塊映射到Cache的哪一組的關(guān)系式: j mod u,該公式的映射關(guān)系如下圖所示:,j: 內(nèi)存頁號 u: Cache的組數(shù)量 內(nèi)存頁映射到Cache的哪一組的關(guān)系式: j mod u Cache的一個組有兩個頁可供查找, 判斷是否命中。,例: 32個字節(jié)為一個頁, Cache共計16頁, 采用雙組關(guān)聯(lián)(兩頁為一組), 按字節(jié)編址。問內(nèi)存129號單元映射到Cache的哪一組?,解: 因為每一塊32個字節(jié), 因此129號單元在內(nèi)存的4頁。4 mod 8=4 (組),二、高速緩存的數(shù)據(jù)一致性 1、高速緩存內(nèi)容丟失,在正常工作情況下, Cache系統(tǒng)中的數(shù)據(jù)有兩份, 一份在Cache中, 另一份在主存對應地址單元中, 兩份內(nèi)容是一致的。,比如從主存的A1單元讀取一個數(shù)據(jù)D1后, Cache與主存的情況是:,(1) 丟失原因,Cache內(nèi)容與它對應主存內(nèi)容不一致例:, 計算出中間結(jié)果 x+y; 將x+y存入A1單元(命中), Cache與內(nèi)存不再一致;,計算函數(shù) M= (x+y) f(z),Cache與主存的當前情況:, 此時, 如果Cache控制器進行Cache更新, 并正好淘汰A1單元 , 即新數(shù)據(jù)和地址(假設是D2和A2)覆蓋x+y和A1, 則x+y從Cache中消失(主存也無x+y);, 計算出f(z) ; 從A1單元讀中間結(jié)果(x+y); 計算 M= (x+y) f(z) 得到錯誤結(jié)果 M= D1 f(z),(2) 解決方法 直寫方式(Write through 通寫/透寫/直寫) 基本思想:,寫命中Cache的同時將該數(shù)據(jù)寫入對應的主存單元, 使Cache和主存的同一地址中內(nèi)容保持一致。,如上例中, 將x+y存入Cache A1單元的同時, 將該數(shù)據(jù)寫入內(nèi)存的A1單元。, 回寫方式 (Write-Back 寫回),對Cache的每一數(shù)據(jù)塊, 增加了一個“更新位”。當寫命中Cache時, 不將該數(shù)據(jù)立即寫入內(nèi)存, 只將“更新位”置“1”, 用來指明當前Cache內(nèi)容與對應的主存單元是不一致的。,如上例, 如下圖所示:,如果地址A1及內(nèi)容x+y要被新的內(nèi)容(地址A2和內(nèi)容D2)淘汰, 則首先檢查A1的“更新位”, 如果為1, 表明當前Cache內(nèi)容與對應的主存內(nèi)容不一致; 則先將A1內(nèi)容(如上例的x+y)寫入主存A1單元, 然后才將地址A2和內(nèi)容D2寫入Cache, 同時將“更新位”清0。,如下圖所示:,結(jié)論:,中間結(jié)果x+y僅在Cache被淘汰, 但在內(nèi)存中仍然存在, 沒有丟失。,與直寫相比, 減少了寫內(nèi)存的次數(shù)。,2、Cache內(nèi)容過時 Cache內(nèi)容過時, 即Cache內(nèi)容不能反映當前系統(tǒng)的狀況。, 發(fā)生Cache內(nèi)容過時的條件, 多機(多處理器)系統(tǒng) 各處理器有自己的Cache 多處理器共享一部分內(nèi)存區(qū)域,如下圖所示(以三個處理器為例):,(用于多處理器之間的通信),多機對共享存儲區(qū)的要求:,各處理器的Cache單元內(nèi)容應與共享存儲區(qū)相同地址單元內(nèi)容一致,在共享內(nèi)存區(qū)域有一個單元Ai的內(nèi)容為Di , 如果在Cache內(nèi)有該地址和數(shù)據(jù), 則三個Cache的Ai單元內(nèi)都應該為Di。并且, 三個處理器的Cache必須能夠反映當前共享內(nèi)存區(qū)的“更新”情況。,例如:,如果哪一個Cache的某個單元內(nèi)容, 不能反映當前共享內(nèi)存區(qū)的“更新”情況。那么, 該Cache相應單元內(nèi)容就過時了(該內(nèi)容也稱為“過時數(shù)據(jù)”), Cache 內(nèi)容過時的概念及原因,例如(一致的情況):,圖: Cache單元與共享區(qū)對應單元內(nèi)容一致,假設:,處理器1向共享區(qū)的Ai單元寫入數(shù)據(jù)Dk (如下圖所示),則Cache2和Cache3的Ai單元內(nèi)容Di 成為過時數(shù)據(jù)。,過時數(shù)據(jù),Cache內(nèi)容過時的后果:,多處理器系統(tǒng)通過共享內(nèi)存交換數(shù)據(jù), 并共同完成某一項工作, 過時數(shù)據(jù)可能導致錯誤結(jié)果。,比如: 三個處理器共同完成一個復雜函數(shù)計算。,假設:,三個處理器在執(zhí)行過程中, 共享一個參數(shù)C, 該參數(shù)隨執(zhí)行過程的推進而變化, 該參數(shù)由處理器1提供, 通過共享存儲區(qū)交換該參數(shù)值(處理器2和處理器3通過共享存儲區(qū)獲取該參數(shù))。,如果處理器1計算出C=a1, 并寫入共享區(qū)單元Ai。當處理器2和處理器3需要該參數(shù)時, 讀Ai單元,不命中Cache (初始狀態(tài)下, Cache2和Cache3還沒有地址Ai ), 則訪問共享區(qū)Ai單元, 并將該地址以及內(nèi)容C=a1存入自己的Cache, 如下圖所示:,由于C是一個變化的值, 如果處理器1為C賦了一個新的值a2, 并寫入共享區(qū):,過時數(shù)據(jù),如果處理器2或處理器3需要再次讀取該參數(shù), 則讀Ai單元且命中Cache, 從自己的Cache Ai單元中讀取a1。, 解決Cache內(nèi)容過時的方法, 方法一 : 總線監(jiān)視,基于總線監(jiān)視的Cache內(nèi)容清除或標識無效,Cache控制器監(jiān)視系統(tǒng)地址總線。如果有其它處理器向內(nèi)存共享區(qū)中寫數(shù)據(jù)(寫入的地址在自身的Cache中存在), 意味著自身Cache的這一單元內(nèi)容將變?yōu)檫^時, 則將該單元內(nèi)容清除或標識為無效, 使Cache中不再有過時的數(shù)據(jù)。,但此時C的最新值應該是a2, 導致處理器2或處理器3產(chǎn)生計算錯誤。, 方法二 :,不可高速用存儲器,硬件透明性, 方法三 :,一種能夠避免過時數(shù)據(jù)的方法。 即凡是共享區(qū)的主存單元內(nèi)容都不能進入高速緩存，因此從根本上消除了“過時”。,硬件透明性包括:, 廣播方式(交叉連接), 多處理器使用同一個Cache(共享Cache),Cache,共享Cache, 多處理器使用同一個Cache(共享Cache),處理器1,Cache1,處理器2,Cache2, 廣播方式(交叉連接),Cache清除, 方法四 :,將Cache中所有已經(jīng)更新過的數(shù)據(jù)寫入主存儲器, 并清除Cache的所有內(nèi)容。 具體方法是: 在任一部件寫入共享主存之前, 對系統(tǒng)中的所有Cache都進行清除, 則任何Cache都不會有過時數(shù)據(jù)存在。,三