【正文】 不命中 命中 1）直接映象法 主存的頁以 2c為模映象到 Cache的固定位置上。由映象函數(shù)還可以看出，主存頁號的低 C位（即 j mod 2c）正好是它要裝入的 Cache的 頁 號。 直接映象函數(shù)為 i=j mod 2c ，其中 i是 Cache頁 號，j是主存 頁 號。 t位標(biāo)志用來區(qū)別記入的是主存中的哪一 頁 ，在一個新 頁 送入 Cache時，把主存地址的高 t位存入 Cache的標(biāo)志字段中。 頁面號 0 標(biāo)記 頁面號 1 …… 頁面號 2c1 標(biāo)記 標(biāo)記 頁面號 0 頁面號 1 …… 頁面號 2c1 頁面號 2c 頁面號 2c+1 …… 頁面號 2c+11 頁面號 2c+1 …… 頁面號 2m1 主存頁面標(biāo)記 Cache頁面地址 頁內(nèi)地址 m位 t位 c位 b位 t位 Cache 主存儲器 主存地址 頁面 標(biāo)記 按地址訪問 有效位 頁面號 Cache頁面地址 頁內(nèi)地址 頁內(nèi)地址 主存地址 Cache地址 相等 頁面 標(biāo)記 相等比較 不等 訪問 Cache 若比較相等，且有效位為 “1”，則用 Cache地址去 訪問 Cache，讀出的數(shù)據(jù) 送往 CPU t位 c位 b位 m位 直接映象的優(yōu)點(diǎn)是實(shí)現(xiàn)簡單，其缺點(diǎn)是不夠靈活。 出現(xiàn)Cache中還有很多空頁，也必須對指定的 Cache頁進(jìn)行替換。 主存和 Cache的讀出 CPU訪問時，首先根據(jù)訪存地址中的 C位 (頁號 )，直接查出該主存對應(yīng)的 Cache頁號。找到對應(yīng)的 Cache頁后，檢查它的標(biāo)記和主存的高 t位是否一致。若一致，訪問 ? 命中 ? ，再根據(jù)頁內(nèi)地址 (b位 )，從 Cache中讀數(shù)據(jù)。否則 ? 不命中 ? ，CPU直接從主存讀出。 例 :考慮一個具有 16KB直接相連 Cache的 32位微處理 器 ,假定該 Cache的頁面為 4個 32位的字 : (1)畫出 Cache的地址映像方式 ,指出主存地址的不同 字段的作用 。 (2)主存地址為 ABCDE8F8H的單元在 Cache中的什么 位置 ,指出主存頁面標(biāo)記、頁面號和頁內(nèi)地址值 . 頁面 標(biāo)記 Cache頁面 號 頁 內(nèi)字地址 字節(jié)號 頁面 號 頁 內(nèi)字地址 字節(jié)號 比較 0 1023 18位 10位 2位 2位 2位 2位 10位 不相等 頁面失效 主存 頁面 標(biāo)志 2位 Cache Cache地址 主存地址 地址映像方式 ABCDE8F8 H =1010 1011 1100 1101 11 10 1000 1111 10 00 頁面標(biāo)記 = 1010 1011 1100 1011 11 Cache頁號 = 10 1000 1111 頁內(nèi)字地址 = 10 字節(jié)地址 = 00 2）全相聯(lián)映象法 對應(yīng)關(guān)系 :主存中任一 頁面 可裝入 Cache內(nèi)任一 頁面 的位置。 ? 采用存放于 相聯(lián)存儲器中的目錄表 來實(shí)現(xiàn)地址映象；以加快 ? 主存 — Cache”地址變換速度。 第 2m1頁 … … 第 1頁 第 0頁 第 0頁 … 第 1頁 第 0頁 Cache 主存 全相聯(lián)映象法 主存 — Cache地址變換過程 讓主存頁號與目錄表中各項(xiàng)的頁號作相聯(lián)比較；如有相同的，則將對應(yīng)行的 Cache頁號取出，拼接上頁內(nèi)地址就形成了Cache地址。 相聯(lián)表中無相同的頁號，表示主存頁未裝入Cache，失靶，去主存讀。 優(yōu)點(diǎn)是頁面沖突概率最低；但查表速度難以提高。幾乎沒有單純采用全相聯(lián)映象法。 頁號 頁內(nèi)地址 主存地址 Cache地址 相聯(lián)比較 失靶 去主存讀 命中 頁號 頁內(nèi)地址 全相聯(lián)映象地址變換 ... ... 讓主存頁號與目錄表中各項(xiàng)的頁號作相聯(lián)比較；如有相同的，則將對應(yīng)行的 Cache頁號取出，拼接上頁內(nèi)地址就形成了Cache地址。 相聯(lián)表中無相同的頁號，表示主存頁未裝入Cache，失靶，去主存讀。 3）組相聯(lián)映象法 將 Cache空間分成若干組，每組包含若干頁， 組間采用直接映象，組內(nèi)各頁則是全相聯(lián)映象 。 全相聯(lián)映象法和直接映象法結(jié)合起來，就產(chǎn)生了組相聯(lián)映象法。 組相聯(lián)映像方式的地址變換過程如下圖所示。 區(qū)號 E ， 組內(nèi)頁號 B 組內(nèi)頁號 b C b 個塊 組內(nèi)頁號 B 組內(nèi)頁號 b 頁內(nèi)地址 W 頁內(nèi)地址 w 主存地址 Cache 地址 區(qū)號 E 相聯(lián)比較 塊表 組號 G 組號 g 相等 不等 Cache工作原理要求它盡量保存最新數(shù)據(jù)，必然要產(chǎn)生替換。 對直接映射的 Cache來說，只要把此特定位置上的原主存塊換出 Cache即可。 對全相聯(lián)和組相聯(lián) Cache來說， 就要從允許存放新主存塊的若干特定行中選取一行換出。 常用替換策略 – 先進(jìn)先出（ FIFO）策略 – 最近最少使用（ LRU）策略 ? FIFO 算法選擇最早裝入 Cache的頁面作為被替換的頁 。 ? 占用空間表的每一頁都與一個 ? 裝入順序數(shù) ? 相聯(lián)系，每當(dāng)一個頁送入 Cache 或從 Cache重取走，都將更新 ? 裝入順序數(shù) ? 。 ? 通過檢查這些數(shù)，決定最先進(jìn)入的頁。 先進(jìn)先出（ FIFO） 這種算法優(yōu)點(diǎn)是容易實(shí)現(xiàn)，缺點(diǎn)是經(jīng)常使用的頁，如一個包含程序循環(huán)的頁，也可能由于它是最早的頁而被替換掉。 ? LRU算法將近期內(nèi)長久未被訪問過的行換出。 ? 每行也設(shè)置一個計數(shù)器， Cache每命中一次，命中行計數(shù)器清零，其它各行計數(shù)器增 1。 ? 當(dāng)需要替換時，將計數(shù)值最大的行換出。 最近最少使用 (LRU)算法 這種算法保護(hù)了剛拷貝到 Cache中的新數(shù)據(jù)行，有較高的命中率。 *優(yōu)化替換算法（ OPT） 選擇將來最少使用訪問的 Cache頁為調(diào)出頁。 是一種理想 算法，命中率最高。 程序需運(yùn)行兩次，第一次分析地址流，第二次才真正運(yùn)行程序。 下面通過一個程序和的運(yùn)行情況，來說明各種算法的工作過程及性能比較。假定該程序有 5頁信息塊，Cache空間為 3頁，該程序的頁地址流為： 3種算法工作過程和命中情況 ， 如圖所示 。 時間 ti t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 t11 t12 使用頁 Pi P2 P3 P2 P1 P5 P2 P4 P5 P3 P2 P5 P2 命中率： 25% 命中率： % 命中率： 50% ４． Cache— 主存內(nèi)容的一致性問題 CPU執(zhí)行寫操作時，要寫的內(nèi)容恰在 Cache中，則Cache內(nèi)容被更改，但該單元對應(yīng)的主存內(nèi)容尚沒有改變，這就產(chǎn)生了 Cache和主存內(nèi)容不一致的情況。 解決問題的關(guān)鍵是選擇更新主存內(nèi)容的算法； 采用兩種算法。 處理機(jī)進(jìn)行寫操作時，利用 ? Cache— 主存 ? 層次中存在于處理機(jī)和主存之間的通路將信息也寫回主存。 寫直達(dá)法又稱存直達(dá)法， 在頁替換時，就不必將被替換的 Cache頁內(nèi)容寫回，可以直接調(diào)入新頁。 ‘ 寫回法 ’ （ Write back） 處理機(jī)執(zhí)行寫操作時，信息只寫入 Cache，當(dāng) Cache頁被替換時，將該頁內(nèi)容寫回主存后，再調(diào)入新頁。 ? 寫直達(dá)則在每次寫入時，都要附加一個比寫 Cache長得多的寫主存時間；寫直達(dá)法的開銷大一些，但其一致性保持要好一些。 ◆ 采用兩種算法比較 ? 寫回法的開銷是在 頁替換時的回寫時間 ； 主存地址空間 4GB被分成 217頁，頁的大小為 8K字（ 32位） Cache (有數(shù)據(jù) SRAM和目錄 SRAM兩塊組成 ): 數(shù)據(jù) SRAM： 8K字（ 32位），可分成 1024個段，每段 8個字，每個字為一行。 目錄 SRAM： 存放目錄表，對應(yīng)數(shù)據(jù) SRAM的每一段的一個條目，由標(biāo)記位 （ 17位，指主存的頁面號，是 217頁中的一個頁號）、標(biāo)記有 效位（ 1位）和行有效位（ 8位）組成。 地址總線分成三部分： 17位標(biāo)記位（ A31— A15）， 10位段地址字段（ A14— A5） 3位行選擇位（ A4— A2）， 總線的低 13位（ A14— A2）還作為 Cache地址，直接選中數(shù)據(jù)SRAM中 8K字中的一行。 組間直接映象： 主存中各頁中第 0段只能對應(yīng)數(shù)據(jù) SRAM中第 0段 ? 。 組內(nèi)頁面全相聯(lián)： 每段 8行中可采用全相聯(lián)，用 8位行有效位和一位標(biāo)記有效位標(biāo) 注。 多體交叉存儲器 出發(fā)點(diǎn)： 能夠?qū)崿F(xiàn)同時從存儲器取出 n條指令 特點(diǎn) ：通過改進(jìn)主存的組織方式，在不改變存儲器存取周期的情況下，提高存儲器的帶寬。 結(jié)構(gòu)特點(diǎn) ：多體交叉存儲器由 M個的存儲體 （或稱存儲模塊）組成，每個存儲體有相同的容量和存取速度，又 有各自獨(dú)立的地址寄存器、地址譯碼器、讀寫電路和驅(qū)動電路 。 每個模塊各自以等同的方式與 CPU傳送信息。 CPU同時訪問四個模塊，由存儲器控制部件控制它們分時使用數(shù)據(jù)總線進(jìn)行信息傳遞。這是一種 并行存儲器結(jié)構(gòu) 。 ? 編址方法 ： 交叉編址 ，即 任何兩個相鄰地址的物理單元不屬于同一個存儲體 ，一般在相鄰的存儲體中；同一個存儲體內(nèi)的地址都是不連續(xù)的。 ? 主要有兩種： – 順序方式 – 地址交叉法 ? 某個模塊進(jìn)行存取時，其他模塊不工作；某一模塊出現(xiàn)故障時，其他模塊可以照常工作；通過增添模塊來擴(kuò)充存儲器容量比較方便。 ? 但各模塊串行工作，存儲器的帶寬受到了限制。 順序方式： ? 地址碼的低位字段經(jīng)過譯碼選擇不同的模塊，而高位字段指向相應(yīng)模塊內(nèi)的存儲字。 ? 連續(xù)地址分布在相鄰的不同模塊內(nèi)，同一個模塊內(nèi)的地址都是不連續(xù)的。 交叉方式： ? 對連續(xù)字的成塊傳送可實(shí)現(xiàn)多模塊流水式并行存取，大大提高存儲器的帶寬。 高 n 2 位042n 4152n 3262n 2372n 1低 2 位存 儲 器 地 址n 位............譯 碼 器M A R0M A R3M A R2M A R1M D R0M D R3M D R2M D R1數(shù) 據(jù) 總 線多體交叉存儲器 ? 訪問： CPU同時送出的 M個地址，只要他們分屬于 M個存儲體，訪問就不會沖突；由存儲器控制部件控制它們分時使用數(shù)據(jù)總線進(jìn)行信息傳遞。 ? 適合采用流水線 方式并行存取，雖然 每個存儲體的存儲周期沒變 ，但是當(dāng) CPU連續(xù)訪問一個字塊時，可以 大大提高存儲器的帶寬 。 512K 8位 偶地址 存儲體 512K 8位 奇地址 存儲體 FFFFFH 00005Ｈ 00003Ｈ 00001Ｈ ` FFFFEH 00004Ｈ 00002Ｈ 00000Ｈ ` 15 8 7 0 8086存儲器交叉編址結(jié)構(gòu)示意圖 例： 例 1:有一個具有 8個存儲體的低位多體交叉存儲器中 , 如果處理器的訪存地址為以下八進(jìn)制值 ,問該存儲 器比單體存儲器的平均訪問速度提高多少 ? (忽略初啟時的延遲 ) (1)1001 1002 1003 11008 (2) 1002 1004 1006 12022 (3) 1003 1006 1011 13008 8 , 4 , 8 例 2:設(shè)存儲器容量為 32字，字長 64位，模塊數(shù) m=4，分別用順序方式和交叉方式進(jìn)行組織。存儲周期 T=200ns，數(shù)據(jù)總線寬度為 64位，總線傳送周期 τ=50ns 。問順序存儲器和交叉存儲器的帶寬各是多少 ? 【