【正文】 ?則一塊包含 4個字，故需要 2位表示選擇一塊內(nèi)的哪個字，而一個字 32位又包含 4個字節(jié)，故用 2位表示一個 32位字中的哪個字節(jié)。Cache的數(shù)據(jù)區(qū)容量為 64KB，主存地址為 32位，按字節(jié)編址，數(shù)據(jù)字長 32位。 與存放順序一致，故 空間局部性好 ！ 但每個 A[i][j]只被訪問一次，故 時間局部性差 ！ (2)變量 sum：單個變量不考慮空間局部性； 每次循環(huán)都要訪問 sum，所以其時間局部性較好！ (3)for循環(huán)體：循環(huán)體內(nèi)指令按序連續(xù)存放，所以空間局部性好！ 循環(huán)體被連續(xù)重復執(zhí)行 2048x2048次，所以時間局部性好！ 程序段 B的時間局部性和空間局部性分析 (1)變量 sum：（同程序 A ） (2)for循環(huán)體：（同程序 A） (3)數(shù)組 A：訪問順序為 A[0][0] ~A[2047][0]。 1) 主存和 Cache的地址格式及其每部分的長度如下： 主存組號 組內(nèi)塊號 塊內(nèi)字號 2 1 3 主存地址格式 Cache組號 組內(nèi)行號 塊內(nèi)字號 1 1 3 Cache地址格式 2)Cache與主存之間的對應(yīng)關(guān)系如下圖所示 主存塊號及二進制值 0 1 2 3 4 5 6 7 00 0 00 1 01 0 01 1 10 0 10 1 11 0 11 1 Cache 組號 1 0 30 B3 60 B6 10 B1 ? 50 1 70 0 61 60 20 1 40 00 40 0 B7 B5 B4 B0 B6 B6 B4 B2 C0 C1 3)利用 FLU算法進行替換算法的映射全過程 命中率 = 1/11 例 。 (2)情況 2 ?解決問題的方法 當外設(shè)修改主存單元內(nèi)容時，將Ｃ ache對應(yīng)位置的有效標致位置無效即可． 主存 cache CPU1 X X’ 或 X (3)情況 3 CPU2 X’ …….. 習題課 直接 組相聯(lián) 例 1 采用組相聯(lián)映射方式的 Cache中，主存由 B0~ B7共 8塊組成，Cache有 2組，每組 2塊，每塊的大小為 8B，采用 LFU替換算法，在程序執(zhí)行過程中，依次訪問主存地址的塊流為 B B B B BB B0、 B B B B3。 (b)寫回法 (WB Write Back): CPU寫 Cache命中時，數(shù)據(jù)只寫向 Cache，不寫主存，同時修改 Cache中數(shù)據(jù)的臟位或修改位，供其它讀內(nèi)存的設(shè)備參考。 ? Cache有效位 (Valid bit) 用來表示是否有不經(jīng)過 Cache的主存數(shù)據(jù)更新 (如 DMA操作 ),當有這種主存數(shù)據(jù)更新時 ,有效位修改成 0,表示主存的數(shù)據(jù)被更新 ,而Cache中的數(shù)據(jù)無效 . 8) CACHE的一致性問題 b)Cache的結(jié)構(gòu) Tag Data Valid(1) Dirty(1) ?問題的提出： 正常情況下 , Cache是主存的副本，但經(jīng)過一段時間后，可 能會出現(xiàn)兩者內(nèi)容不一致的情況，導致這種不一致的情況有： CPU將 Cache某單元的內(nèi)容修改 成了 X’，而主存相關(guān)單元的內(nèi)容 還是 X，當外設(shè)讀取 X對應(yīng)單元的 數(shù)值時，就會發(fā)生不一致錯誤。 1 1 2 3 2 3 4 5 ?LRU舉例 10 11 20 12 21 30 13 20 31 14 21 30 15 22 31 40 50 23 32 41 10 ?如果出現(xiàn)了下列情況 (LRU) 11 20 10 21 30 12 11 10 22 31 13 40 23 32 50 41 10 33 51 42 11 20 52 43 12 21 53 30 1 2 3 4 5 1 2 3 ?上述現(xiàn)象稱為抖動，出現(xiàn)的原因是用戶的程序足局性不好 在這種情況下， Cache的作用得不到發(fā)揮。 ?舉例 1 1 2 3 2 3 4 5 21 11 11 20 11 20 30 11 21 30 11 21 31 11 31 40 11 21 31 50 10 ?缺點： 對新鮮數(shù)據(jù)保護不夠 (2)LRU 最近最少用算法 (Least recently used ) 該算法將一段時間內(nèi)最長時間沒有被使用的行調(diào)出。 ?若 CPU要訪問的地址為： 00001 11 0 11 則不命中 ?組相聯(lián)映射的特點： 前兩者的優(yōu)點 5）映射方式的地址抽象 主存地址 塊地址 塊內(nèi)偏移 Tag Index 塊內(nèi)偏移 Tag=主存塊號，無 Index 全 Tag=主存區(qū)號，區(qū)內(nèi)組，組內(nèi)塊 Index=Cache組號 Tag=主存區(qū)號 ,Index =Cache行 直 Tag=主存組號， Index=Cache組號 組 Tag Index作用？ ?飯碗？ ?現(xiàn)實生活中的 Cache ! ?使用飯碗可以解決什么問題？ 6）替換算法 (1)LFU算法 最不經(jīng)常使用算法 (Least Frequently Used ) 該算法將一段時間內(nèi)使用次數(shù)最少的行調(diào)出。 ? 映射時，主存區(qū)號、區(qū)內(nèi)組號和組內(nèi)塊號被填寫到 Cache特定組 的 任意行 的標記中，內(nèi)容存放到 Cache相同組號任一存儲體行中。 ?以 Cache的 行數(shù) 為基準對主存分區(qū)，區(qū)內(nèi)組的分布同Cache的組分布。 ?舉例： 設(shè)每塊 4個字，則主存的大小為 1024個字，其中第 61個字的主存地址為： 000011 11 01 (主存 3組中第 3塊、 即 B15塊中 ) 則將 000011填入 Cache的第 3組某行的標記部分，該塊的 4個字填入該行的 Cache存儲體 又如第 93個字的主存地址為 : 000101 11 01 也將分配到 Cache第 3組某行 ?組相聯(lián)映射的檢索 ?舉例： CPU要讀內(nèi)存地址為： 000011 11 11 則將前 6位 000011與 Cache的 第 3組中所有行標記的內(nèi)容送入比較器，若命中，選擇Cache第 3組中命中行內(nèi)的第 3個字。 ?直接映射的特點： 優(yōu)點： 硬件簡單、控制容易 缺點： 沖突率高，頁面調(diào)度頻繁，容易產(chǎn)生抖動 ?適用場合： 適用于大容量 Cache的場合，當 Cache的行增加后，與 Cache的同一行相對的主存的塊數(shù)就相對減少，從而減少 了沖突率 3）組相聯(lián)映射 1 ?主存分塊； Cache分行，兩者容量相同。 ? 若 CPU讀內(nèi)存地址： 00010 111 01 它是第 93個字， B23塊。 缺點： 比較電路相對復雜 ?使用場合： 適合小容量的 Cache中使用 2)直接映射 ?主存按 Cache容量 分區(qū)，區(qū)內(nèi)分塊；Cache分行，主存塊的容量和 Cache行的容量相同 ?對于如圖所示的情況 ,分區(qū)數(shù)為 32 ?算法： i =j mod 8 (i 是 Cache行號， j是 主存 塊號 )是一種多對一的映射 ?映射時，數(shù)據(jù)所在 主存區(qū)號 被填寫到 Cache某行的 標記 部分，內(nèi)容存放到 Cache相應(yīng)行的存儲體中。 ?舉例： 設(shè)每塊 4個字，則主存的大小為1024個字，其中第 61個字的主存地址為： 00001111 01 （塊號 塊內(nèi)地址） 則將 00001111填入 Cache某行 的標記，該塊的 4個字填入該行的 Cache存儲體 內(nèi)存 ?檢索過程 ?舉例： CPU要讀內(nèi)存地址為： 00001111 10 則將前 8位 00001111送入比較器，同時 Cache的所有行的標記字段也同時送入該比較器，如果某行命中，則選通內(nèi)存地址的剩余部分，并由它選擇 Cache中相應(yīng)字，本例中選擇該塊內(nèi)的第 2個字。 ?地址映射的實現(xiàn)： 硬件實現(xiàn)，對軟件人員 (包括程序員和系統(tǒng)程序員 ) 透明 ?三種地址映射方法： 全相聯(lián)、直接相聯(lián)、組相聯(lián) 1)全相聯(lián)映射方式 ?主存分塊， Cache分行，兩者的容量相同，即包含相同數(shù)量的字 ?圖中主存被分成 256塊， Cache被分成8行。 ? Cache的一個塊包含若干個字。 4) 交叉方式 交叉方式的特點 : ?相鄰地址分布在不同存儲體中 ?同一存儲體中的地址不相鄰 ?實現(xiàn)方法： 字擴展時，用低位地址作為多余地址送入片選譯碼輸入 ?四片的地址通項公式分別為 : 4i +0 、 4i+ 4i + 4i+3 ?能在一個存儲周期內(nèi)存取多個字 5)相聯(lián)存儲器 (1) 什么是相聯(lián)存儲器 按內(nèi)容訪問的存儲器。 ? 是一種并行存儲器結(jié)構(gòu) 2)多體交叉存儲器的定量分析 設(shè)模塊存取周期為 T ，總線傳送周期為 ? ，交叉模塊數(shù)為 m , 實現(xiàn)流水線方式存取，必須滿足的條件是： T = m ? 即每個模塊啟動后經(jīng)過 ? 時間的延時，就可以啟動下一個模塊。 1 五、高速存儲器 問題的提出 (1)CPU和主存速度上存在差異 (2)一個 CPU周期內(nèi)需要多個存儲字 60%/yr. DRAM 7%/yr. 1 10 100 1000 1980 1981 1983 1984 1985 1986 1987 1988 1989 1990 1991 1992 1993 1994 1995 1996 1997 1998 1999 2022 DRAM CPU 1982 ProcessorMemory Performance Gap: (grows 50% / year) Performance “Moore’s Law” 幾種解決問題的方法 (1)主存采用更高速的材料，縮短讀寫時間；或增加存儲器字長 (2)采用并行操作的雙端口存儲器 (3)在 CPU和主存間插入高速緩沖存儲器 (Cache) (4)在每個存儲周期中存取幾個字 雙端口存儲器 構(gòu)造及工作原理： ? 具有相互獨立的兩組讀 /寫控制電路 , 正常情況下各自獨立進行讀 /寫 ?左右讀 /寫不同單元時不發(fā)生沖突 ?左右同時存取同一個單元時 ,發(fā)生讀寫沖突 .此時 ,由判斷邏輯來延時一個讀寫控制器的工作并設(shè)該端口 . BUSY=0. 多體交叉存儲器 1)多體交叉存儲器的工作原理 結(jié)構(gòu)分析及工作原理 : ?增加了存儲器控制部件 ? 總線寬度不變 ? 四個存儲器的容量相同 ,各有自己的讀 \寫線路、地址寄存器、數(shù)據(jù)寄存器。 解：先畫出主存地址空間分布圖和分析移碼器的處理 8K(EPROM) 24K(SRAM) 30K(空 ) 2K(SRAM) 選用的芯片 : ?EPROM : 8Kx8 1片 ?SRAM :