【正文】 聯(lián) 命中時間小 命中時間大 不命中率高 不命中率低 “ 偽相聯(lián) ” 又稱 “ 列相聯(lián) ” ，按原理還可稱為 “ 伴生 Cache‖。 (1) 比較直接相聯(lián)、組相聯(lián)的優(yōu)缺點 從例 ，直接相聯(lián)的命中時間較短，而多路組相聯(lián)的失效率較低，所以它們的平均訪問時間依兩個因素的作用大小而互有輸贏。有沒有什么方法取二者之長呢？ (2) 偽相聯(lián)的優(yōu)點 偽相聯(lián)就是直接相聯(lián)、組相聯(lián)的一種組合方案。優(yōu)點是命中時間短、 不命中 率還低，所以它的平均訪問時間往往比直接相聯(lián)、組相聯(lián)都短 。 計算機系統(tǒng)結構 46 (3) 基本思想及工作原理 在邏輯上把直接 相聯(lián) Cache的空間分為上、下兩個區(qū)。對于任何一次訪問，偽相聯(lián) Cache先按直接 相聯(lián) Cache的方式去處理。若命中，則其訪問過程與直接 相聯(lián) Cache的情況一樣。若不命中，則再到另一區(qū)相應的位置去查找。若找到，則發(fā)生了偽命中。再找不到就只好訪問下一級存儲器。 顯然偽 相聯(lián)的 “ 候選位置 ” =2， 與 2路組相聯(lián)相同。 每次訪問時間有 3種可能： ? 正常命中（快速命中） ? 偽命中（慢速命中） ? 不命中 偽相聯(lián)（續(xù) 1） 索引 至 CPU 取出數(shù)據(jù)送往 CPU 偽相聯(lián)組 … … 計算機系統(tǒng)結構 47 (4) 快速命中與慢速命中 要保證絕大多數(shù)命中都是快速命中，就是命中率要高。一種簡單的辦法是在出現(xiàn)偽命中時，交換上下兩個區(qū)的內容，因為當前在下區(qū)的塊很可能是“常用塊”。偽命中情況下 需要增加 2個額外的 時鐘 周期（其中 1個周期是多找 1次花去的， 1個周期是交換操作所需）。 (5) 偽相聯(lián)的缺點： 它的多種命中時間使得 CPU流水線上各指令之間的時間對齊變得困難，所以往往應用在離 CPU比較遠的 Cache上，比如 L2Cache。 偽相聯(lián)（續(xù) 2） 計算機系統(tǒng)結構 48 偽相聯(lián)（續(xù) 3） 折中方案：偽相聯(lián)（ 2路） ， 目錄表法（ P209） P 位 S 位 虛地址 虛塊號 偏移 標識段 索引段 （ p 1 位 ） p 位 最高位 實地址 先補 0 常通方向 實存 目錄表 1 塊 =2S 標識 0 實塊號 0 標志位 裝入？ ∶ 先比較 正常命中？ ∶ 后比較 偽命中？ 標識 1 實塊號 1 標志位 裝入？ ∶ 行數(shù) =2P 行數(shù) = 塊數(shù) 8b 塊數(shù) =2p 正常命中： 偽命中（增加 2 拍）： AF IF ID EX ME WB AF IF ID EX ME WB AF IF ID EX ME WB AF IF ID EX ME WB AF IF ID EX ME WB AF IF ID EX ME WB 計算機系統(tǒng)結構 49 例 （補充， 2版 P198例 ） 一個偽相聯(lián) Cache，當在按直接映象找到的位置處沒有發(fā)現(xiàn)匹配、而在另一個位置才找到數(shù)據(jù)（偽命中）時需要增加 2個額外的周期。其它已知條件如下表所示。 (1) 推導偽相聯(lián)平均訪存時間公式； (2) 當 Cache容量分別為 2KB和 128KB時，直接映象、兩路組相聯(lián)和偽相聯(lián)這三種組織結構中，哪一種 的平均訪存時間最短 ？ 偽相聯(lián)（續(xù) 4） 命中周期數(shù) 不命中率 2KB 不命中率 128KB 不命中 開銷 1 路 Ca che 1. 0 9. 8% 1. 0% 50 2 路 Ca che 1. 1 7. 6% 0. 7% 50 計算機系統(tǒng)結構 50 解： (1) 首先按通用形式寫出偽相聯(lián)的平均訪存時間公式： 平均訪存時間 偽相聯(lián) ＝平均命中時間 偽相聯(lián) ＋不命中率 偽相聯(lián) 不命中開銷 偽相聯(lián) 然后根據(jù)偽相聯(lián)原理，可以寫出其中的： 平均命中時間 偽相聯(lián) ＝命中時間 1路 ＋偽命中率 偽相聯(lián) 2周期 由于偽相聯(lián)不命中時，就是 2個候選位置都不命中，所以： 不命中率 偽相聯(lián) ＝不命中率 2路 又由于偽相聯(lián)的 2個候選位置命中率之和等于 2路組相聯(lián)，所以： 偽命中率 偽相聯(lián) ＝命中率 2路 －命中率 1路 ＝ (1－不命中率 2路 )－ (1－不命中率 1路 ) ＝不命中率 1路 －不命中率 2路 偽相聯(lián)（續(xù) 5） 計算機系統(tǒng)結構 51 將后 3式依次向前代入，得到所需公式： 平均訪存時間 偽相聯(lián) ＝命中時間 1路 ＋ (不命中率 1路 －不命中率 2路 ) 2周期 ＋不命中率 2路 不命中開銷 1路 (2) 當 Cache容量為 2KB時： 平均訪存時間 1路 ＝ ＋ 50＝ 平均訪存時間 2路 ＝ ＋ 50＝ 平均訪存時間 偽相聯(lián)， 2KB ＝ ＋ (－ ) 2＋ ( 50)＝ 當 Cache容量為 128KB時： 平均訪存時間 1路 ＝ ＋ 50＝ 平均訪存時間 2路 ＝ ＋ 50＝ 平均訪存時間 偽相聯(lián)， 128KB＝ ＋ (－ ) 2＋ ( 50)＝ 可見，對于這兩種 Cache容量，偽相聯(lián) Cache都是速度最快的。 偽相聯(lián)（續(xù) 6） 計算機系統(tǒng)結構 52 結論： ? 從 不命中 率看， F2路 = F偽相聯(lián) F1路 ，偽相聯(lián)因不命中帶來的平均延時與 2路一樣短（ 1路較長）； ? 從命中時間看，偽相聯(lián)在正常命中時與 1路一樣短（ 2路較長），偽命中時要增加 2拍，后者概率 = H2路 – H1路 。這種情況下 1路要增加 50拍。 ? 代入 2KB、 128KB容量的數(shù)據(jù)，算出平均訪存時間 TA都是偽相聯(lián)最短。 缺點：多種命中時間 習題： 偽相聯(lián)（續(xù) 7） 計算機系統(tǒng)結構 53 各次作業(yè)應交的內容 作業(yè) 9（第 10次課） 2 月 19 日 1. 10 ( 改 ) ， 1. 7 ， 1. 1 1( 2 解法 ) 4 月 9 日 7. 14 ( 難題 ) ， 7. 12 ( 難題 ) 2 月 26 日 2. 14 ( 補充 ) ，實驗 1 ， 3. 8 ， 3. 10 4 月 16 日 8. 12 ( 補 ) ， 8. 1 1( 改 ) ( 難題 ) 3 月 5 日 3. 1 1( 改 ) ，實驗 2 ， 5. 1 1 ， 5. 8 ， 5. 9 4 月 23 日 9. 9( 改 ) ， 9. 13 3 月 12 日 6. 8( 改 ) ， 6. 7 ， 7. 9 4 月 30 日 10 .6 ， 10 .9 ( 難題 ) 4 月 2 日 7. 1 1 ， 7. 10 計算機系統(tǒng)結構 54 衡量訪存時間是否合適的主要標準是處理機速度 ， 具體說是處理機分配來讀 /寫存儲器的時間長短 。 處理機速度越高要求訪存時間越短 。 衡量處理機速度的常用標準是 CPI， 因為它與程序執(zhí)行時間成正比 。 對順序執(zhí)行的處理機 ， CPI定義為每條指令執(zhí)行所需的平均周期數(shù) 。對流水執(zhí)行的處理機 ， CPI定義為相鄰兩條指令啟動時間相差的平均周期數(shù) 。 我們現(xiàn)在只關心流水處理機 。 下圖說明訪存等待 （ 不命中 ） 會延長 瞬時 CPI。 訪存時間對 CPU性能的影響 1（ P203） C Y C L EC P IICC P U ??? 實際時間IF ID EX Mem WB stall IF ID EX Mem WB IF ID EX Mem WB IF ID EX Mem WB IF ID EX Mem WB CPI=1 CPI=2 計算機系統(tǒng)結構 55 所以 在計算 平均 CPI時 ， 應該加上存儲器平均 “ 不命中開銷 ” 。 本章僅考慮存儲器等待在平均 CPI計算中的作用 ， 暫時不考慮流水線因相關 、 沖突導致的延遲 ， 所以上式簡化寫為 又被稱為 以下是計算二者關系的幾組常用公式 。 訪存時間對 CPU性能的影響 2 存儲器平均不命中開銷延遲流水線自身產生的平均每條指令平均延遲理想理想平均?????C P IC P IC P I銷每條指令平均不命中開理想平均 ?? C P IC P I平均CPI 實際CPI 計算機系統(tǒng)結構 56 (1) 第 i級的不命中率： 特殊地 ， F1又可以記為 F， 因為 M1被訪問次數(shù)就是 CPU的總訪存次數(shù) 。 (2) 存儲系統(tǒng)的平均訪問時間 （ 從 CPU看 ） ： 其中 H1～ Hn是來自互斥事件的完備群 ， 它們滿足關系式： 注意該公式忽略了各級之間的傳送時間 。 (3) 第 i級的平均訪問時間： 其中 Ti是第 i級的命中時間 ， TMi是第 i級的失效開銷時間 。 訪存時間對 CPU性能的影響 3 次數(shù)訪問次數(shù)不命中iiii MMHF ??? 1??? ni iiA HTT 111???ni iHMiiiiA TFTT ??? 計算機系統(tǒng)結構 57 (4) 程序執(zhí)行時間 （ 即 “ CPU時間 ” ） ： a. b. c. d. () e. () f. () g. 訪存時間對 CPU性能的影響 4 C Y C L EC P IICT e ??? 實際? ? C Y C L EFC P IICT e ?????? 平均不命中開銷每條指令平均訪存次數(shù) 平均理想? ? C Y C L EC P IICT e ???? 數(shù)每條指令平均等待周期理想? ? C Y C L EC P UT e ??? 等待存儲器周期數(shù)實際執(zhí)行周期數(shù)? ? C Y C L EC P IICT e ????? 平均不命中開銷數(shù)每條指令平均不命中次理想平均不命中開銷周期數(shù)訪存次數(shù)等待存儲器周期數(shù) 平均 ??? F寫不命中開銷周期數(shù)“寫”次數(shù)讀不命中開銷周期數(shù)“讀”次數(shù)等待存儲器周期數(shù)寫讀 ???????FF 計算機系統(tǒng)結構 58 例 （ P204） 假設 Cache不命中開銷為 50個時鐘周期，當不考慮存儲器停頓時，所有指令的執(zhí)行時間都是 ，訪問 Cache不命中率為 2%，平均每條指令訪存 。 比較有 Cache與無 Cache情況下的 CPU時間。 解： 已知 TA1=， 即理想 CPI = ， TA2=50， F=2%， 平均每條指令訪存 CPU時間 有 cache＝ IC （ CPIexecution＋ 每條指令的平均訪存次數(shù) 不命中率不命中開銷） 時鐘周期時間 ＝ IC （ ＋ 2 % 50） 時鐘周期時間 ＝ IC 時鐘周期時間 從此式知，實際 CPI＝ ＋ 2 % 50＝ ， 是理想情況下的 ＝ (倍 )，換言之， CPU時間是理想情況下的 。 若不采用 Cache， 則每次訪存增加 50個時鐘周期，每條指令的周期數(shù)為： CPI無 cache＝ ＋ 50＝ ， 是理想情況下的 ＝ ！ 計算機系統(tǒng)結構 59 例 （ P204） 考慮兩種不同組織結構的 Cache： 直接映象 Cache和兩路組相聯(lián) Cache， (1)理想 Cache（ 命中率為 100%）情況下的 CPI為 ，時鐘周期為 2ns， 平均每條指令訪存 ； (2)兩種 Cache容量均為 64KB， 塊大小都是 32B； (3)在組相聯(lián) Cache中， 由于多路選擇器的存在而使 CPU的時鐘周期增加到原來的 。這是因為對 Cache的訪問總是處于關鍵路徑上，對 CPU的時鐘周期有直接的影響； (4)這兩種結構 Cache的不命中開銷都是 70ns（ 在實際應用中，應取整為整數(shù)個時鐘周期）； (5)命中時間為 1個時鐘周期， 64KB直接映象 Cache的不命中率為 %，相同容量的兩路組相聯(lián) Cache的不命中率為 %。 分別比較它們的平均訪存時間、 CPU時間。 計算機系統(tǒng)結構 60 例 （續(xù)