并行計(jì)算機(jī)體系結(jié)構(gòu)第五章.ppt

第五章 并行存儲(chǔ)系統(tǒng)和同步機(jī)制,并行存儲(chǔ)系統(tǒng)和同步機(jī)制,計(jì)算機(jī)邏輯器件速度大幅提高，致使系統(tǒng)與存儲(chǔ)機(jī)制之間的速度差距日益增大，存儲(chǔ)系統(tǒng)已經(jīng)成為計(jì)算機(jī)系統(tǒng)的速度瓶頸。 多體并行、多體交叉 寬字訪問(wèn)和順序交叉訪問(wèn) 存儲(chǔ)器層次結(jié)構(gòu),層次存儲(chǔ)系統(tǒng),層次存儲(chǔ)系統(tǒng),在一般計(jì)算機(jī)系統(tǒng)中，有兩種存儲(chǔ)系統(tǒng)： Cache存儲(chǔ)系統(tǒng)：由Cache和主存儲(chǔ)器構(gòu)成 主要目的：提高存儲(chǔ)器速度,解決主存速度不足,虛擬存儲(chǔ)系統(tǒng)：由主存儲(chǔ)器和硬盤構(gòu)成 主要目的：擴(kuò)大存儲(chǔ)器容量,解決主存容量不足,存儲(chǔ)系統(tǒng)的容量 要求： 提供盡可能大的地址空間 能夠隨機(jī)訪問(wèn) 方法有兩種： 只對(duì)系統(tǒng)中存儲(chǔ)容量最大的那個(gè)存儲(chǔ)器進(jìn)行編址，其他存儲(chǔ)器只在內(nèi)部編址或不編址 Cache存儲(chǔ)系統(tǒng) 另外設(shè)計(jì)一個(gè)容量很大的邏輯地址空間，把相關(guān)存儲(chǔ)器都映射這個(gè)地址空間中 虛擬存儲(chǔ)系統(tǒng),存儲(chǔ)系統(tǒng)的價(jià)格 計(jì)算公式： 當(dāng)S2S1時(shí)，CC2 S2與S1不能相差太大,存儲(chǔ)系統(tǒng)的速度 表示方法：訪問(wèn)周期、存取周期、存儲(chǔ)周期、存取時(shí)間等 命中率定義：在M1存儲(chǔ)器中訪問(wèn)到的概率 其中：N1是對(duì)M1存儲(chǔ)器的訪問(wèn)次數(shù) N2是對(duì)M2存儲(chǔ)器的訪問(wèn)次數(shù) 訪問(wèn)周期與命中率的關(guān)系： THT1(1H)T2 當(dāng)命中率H1時(shí)，TT1,存儲(chǔ)系統(tǒng)的訪問(wèn)效率： 訪問(wèn)效率主要與命中率和兩級(jí)存儲(chǔ)器的速度之比有關(guān) 例3.1：假設(shè)T2T，在命中率H為0.9和0.99兩種情況下，分別計(jì)算存儲(chǔ)系統(tǒng)的訪問(wèn)效率。 解：,當(dāng)H0.9時(shí)， e11(0.95(10.9)0.72,當(dāng)H0.99時(shí)， e21(0.995(10.99)0.96,提高存儲(chǔ)系統(tǒng)速度的兩條途徑： 一是提高命中率H， 二是兩個(gè)存儲(chǔ)器的速度不要相差太大 其中：第二條有時(shí)做不到(如虛擬存儲(chǔ)器)，這時(shí)，只能依靠提高命中率 例3.2：在虛擬存儲(chǔ)系統(tǒng)中，兩個(gè)存儲(chǔ)器的速度相差特別懸殊，例如：T2105 T。如果要使訪問(wèn)效率到達(dá)e0.9，問(wèn)需要有多高的命中率？,解：,0.9H90000(1-H)1 89999.1 H89999 計(jì)算得： H0.999998888877777 0.999999,5. 采用預(yù)取技術(shù)提高命中率 方法：不命中時(shí)，把M2存儲(chǔ)器中相鄰多個(gè)單元組成的一個(gè)數(shù)據(jù)塊取出來(lái)送入M1存儲(chǔ)器中。,計(jì)算公式： 其中：H是采用預(yù)取技術(shù)之后的命中率 H是原來(lái)的命中率 n為數(shù)據(jù)塊大小與數(shù)據(jù)重復(fù)使用次數(shù)的乘積,例3.3：在一個(gè)Cache存儲(chǔ)系統(tǒng)中，當(dāng)Cache的塊大小為一個(gè)字時(shí)，命中率H0.8；假設(shè)數(shù)據(jù)的重復(fù)利用率為5，T25T1。計(jì)算塊大小為個(gè)字時(shí)，Cache存儲(chǔ)系統(tǒng)的命中率？并分別計(jì)算訪問(wèn)效率。,解：n4520， 采用預(yù)取技術(shù)之后，命中率提高到：,證明方法一： 采用預(yù)取技術(shù)之后， 不命中率(1-H)降低倍：,證明方法二： 在原有命中率的計(jì)算公式中，把訪問(wèn)次數(shù)擴(kuò)大到n倍。由于采用了預(yù)取技術(shù)，命中次數(shù)為：nN1(n-1)N2,不命中次數(shù)仍為N2，因此新的命中率為：,存儲(chǔ)系統(tǒng)的層次結(jié)構(gòu),多個(gè)層次的存儲(chǔ)器： 第1層：Register Files(寄存器堆) 第2層： Buffers(Lookahead)(先行緩沖棧) 第3層： Cache(高速緩沖存儲(chǔ)器) 第4層： Main Memory(主存儲(chǔ)器) 第5層： Online Storage(聯(lián)機(jī)存儲(chǔ)器) 第6層： Off-line Storage(脫機(jī)存儲(chǔ)器) 用i表示層數(shù)，則有：工作周期TiTi+1， 存儲(chǔ)容量：SiSi+1，單位價(jià)格：CiCi+1,存儲(chǔ)層次的四個(gè)問(wèn)題,1.當(dāng)把一個(gè)塊調(diào)入高一層(靠近CPU)存儲(chǔ)器時(shí)，可以放在哪些位置上? (映象規(guī)則),2.當(dāng)所要訪問(wèn)的塊在高一層存儲(chǔ)器中時(shí)，如何找到該塊? (查找算法),3. 當(dāng)發(fā)生失效時(shí)，應(yīng)替換哪一塊？ (替換算法),4. 當(dāng)進(jìn)行寫訪問(wèn)時(shí)，應(yīng)進(jìn)行哪些操作?(寫策略),多體并行,多套地址寄存器和控制邏輯 1. 高位交叉訪問(wèn)存儲(chǔ)器 主要目的：擴(kuò)大存儲(chǔ)器容量 實(shí)現(xiàn)方法：用地址碼的高位部分區(qū)分存儲(chǔ)體號(hào) 要求每個(gè)模塊都有各自獨(dú)立的控制部件，每個(gè)模塊均可獨(dú)立工作。但系統(tǒng)地址的連續(xù)空間落在同一存儲(chǔ)體內(nèi)，容易發(fā)生訪存沖突。并行存取的可能性很小。,交叉訪問(wèn)存儲(chǔ)器,高位交叉訪問(wèn)存儲(chǔ)器結(jié)構(gòu)框圖,例3.4：用4M字4位的存儲(chǔ)芯片組成16M32位的主存儲(chǔ)器。共用存儲(chǔ)芯片： 用最高2位地址經(jīng)譯碼后產(chǎn)生的信號(hào)，控制各組存儲(chǔ)芯片CS。 每組中的32根數(shù)據(jù)線分別對(duì)應(yīng)直接相連，稱為“線或”方式。,低位交叉訪問(wèn)存儲(chǔ)器 主要目的：提高存儲(chǔ)器訪問(wèn)速度 實(shí)現(xiàn)方法：用地址碼的低位部分區(qū)分存儲(chǔ)體號(hào) 要求每個(gè)模塊都有各自獨(dú)立的控制部件，每個(gè)模塊均可獨(dú)立工作。系統(tǒng)地址在一個(gè)存儲(chǔ)體內(nèi)部是不連續(xù)的，對(duì)連續(xù)地址的訪問(wèn)分布在不同的存儲(chǔ)體中，可避免存儲(chǔ)體訪問(wèn)沖突。 理想情況下，即一個(gè)模m的多體交叉訪問(wèn)存儲(chǔ)器在不發(fā)生分體沖突時(shí)的頻寬是單體存儲(chǔ)器頻寬的m倍。,低位交叉訪問(wèn)存儲(chǔ)器結(jié)構(gòu)框圖,地址編碼方法： 由8個(gè)存儲(chǔ)體構(gòu)成的低位交叉編址方式,n個(gè)存儲(chǔ)體分時(shí)啟動(dòng) 一種采用流水線方式工作的并行存儲(chǔ)器 每存儲(chǔ)體的啟動(dòng)間隔為：t 其中： Tm為每個(gè)存儲(chǔ)體的訪問(wèn)周期, n為存儲(chǔ)體個(gè)數(shù)。,訪問(wèn)沖突 共有n個(gè)存儲(chǔ)體，每個(gè)存儲(chǔ)周期只能取到k個(gè)有效字,其余n-k個(gè)存儲(chǔ)體有沖突。 假設(shè)p(k)是k的概率密度函數(shù)，即p(1)是k1的概率，p(2)是k2的概率，,p(n)是kn的概率。k的平均值為： N是每個(gè)存儲(chǔ)周期能夠訪問(wèn)到的平均有效字的個(gè)數(shù)。 通常把 N稱為并行存儲(chǔ)器的加速比。,定義轉(zhuǎn)移概率為g，即讀出的是轉(zhuǎn)移指令，且轉(zhuǎn)移成功的概率。這時(shí)有： p(1)g p(2)(1-p(1)g(1-g)g p(3)(1-p(1)-p(2)g(1-g)2g p(k)(1-g)k-1g (k1,2,n1) p(n)(1-g)n-1,則：1g2(1-g)g3(1-g)2g (n-1)(1-g)n-2gn(1-g)n-1,若g=0，n個(gè)存儲(chǔ)體的加速倍數(shù)達(dá)到最大值n。 若g=1, n個(gè)存儲(chǔ)體的加速倍數(shù)只有1，與單個(gè)存儲(chǔ)體完全一樣。,無(wú)沖突訪問(wèn)存儲(chǔ)器,1. 一維數(shù)組(向量)的無(wú)沖突訪問(wèn)存儲(chǔ)器 按連續(xù)地址訪問(wèn)，沒(méi)有沖突， 位移量為2的變址訪問(wèn)，速度降低一倍，,具體方法： 存儲(chǔ)體的個(gè)數(shù)取質(zhì)數(shù)。 原因：變址位移量必然與存儲(chǔ)體個(gè)數(shù)互質(zhì) 設(shè)地址間距為d=1,m體交叉存儲(chǔ)器的工作體數(shù)為m=m/(m,d)，其中(m,d)為m和d的最大公約數(shù)。當(dāng)m=T/時(shí)，必將引起流水線斷流，所以m取為質(zhì)數(shù)。,2. 二維數(shù)組的無(wú)沖突訪問(wèn)存儲(chǔ)器 要求：一個(gè)nn的二維數(shù)組，按行、列、對(duì)角線和反對(duì)角線訪問(wèn)，并且在不同的變址位移量情況下，都能實(shí)現(xiàn)無(wú)沖突訪問(wèn)。 順序存儲(chǔ)：按行、對(duì)角線訪問(wèn)沒(méi)有沖突，但按列訪問(wèn)每次沖突,錯(cuò)位存儲(chǔ)： 按行、按列訪問(wèn)無(wú)沖突， 但按對(duì)角線訪問(wèn)有沖突,nn二維數(shù)組無(wú)沖突訪問(wèn)存儲(chǔ)方案 ( P Budnik 和 D J Kuck提出 ) ： 并行存儲(chǔ)體的個(gè)數(shù)mn，并且取質(zhì)數(shù)，同時(shí)還要在行、列方向上錯(cuò)開一定的距離存儲(chǔ)數(shù)組元素。 設(shè)同一列相鄰元素在并行存儲(chǔ)器中錯(cuò)開d1個(gè)存儲(chǔ)體存放，同一行相鄰元素在并行存儲(chǔ)器中錯(cuò)開d2個(gè)存儲(chǔ)體存放。當(dāng)m22p1（p為任意自然數(shù)）時(shí)，能夠同時(shí)實(shí)現(xiàn)按行、按列、按對(duì)角線和按反對(duì)角線無(wú)沖突訪問(wèn)的充要條件是：d12P，d21。,例如：44的二維數(shù)組，取并行存儲(chǔ)體的個(gè)數(shù)m5，由關(guān)系式m22P1，解得到p1，計(jì)算得到： d1212 d21,37,nn數(shù)組中的任意一個(gè)元素aij在無(wú)沖突并行存儲(chǔ)器中的體號(hào)地址和體內(nèi)地址的計(jì)算公式： 體號(hào)地址：(2P ijk) MOD m 體內(nèi)地址：i 其中：0in1， 0jn1， k是數(shù)組的第一個(gè)元素a00所在體號(hào)地址，通常k=0 ， m是并行存儲(chǔ)體的個(gè)數(shù)，要求mn且為質(zhì)數(shù)， p是滿足m22P1關(guān)系的任意自然數(shù)。 主要缺點(diǎn)：浪費(fèi)存儲(chǔ)單元 對(duì)于nn數(shù)組,有1/(n+1)的存儲(chǔ)單元浪費(fèi) 主要優(yōu)點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單 行元素順序存儲(chǔ)，列元素按地址取模順序存儲(chǔ),3. 二維數(shù)組的無(wú)沖突訪問(wèn)存儲(chǔ)器(之二) 規(guī)則：對(duì)于任意一個(gè)nn的數(shù)組，如果能夠找到滿足n22P關(guān)系的任意自然數(shù)p，則這個(gè)二維數(shù)組就能夠使用n個(gè)并行存儲(chǔ)體實(shí)現(xiàn)按行、列、對(duì)角線和反對(duì)角線的無(wú)沖突訪問(wèn)。 44數(shù)組用4個(gè)存儲(chǔ)體的無(wú)訪問(wèn)沖突存儲(chǔ)方案,實(shí)現(xiàn)方法： 假設(shè)aij是44數(shù)組中的任意一個(gè)元素，下標(biāo)i和j都可以用兩位二進(jìn)制表示。假設(shè)i和j的高位和低位分別為iH、iL、jH和jL，則aij在無(wú)沖突并行存儲(chǔ)器中的體號(hào)地址和體內(nèi)地址如下： 體號(hào)地址：2(iL jH)(iH iL jL) 體內(nèi)地址：j 其中：0i3，0j3 主要優(yōu)點(diǎn)：沒(méi)有浪費(fèi)的存儲(chǔ)單元 主要缺點(diǎn)：在執(zhí)行并行讀和寫操作時(shí)需要借助比較復(fù)雜的對(duì)準(zhǔn)網(wǎng)絡(luò)。,Cache主存存儲(chǔ)系統(tǒng),存儲(chǔ)空間分割與地址計(jì)算,映象規(guī)則,全相聯(lián)映象 全相聯(lián)：主存中的任一塊可以被放置到 Cache中的任意一個(gè)位置。 對(duì)比： 閱覽室位置 隨便坐 特點(diǎn)： 空間利用率最高，沖突概率最低， 實(shí)現(xiàn)最復(fù)雜。,Cache和主存分塊,2. 直接映象, 直接映象：主存中的每一塊只能被放置到 Cache中唯一的一個(gè)位置。 對(duì)比：閱覽室位置 只有一個(gè)位置可以坐 特點(diǎn)：空間利用率最低，沖突概率最高，實(shí)現(xiàn)最簡(jiǎn)單。 對(duì)于主存的第i 塊，若它映象到Cache的第j 塊，則: ji mod (M ) （M為Cache的塊數(shù)）, 組相聯(lián)：主存中的每一塊可以被放置Cache中唯一的一個(gè)組中的任何一個(gè)位置。 組相聯(lián)是直接映象和全相聯(lián)的一種折衷, 設(shè)M2m，則當(dāng)表示為二進(jìn)制數(shù)時(shí)，j 實(shí)際 上就是i 的低m 位：,3. 組相聯(lián)映象,m位,j,i：,上述的j 和k 通常稱為索引,組的選擇常采用位選擇算法 若主存第i 塊映象到第k 組，則:ki mod（G） （G為Cache的組數(shù)）設(shè)G2g，則當(dāng)表示為二進(jìn)制數(shù)時(shí)，k 實(shí)際上就是i 的低 g 位：,g 位,k,i：, 絕大多數(shù)計(jì)算機(jī)的Cache: n 4 想一想：相聯(lián)度一定是越大越好？, n 路組相聯(lián)：每組中有n 個(gè)塊(nM/G )，n 稱為相聯(lián)度。相聯(lián)度越高，Cache空間的利用率就越高塊沖突概率就越低，失效率也就越低。,全相聯(lián),直接映象,組相聯(lián),n (路數(shù)),G (組數(shù)),M,M,1,1,1nM,1GM,查找方法,如何確定Cache中是否有所要訪問(wèn)的塊？ 若有的話如何確定其位置？,目錄表的結(jié)構(gòu), 只需查找候選位置所對(duì)應(yīng)的目錄表項(xiàng), 并行查找與順序查找, 提高性能的重要思想：主候選位置(MRU塊) 前瞻執(zhí)行, 并行查找的實(shí)現(xiàn)方法：,相聯(lián)存儲(chǔ)器 單體多字存儲(chǔ)器比較器,路組相聯(lián)Cache的查找過(guò)程, 直接映象Cache的查找過(guò)程,替換算法,所要解決的問(wèn)題：當(dāng)新調(diào)入一塊，而Cache 又已被占滿時(shí)，替換哪一塊？,1. 隨機(jī)法 優(yōu)點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單 2. FIFO 3. LRU 優(yōu)點(diǎn)：失效率低,寫策略,1. “寫”操作所占的比例 Load指令：26 Store指令：9 “寫”在所有訪存操作中所占的比例： 9/(100269)7 “寫”在訪問(wèn)Cache操作中所占的比例： 9/(269)25,3“寫”訪問(wèn)有可能導(dǎo)致Cache和主存內(nèi)容的不一致,2. “寫”操作必須在確認(rèn)是命中后才可進(jìn)行,兩種寫策略 寫直達(dá)法 執(zhí)行“寫”操作時(shí)，不僅寫入Cache，而且 也寫入下一級(jí)存儲(chǔ)器。 寫回法 執(zhí)行“寫”操作時(shí)，只寫入Cache。僅當(dāng) Cache中相應(yīng)的塊被替換時(shí)，才寫回主存。 (設(shè)置“污染位”),5兩種寫策略的比較 寫回法的優(yōu)點(diǎn)：速度快，所使用的存儲(chǔ)器頻 帶較低； 寫直達(dá)法的優(yōu)點(diǎn)：易于實(shí)現(xiàn)，一致性好。,6. 寫緩沖器,寫策略與調(diào)塊 寫回法 按寫分配 寫直達(dá)法 不按寫分配,“寫”操作時(shí)的調(diào)塊 按寫分配(寫時(shí)取) 寫失效時(shí)，先把所寫單元所在的塊調(diào)入 Cache，再行寫入。 不按寫分配(繞寫法) 寫失效時(shí)，直接寫入下一級(jí)存儲(chǔ)器而不調(diào)塊。,Cache的結(jié)構(gòu),例子：DEC的Alpha AXP21064中的內(nèi)部數(shù)據(jù)Cache,簡(jiǎn)介 容量：8KB 塊大?。?2B 塊數(shù)：256 采用不按寫分配 映象方法：直接映象 “寫”策略：寫直達(dá) 寫緩沖器大?。?個(gè)塊,混合Cache與分離Cache (1) 優(yōu)缺點(diǎn) (2) 失效率的比較,失效情況下的操作,16 KB,容 量,1 KB,2 KB,4 KB,8 KB,32 KB,指令 Cache,3.06%,失 效 率 的 比 較,64 KB,128 KB,數(shù)據(jù) Cache,混合 Cache,2.26%,1.78%,1.10%,0.64%,0.39%,0.15%,0.02%,24.61%,20.57%,15.94%,10.19%,6.47%,4.82%,3.77%,2.88%,13.34%,9.78%,7.24%,4.57%,2.87%,1.99%,1.36%,0.95%,訪問(wèn)指令Cache的百分比指令Cache的失效率 訪問(wèn)數(shù)據(jù)Cache的百分比數(shù)據(jù)Cache的失效率,Cache性能分析,平均訪問(wèn)時(shí)間 平均訪問(wèn)時(shí)間命中時(shí)間失效率失效開銷,失效率,假設(shè)Cache的命中時(shí)間為1個(gè)時(shí)鐘周期，失效開銷為50 個(gè)時(shí)鐘周期，在混合Cache中一次load或store操作訪問(wèn)Cache的命中時(shí)間都要增加一個(gè)時(shí)鐘周期(因?yàn)榛旌螩ache只有一個(gè)端口，無(wú)法同時(shí)滿足兩個(gè)請(qǐng)求?；旌螩ache會(huì)導(dǎo)致結(jié)構(gòu)沖突)，根據(jù)表所列的失效率，試問(wèn)指令Cache和數(shù)據(jù)Cache容量均為16KB的分離Cache和容量為32KB的混合Cache相比，哪種Cache的失效率更低？又假設(shè)采用寫直達(dá)策略，且有一個(gè)寫緩沖器，并且忽略寫緩沖器引起的等待。請(qǐng)問(wèn)上述兩種情況下平均訪存時(shí)間各是多少？,解： 如前所述，約75%的訪存為取指令。因此， 分離Cache的總體失效率為： (75%0.64%)(25%6.47%)2.10% 根據(jù)表，容量為32KB的混合Cache的失 效率略低一些，只有1.99%.,平均訪存時(shí)間公式可以分為指令訪問(wèn)和數(shù)據(jù)訪問(wèn)兩部分： 平均訪存時(shí)間指令所占的百分比 (指令命中時(shí)間指令失效率失效開銷) 數(shù)據(jù)所占的百分比 (數(shù)據(jù)命中時(shí)間數(shù)據(jù)失效率失效開銷) 所以，兩種結(jié)構(gòu)的平均訪存時(shí)間分別為： 平均訪存時(shí)間分離75%(10.64%50) 25%(16.47%50) (75%1.32)(25%4.325) 0.9901.0592.05,平均訪存時(shí)間混合75%(11.99%50) 25%(111.99%50) (75%1.995)(25%2.995) 1.4960.7492.24,程序執(zhí)行時(shí)間 CPU時(shí)間(CPU執(zhí)行周期數(shù)存儲(chǔ)器停頓周期數(shù)) 時(shí)鐘周期時(shí)間 其中： 存儲(chǔ)器停頓周期數(shù)訪存次數(shù)失效率失效開銷,CPU時(shí)間ICCPIexe每條指令的平均存儲(chǔ) 器停頓周期數(shù)時(shí)鐘周期時(shí)間,CPU時(shí)間ICCPIexe訪存次數(shù)/指令數(shù) 失效率失效開銷時(shí)鐘周期時(shí)間,例 我們用一個(gè)和Alpha AXP類似的機(jī)器作為 第一個(gè)例子。假設(shè)Cache失效開銷為50個(gè)時(shí)鐘 周期，當(dāng)不考慮存儲(chǔ)器停頓時(shí)，所有指令的 執(zhí)行時(shí)間都是2.0個(gè)時(shí)鐘周期， Cache的失效 率為2%，平均每條指令訪存1.33次。試分析 Cache對(duì)性能的影響。,考慮Cache的失效后，性能為： CPU 時(shí)間有cacheIC(2.0(1.332%50) 時(shí)鐘周期時(shí)間 IC3.33時(shí)鐘周期時(shí)間,CPU 時(shí)間IC(CPIexe ) 時(shí)鐘周期時(shí)間,存儲(chǔ)器停頓周期數(shù),指令數(shù),解：,實(shí)際CPI ：3.33 3.33/2.0 = 1.67(倍),CPU時(shí)間也增加為原來(lái)的1.67倍。但若不采用Cache,則： CPI2.0+501.3368.5,考慮兩種不同組織結(jié)構(gòu)的Cache：直接映象 Cache和兩路組相聯(lián)Cache，試問(wèn)它們對(duì)CPU的性 能有何影響？先求平均訪存時(shí)間，然后再計(jì)算 CPU性能。分析時(shí)請(qǐng)用以下假設(shè)： 理想Cache(命中率為100)情況下的CPI 為2.0，時(shí)鐘周期為2ns，平均每條指令 訪存1.3次。 兩種Cache容量均為64KB，塊大小都是32 字節(jié)。, 后圖說(shuō)明，在組相聯(lián)Cache中，我們必須增 加一個(gè)多路選擇器，用于根據(jù)標(biāo)識(shí)匹配結(jié)果 從相應(yīng)組的塊中選擇所需的數(shù)據(jù)。因?yàn)镃PU 的速度直接與Cache命中的速度緊密相關(guān),所 以對(duì)于組相聯(lián)Cache，由于多路選擇器的存 在而使CPU的時(shí)鐘周期增加到原來(lái)的1.10倍。 這兩種結(jié)構(gòu)Cache的失效開銷都是70ns。在 實(shí)際應(yīng)用中，應(yīng)取整為整數(shù)個(gè)時(shí)鐘周期。 命中時(shí)間為1個(gè)時(shí)鐘周期，64KB直接映象 Cache的失效率為1.4%，相同容量的兩路組 相聯(lián)Cache的失效率為1.0%。,由: 平均訪存時(shí)間命中時(shí)間失效率失效開銷 得: 平均訪存時(shí)間1路2.0(0.01470)2.98ns 平均訪存時(shí)間2路2.01.10(0.01070)2.90ns,由: CPU 時(shí)間IC(CPIexe每條指令的平均存儲(chǔ)器 停頓周期數(shù))時(shí)鐘周期時(shí)間 IC (CPIexe時(shí)鐘周期時(shí)間 每條指令的平均存儲(chǔ)器停頓時(shí)間),解：,CPU時(shí)間1路IC(2.02(1.30.01470) 5.27IC CPU時(shí)間2路IC(2.021.10 (1.30.01070) 5.31IC,5.31IC,CPU時(shí)間1路, 1.01,5.27IC,CPU時(shí)間2路,平均訪存時(shí)間命中時(shí)間失效率失效開銷 可以從三個(gè)方面改進(jìn)Cache的性能： (1) 降低失效率 (2) 減少失效開銷 (3) 減少Cache命中,改進(jìn)Cache性能,(1)強(qiáng)制性失效(Compulsory miss) 當(dāng)?shù)谝淮卧L問(wèn)一個(gè)塊時(shí)，該塊不在Cache中，需從下一級(jí)存儲(chǔ)器中調(diào)入Cache，這就是強(qiáng)制性失效。 (冷啟動(dòng)失效，首次訪問(wèn)失效。) (2) 容量失效(Capacity miss ) 如果程序執(zhí)行時(shí)所需的塊不能全部調(diào)入Cache中，則當(dāng)某些塊被替換后，若又重新被訪問(wèn)，就會(huì)發(fā)生失效。這種失效稱為容量失效。,降低Cache失效率的方法,(3) 沖突失效(Conflict miss) 在組相聯(lián)或直接映象Cache中，若太多 的塊映象到同一組(塊)中，則會(huì)出現(xiàn)該組 中某個(gè)塊被別的塊替換(即使別的組或塊有 空閑位置)，然后又被重新訪問(wèn)的情況。這 就是發(fā)生了沖突失效。 (碰撞失效，干擾失效),可以看出： (1) 相聯(lián)度越高，沖突失效就越少； (2) 強(qiáng)制性失效和容量失效不受相聯(lián)度的影響； (3) 強(qiáng)制性失效不受Cache容量的影響，但容 量失效卻隨著容量的增加而減少； (4) 表中的數(shù)據(jù)符合2:1的Cache經(jīng)驗(yàn)規(guī)則，即 大小為N 的直接映象Cache的失效率約等于 大小為N/2 的兩路組相聯(lián)Cache的失效率。,強(qiáng)制性失效：增加塊大小，預(yù)取 (本身很少) 容量失效：增加容量 (抖動(dòng)現(xiàn)象) 沖突失效：提高相聯(lián)度 (理想情況：全相聯(lián)),減少三種失效的方法,許多降低失效率的方法會(huì)增加命中時(shí)間或失效開銷,增加Cache塊大小,1. 失效率與塊大小的關(guān)系 (1) 對(duì)于給定的Cache容量，當(dāng)塊大小增加 失效率開始是下降，后來(lái)反而上升了； (2) Cache容量越大，使失效率達(dá)到最低的 塊大小就越大。,2. 增加塊大小會(huì)增加失效開銷,例 5.4,假定存儲(chǔ)系統(tǒng)在延遲40個(gè)時(shí)鐘周期后，每2個(gè) 時(shí)鐘周期能送出16個(gè)字節(jié)。即:經(jīng)過(guò)42個(gè)時(shí)鐘周期， 它可提供16個(gè)字節(jié)；經(jīng)過(guò)44個(gè)時(shí)鐘周期，可提供32 個(gè)字節(jié)；依此類推。試問(wèn)對(duì)于表5-6中列出的各種 容量的Cache，在塊大小分別為多少時(shí)，平均訪存 時(shí)間最??？,解： 1KB、4KB、16KB Cache: 塊大小32字節(jié) 64KB、256KB Cache: 塊大小64字節(jié),提高相聯(lián)度,1. 采用相聯(lián)度超過(guò)8的方法實(shí)際意義不大,2. 2:1 Cache經(jīng)驗(yàn)規(guī)則 容量為N 的直接映象Cache 容量為N/2的兩路組相聯(lián)Cache,3. 提高相聯(lián)度是以增加命中時(shí)間為代價(jià) 例如： TTL或ECL板級(jí)Cache，兩路組相聯(lián)：增加10 定制的CMOS Cache, 兩路組相聯(lián)：增加2,假定提高相聯(lián)度會(huì)按下列比例增大處理器時(shí)鐘周期： 時(shí)鐘周期2路 1.10時(shí)鐘周期1路 時(shí)鐘周期4路 1.12時(shí)鐘周期1路 時(shí)鐘周期8路 1.14時(shí)鐘周期1路 假定命中時(shí)間為1個(gè)時(shí)鐘，直接映象情況 下失效開銷為50個(gè)時(shí)鐘周期，而且假設(shè)不必將 失效開銷取整。使用表55中的失效率，試問(wèn) 當(dāng)Cache為多大時(shí)，以下不等式成立？,平均訪存時(shí)間8路 平均訪存時(shí)間4路 平均訪存時(shí)間4路 平均訪存時(shí)間2路 平均訪存時(shí)間2路 平均訪存時(shí)間1路,在各種相聯(lián)度的情況下，平均訪存時(shí)間分別為： 平均訪存時(shí)間8路 = 命中時(shí)間8路 + 失效率8路 失效開銷8路 = 1.14失效率8路50 平均訪存時(shí)間4路 = 1.12 失效率4路50 平均訪存時(shí)間2路 = 1.10 失效率2路50 平均訪存時(shí)間1路 = 1.00 失效率1路50,在每種情況下的失效開銷相同，都是50個(gè)時(shí)鐘周期。把相應(yīng)的失效率代入上式， 即可得平均訪存時(shí)間。 例如，1KB的直接映象Cache的平均訪存時(shí)間為： 平均訪存時(shí)間1路 1.00(0.13350) 7.65 容量為128KB的8路組相聯(lián)Cache的平均訪存時(shí)間為： 平均訪存時(shí)間8路 1.14(0.00650) 1.44,1. 基本思想 在Cache和它從下一級(jí)存儲(chǔ)器調(diào)數(shù)據(jù) 的通路之間設(shè)置一個(gè)全相聯(lián)的小Cache， 用于存放被替換出去的塊(稱為Victim)， 以備重用。,Victim Cache,對(duì)于減小沖突失效很有效，特別是對(duì)于小容量的直接映象數(shù)據(jù)Cache，作用尤其明顯。 例如，項(xiàng)數(shù)為4的Victim Cache: 使4KB Cache的沖突失效減少20%90%,作用,直接映象 vs組相聯(lián),偽相聯(lián)Cache,偽相聯(lián)Cache,優(yōu) 點(diǎn),缺 點(diǎn),直接映象,組相聯(lián),命中時(shí)間小,命中時(shí)間大,失效率高,失效率低,取直接映象及組相聯(lián)兩者的優(yōu)點(diǎn)： 命中時(shí)間小，失效率低,(1) 基本思想及工作原理 在邏輯上把直接映象Cache的空間上下平分為兩個(gè)區(qū)。對(duì)于任何一次訪問(wèn)，偽相聯(lián)Cache先按直接映象Cache的方式去處理。若命中，則其訪問(wèn)過(guò)程與直接映象Cache的情況一樣。若不命中，則再到另一區(qū)相應(yīng)的位置去查找。若找到，則發(fā)生了偽命中，否則就只好訪問(wèn)下一級(jí)存儲(chǔ)器。,(2) 快速命中與慢速命中 要保證絕大多數(shù)命中都是快速命中。,3. 例題,假設(shè)當(dāng)在按直接映象找到的位置處沒(méi)有發(fā) 現(xiàn)匹配、而在另一個(gè)位置才找到數(shù)據(jù)(偽命中) 需要2個(gè)額外的周期。仍用上個(gè)例子中的數(shù)據(jù)， 問(wèn)：當(dāng)Cache容量分別為2KB和128KB時(shí)，直接 映象、兩路組相聯(lián)和偽相聯(lián)這三種組織結(jié)構(gòu)中， 哪一種速度最快？,首先考慮標(biāo)準(zhǔn)的平均訪存時(shí)間公式： 平均訪存時(shí)間偽相聯(lián) 命中時(shí)間偽相聯(lián)失效率偽相聯(lián)失效開銷偽相聯(lián) 由于： 失效率偽相聯(lián)失效率2路 命中時(shí)間偽相聯(lián)命中時(shí)間1路偽命中率偽相聯(lián)2； 偽命中率偽相聯(lián)命中率2路命中率1路 (1失效率2路)(1失效率1路) 失效率1路失效率2路,故： 平均訪存時(shí)間偽相聯(lián) 命中時(shí)間1路(失效率1路失效率2路)2 失效率2路失效開銷1路,將表中的數(shù)據(jù)代入上面的公式，得： 平均訪存時(shí)間偽相聯(lián)，2KB 1(0.0980.076)2(0.07650) 4.844 平均訪存時(shí)間偽相聯(lián)，128KB 1(0.0100.007)2(0.00750) 1.356,根據(jù)上一個(gè)例子中的表58，對(duì)于2KB Cache，可得： 平均訪存時(shí)間1路 5.90 個(gè)時(shí)鐘 平均訪存時(shí)間2路 4.90 個(gè)時(shí)鐘 對(duì)于128KB的Cache有，可得： 平均訪存時(shí)間1路 1.50 個(gè)時(shí)鐘 平均訪存時(shí)間2路 1.45 個(gè)時(shí)鐘 可見，對(duì)于這兩種Cache容量，偽相聯(lián)Cache 都是速度最快的。,缺點(diǎn)：多種命中時(shí)間,硬件預(yù)取技術(shù),1. 指令和數(shù)據(jù)都可以預(yù)取,2. 預(yù)取內(nèi)容既可放入Cache，也可放在 外緩沖器中 例如：指令流緩沖器,3. 預(yù)取效果 (1) Joppi的研究結(jié)果 指令預(yù)取 (4KB，直接映象Cache, 塊大小16字節(jié)),1個(gè)塊的指令流緩沖器： 捕獲1525的失效 4個(gè)塊的指令流緩沖器： 捕獲50 16個(gè)塊的指令流緩沖器：捕獲72, 數(shù)據(jù)預(yù)取 (4KB,直接映象Cache) 1個(gè)數(shù)據(jù)流緩沖器：捕獲25的失效還可以采用多個(gè)數(shù)據(jù)流緩沖器,Palacharla和Kessler的研究結(jié)果 流緩沖器：既能預(yù)取指令又能預(yù)取數(shù)據(jù) 對(duì)于兩個(gè)64KB四路組相聯(lián)Cache來(lái)說(shuō)： 8個(gè)流緩沖器能捕獲5070的失效。,Alpha AXP 21064采用指令預(yù)取技術(shù)，其實(shí)際 失效率是多少？若不采用指令預(yù)取技術(shù)，Alpha APX 21064的指令Cache必須為多大才能保持平均訪 存時(shí)間不變？,解： 假設(shè)從預(yù)取緩沖器中找到所需指令需多花1個(gè) 時(shí)鐘周期。 平均訪存時(shí)間預(yù)取 命中時(shí)間失效率預(yù)取命中率1 失效率(1預(yù)取命中率)失效開銷,假設(shè)： 預(yù)取命中率25 命中時(shí)間1個(gè)時(shí)鐘周期 失效開銷50個(gè)時(shí)鐘周期 由表5.4可知，8KB指令Cache的失效率1.10 故平均訪存時(shí)間預(yù)取 1(1.10 %25 %1) (1.10 %(125 %)50) 10.002750.4125 1.415 由公式： 平均訪問(wèn)時(shí)間命中時(shí)間失效率失效開銷,可得相應(yīng)的失效率為： 失效率(平均訪問(wèn)時(shí)間命中時(shí)間)/失效開銷 (1.4511)/500.83,8KB Cache,帶預(yù)取的 8kB Cache,失效率,1.10,0.83,16KB Cache,0.64,由編譯器控制的預(yù)取,1. 預(yù)取的類型 寄存器預(yù)?。喊褦?shù)據(jù)取到寄存器中 Cache預(yù)?。?只將數(shù)據(jù)取到Cache中 故障性預(yù)?。侯A(yù)取時(shí)，若出現(xiàn)虛地址故障 或違反訪問(wèn)權(quán)限，就會(huì)發(fā)生異常。 非故障性預(yù)?。侯A(yù)取時(shí)，若出現(xiàn)虛地址故 障或違反訪問(wèn)權(quán)限，并不會(huì)導(dǎo)致異常，只 是轉(zhuǎn)變?yōu)椤安活A(yù)取”。,由編譯器加入預(yù)取指令，在數(shù)據(jù)被用到之前發(fā)出預(yù)取請(qǐng)求。,4. 例題,2. 在預(yù)取數(shù)據(jù)的同時(shí)，處理器應(yīng)能繼續(xù)執(zhí)行 只有這樣，預(yù)取才有意義。 非阻塞Cache (非鎖定Cache),3. 循環(huán)是預(yù)取優(yōu)化的主要對(duì)象 失效開銷小時(shí)：循環(huán)體展開12次 失效開銷大時(shí)：循環(huán)體展開許多次,例 對(duì)于下面的程序，判斷哪些訪問(wèn)可能會(huì)導(dǎo)致 數(shù)據(jù)Cache失效。然后，加入預(yù)取指令以減少失 效。最后，計(jì)算所執(zhí)行的預(yù)取指令的條數(shù)以及通 過(guò)預(yù)取避免的失效次數(shù)。假定： (1) 我們用的是一個(gè)容量為8KB、塊大小為 16B的直接映象Cache，它采用寫回法并 且按寫分配。 (2) a、b分別為3100(3行100列)和1013 的雙精度浮點(diǎn)數(shù)組，每個(gè)元素都是8個(gè) 字節(jié)。當(dāng)程序開始執(zhí)行時(shí)，這些數(shù)據(jù)都 不在Cache內(nèi)。,for (i0 ; i 3 ; ii1 ) for (j0 ; j 100 ; jj1 ) aijbj0bj10;,解： (1) 計(jì)算過(guò)程 (2) 實(shí)效情況 總的失效次數(shù)251次 (3) 改進(jìn)后的程序,for (j0，j100；jj1) prefetch (bj70); /* 預(yù)取7次循環(huán)后所需的b(j ,0 ) */ prefetch (a0j7); /* 預(yù)取7次循環(huán)后所需的a(0,j ) */ a0jbj 0 * b j10 for (i1; i 3; ii1) for (j0; j 100; jj1) prefetch(aij7); /* 預(yù)取7次循環(huán)后所需的a(i , j ) */ aijbj0 * bj10; ,例 在以下條件下，計(jì)算例5.8中所節(jié)約的時(shí)間： (1) 忽略指令Cache失效，并假設(shè)數(shù)據(jù)Cache 無(wú)沖突失效和容量失效。 (2) 假設(shè)預(yù)取可以被重疊或與Cache失效重 疊執(zhí)行，從而能以最大的存儲(chǔ)帶寬傳送 數(shù)據(jù)。 (3) 不考慮Cache失效時(shí)，修改前的循環(huán)每7 個(gè)時(shí)鐘周期循環(huán)一次。修改后的程序中，,失效情況 總的失效次數(shù)19次,解： 修改前： 循環(huán)時(shí)間3007 2100 失效開銷2515012550/14650 21001255014650,第一個(gè)預(yù)取循環(huán)每9個(gè)時(shí)鐘周期循環(huán)一次， 而第二個(gè)預(yù)取循環(huán)每8個(gè)時(shí)鐘周期循環(huán)一 次(包括外層for循環(huán)的開銷)。 (4) 一次失效需50個(gè)時(shí)鐘周期。,修改后： 循環(huán)時(shí)間100920082500 失效時(shí)間1950950 25009503450 加速比14650/34504.2,編譯器優(yōu)化,2KB Cache: 降低50 8KB Cache：降低75%,1. 基本思想,在編譯時(shí)，對(duì)程序中的指令和數(shù)據(jù)進(jìn)行重新組織，以降低Cache失效率。,2. McFaring 發(fā)現(xiàn)：通過(guò)對(duì)指令進(jìn)行重新排序，可有效地降低指令Cache的失效率。,3. 數(shù)據(jù)對(duì)存儲(chǔ)位置的限制比指令的少，因此 更便于優(yōu)化。 通過(guò)把數(shù)據(jù)重新組織，使得在一塊數(shù) 據(jù)被從Cache替換出去之前，能最大限度 利用其中的數(shù)據(jù)(訪問(wèn)次數(shù)最多) (1) 數(shù)組合并 舉例： /* 修改前 */ int val SIZE; int key SIZE;,(2) 內(nèi)外循環(huán)交換 舉例： /* 修改前 */ for (j0 ;j100 ;jj1) for (i0 ;i5000 ;ii1) xij2*xij;,/* 修改后 */ struct merge int val ; int key ; ; struct merge merged_arraysize;,(3) 循環(huán)融合 舉例： /* 修改前 */ for (i0 ; iN ;ii1) for (j0 ; jN ; jj1) aij1/bij*cij;,/* 修改后 */ for (i0 ;i100 ;ii1) for (j0 ;j 000 ;jj1) xij2*xij;,/* 修改后 */ for (i0 ;i N ;ii1) for (j0 ;j N ;jj1) aij1/bij*cij; dijaijcij; ,for (i0 ;iN ;ii1) for (j0 ; jN ;jj1) dijaijcij;,(4)分塊 把對(duì)數(shù)組的整行或整列訪問(wèn)改為按塊進(jìn)行。,舉例： /* 修改前 */ for (i0; i N; ii1) for (j0; j N; jj1) r0; for (k0; k N; kk1) rryik*zkj; xijr; ,計(jì)算過(guò)程 失效次數(shù)：2N3N2,/* 修改后 */ for (jj0; jj N; jjjj1) for (kk0; kk N; kkkk1) for (i0; i N; ii1) for (jjj; j min(jjB1,N); jj1) r0; for (kkk; k min(kkB1,N); kk1) rryik*zkj; xijxijr; ,失效次數(shù)：2N3 /B N2,讓讀失效優(yōu)先于寫,減少Cache失效開銷,1. Cache中的寫緩沖器導(dǎo)致對(duì)存儲(chǔ)器訪問(wèn)的 復(fù)雜化,2. 解決問(wèn)題的方法(讀失效的處理) 推遲對(duì)讀失效的處理 (缺點(diǎn)：讀失效的開銷增加，如50) 檢查寫緩沖器中的內(nèi)容,3. 在寫回法Cache中，也可采用寫緩沖器,子塊放置技術(shù),1. 為減少標(biāo)識(shí)的位數(shù)，可采用增加塊大小的 方法，但這會(huì)增加失效開銷，故應(yīng)采用子 塊放置技術(shù)。,2. 子塊放置技術(shù)：把Cache塊進(jìn)一步劃分為更 小的塊(子塊)，并給每個(gè)子塊賦予一位有 效位，用于指明該子塊中的數(shù)據(jù)是否有效。 Cache與下一級(jí)存儲(chǔ)器之間以子塊為單位傳 送數(shù)據(jù)。但標(biāo)識(shí)仍以塊為單位。,請(qǐng)求字處理技術(shù),1. 請(qǐng)求字 從下一級(jí)存儲(chǔ)器調(diào)入Cache的塊中，只有 一個(gè)字是立即需要的。這個(gè)字稱為請(qǐng)求字。,2. 應(yīng)盡早把請(qǐng)求字發(fā)送給CPU 盡早重啟動(dòng)：調(diào)塊時(shí)，從塊的起始位置開 始讀起。一旦請(qǐng)求字到達(dá)，就立即發(fā)送給 CPU，讓CPU繼續(xù)執(zhí)行。 請(qǐng)求字優(yōu)先：調(diào)塊時(shí)，從請(qǐng)求字所在的位 置讀起。這樣，第一個(gè)讀出的字便是請(qǐng)求 字。將之立即發(fā)送給CPU。,3. 這種技術(shù)在以下情況下效果不大： Cache塊較小 下一條指令正好訪問(wèn)同一Cache塊的另 一部分,非阻塞Cache技術(shù),1. 非阻塞Cache：Cache失效時(shí)仍允許CPU進(jìn)行 其它的命中訪問(wèn)。即允許“失效下命中”。,2. 進(jìn)一步提高性能：“多重失效下命中” “失效下失效” (存儲(chǔ)器必須能夠處理多個(gè)失效),3. 重疊失效個(gè)數(shù)對(duì)平均訪問(wèn)時(shí)間的影響,非阻塞Cache平均存儲(chǔ)器等待時(shí)間 與阻塞Cache的比值,1,2,浮點(diǎn)程序,76,51,64,39,整數(shù)程序,81,78,78,重疊失效個(gè)數(shù),對(duì)于圖所描述的Cache，在兩路組相聯(lián)和“一次失效下命中”這兩種措施中，哪一種對(duì)浮點(diǎn)程序更重要？對(duì)整數(shù)程序的情況如何？ 假設(shè)8KB數(shù)據(jù)Cache的平均失效率為： 對(duì)于浮點(diǎn)程序，直接映象Cache為11.4%，兩路組相聯(lián)Cache為10.7%； 對(duì)于整數(shù)程序，直接映象Cache為7.4%，兩路組相聯(lián)Cache為6.0%。并且假設(shè)平均存儲(chǔ)器等待時(shí)間是失效率和失效開銷的積，失效開銷為16個(gè)時(shí)鐘周期。,對(duì)于浮點(diǎn)程序，平均存儲(chǔ)器等待時(shí)間為： 失效率直接映象失效開銷11.4%161.82 失效率兩路組相聯(lián)失效開銷10.7%161.71 1.71/1.820.94,對(duì)于整數(shù)程序： 失效率直接映象失效開銷7.4 %161.18 失效率兩路組相聯(lián)失效開銷6.0 %16 0.96 0.96/1.18=0.81,解：,采用兩級(jí)Cache,1. 應(yīng)把Cache做得更快？還是更大？ 答案：二者兼顧，再增加一級(jí)Cache 第一級(jí)Cache(L1)小而快 第二級(jí)Cache(L2)容量大,2. 性能分析 平均訪問(wèn)時(shí)間 命中時(shí)間L1失效率L1失效開銷L1 命中時(shí)間L1失效率L1 (命中時(shí)間L2失效率L2失效開銷L2),3. 局部失效率與全局失效率 局部失效率該級(jí)Cache的失效次數(shù)/到達(dá) 該級(jí)Cache的訪問(wèn)次數(shù) 例如：上述式子中的失效率L2 全局失效率該級(jí)Cache的失效次數(shù)/CPU 發(fā)出的訪存的總次數(shù) 全局失效率L2失效率L1失效率L2 評(píng)價(jià)第二級(jí)Cache時(shí)，應(yīng)使用全局失效率 這個(gè)指標(biāo)。,假設(shè)在1000次訪存中，第一級(jí)Cache失效40次， 第二級(jí)Cache失效20次。試問(wèn)：在這種情況下，該 Cache系統(tǒng)的局部失效率和全局失效率各是多少？ 第一級(jí)Cache的失效率（全局和局部）是40/1000， 即4%；第二級(jí)Cache的局部失效率是20/40，即50%， 第二級(jí)Cache的全局失效率是20/1000，即2%。,4. 當(dāng)?shù)诙?jí)Cache比第一級(jí)Cache大得多時(shí)，兩 級(jí)Cache的全局失效率與容量和第二級(jí)Cache 相同的單級(jí)Cache的失效率非常接近。,5. 第二級(jí)Cache的參數(shù) 第二級(jí)Cache不會(huì)影響CPU的時(shí)鐘頻率， 因此其設(shè)計(jì)有更大的考慮空間。 兩個(gè)問(wèn)題： 能否降低CPI中的平均訪存時(shí)間部分？ 成本是多少？ (1) 容量 第二級(jí)Cache的容量一般比第一級(jí)的 大許多，如512KB。,(2) 相聯(lián)度 第二級(jí)Cache可采用較高的相聯(lián)度或偽相聯(lián)方法,例 給出有關(guān)第二級(jí)Cache的以下數(shù)據(jù)： 兩路組相聯(lián)使命中時(shí)間增加10%CPU時(shí)鐘周期 對(duì)于直接映象，命中時(shí)間L210個(gè)時(shí)鐘周期 對(duì)于直接映象，局部失效率L225% 對(duì)于兩路組相聯(lián)，局部失效率L220% 失效開銷L250個(gè)時(shí)鐘周期 試問(wèn)第二級(jí)Cache的相聯(lián)度對(duì)失效開銷的影響如何？,對(duì)于一個(gè)直接映象的第二級(jí)Cache來(lái)說(shuō)，第一級(jí)Cache的失效開銷為： 失效開銷直接映象，L1 1025%5022.5個(gè)時(shí)鐘周期 對(duì)于兩路組相聯(lián)第二級(jí)Cache來(lái)說(shuō)，命中時(shí)間增加了10%(0.1)個(gè)時(shí)鐘周期，故第一級(jí)Cache的失效開銷為： 失效開銷兩路組相聯(lián)，L1 10.120%5020.1個(gè)時(shí)鐘周期 把第二級(jí)Cache的命中時(shí)間取整，得10或11，則：,失效開銷兩路組相聯(lián)，L1 1020%5020.0個(gè)時(shí)鐘周期 失效開銷兩路組相聯(lián)，L1 1120%5021.0個(gè)時(shí)鐘周期 故對(duì)于第二級(jí)Cache來(lái)說(shuō)，兩路組相聯(lián)優(yōu)于直接映象。,(3) 塊大小 第二級(jí)Cache可采用較大的塊， 如 64、128、256字節(jié)。 為減少平均訪存時(shí)間，可以讓容量較小的第一級(jí)Cache采用較小的塊，而讓容量較大的第二級(jí)Cache采用較大的塊。,5.5 減少命中時(shí)間,2. 應(yīng)使Cache足夠小，以便可以與CPU一起放 在同一塊芯片上。,命中時(shí)間直接影響到處理器的時(shí)鐘頻率。在 當(dāng)今的許多計(jì)算機(jī)中，往往是Cache的訪問(wèn)時(shí)間 限制了處理器的時(shí)鐘頻率。,1. 硬件越簡(jiǎn)單，速度就越快；,1. 虛擬Cache 訪問(wèn)Cache的索引以及Cache中的標(biāo)識(shí)都是虛擬地址(一部分)。 2. 并非都采用虛擬Cache(為什么?) 3. 虛擬Cache的清空問(wèn)題,虛擬Cache,解決方法：在地址標(biāo)識(shí)中增加PID字段 (進(jìn)程標(biāo)識(shí)符) 三種情況下失效率的比較 單進(jìn)程，PIDs，清空 PIDs與單進(jìn)程相比：0.30.6 PIDs與清空相比： 0.64.3%,4. 同義和別名 解決方法：反別名法,頁(yè)著色 5. 虛擬索引物理標(biāo)識(shí) 優(yōu)點(diǎn)：兼得虛擬Cache和物理Cache的好處 局限性：Cache容量受到限制 (頁(yè)內(nèi)位移) Cache容量頁(yè)大小相聯(lián)度 6. 舉例：IBM3033的Cache 頁(yè)大小4KB 相聯(lián)度16,Cache容量164KB64KB 7. 另一種方法：硬件散列變換,頁(yè)地址 地址標(biāo)識(shí),頁(yè)內(nèi)位移,索 引,塊內(nèi)位移,31,12 11,0,寫操作流水化,1. 主存的主要性能指標(biāo)：延遲和帶寬 2. 以往： Cache主要關(guān)心延遲，I/O主要關(guān)心帶寬 現(xiàn)在：Cache關(guān)心兩者 下面討論幾種能提高主存性能的存儲(chǔ)器組織技術(shù)在下面的討論中，我們以處理Cache失效為例來(lái)說(shuō)明各種存儲(chǔ)器組織結(jié)構(gòu)的好處。,主 存, 增加Cache塊大小能利用主存帶寬增加所帶 來(lái)的好處。在以下的討論中，我們假設(shè)基本存儲(chǔ)器結(jié)構(gòu)的性能為：,送地址需4個(gè)時(shí)鐘周期 每個(gè)字的訪問(wèn)時(shí)間為24個(gè)時(shí)鐘周期 傳送一個(gè)字的數(shù)據(jù)需4個(gè)時(shí)鐘周期, 為了減少失效開銷TM，應(yīng)該：,減少主存延遲 提高主存帶寬,如果Cache大小為4個(gè)字，則： 失效開銷4(4244) 432128(時(shí)鐘周期) 帶寬16/1280.0125(字節(jié)/時(shí)鐘周期),增加存儲(chǔ)器的寬度 性能舉例 (參照前面的假設(shè)) 當(dāng)寬度為4個(gè)字時(shí)： 失效開銷132(周期) 帶寬0.5(字節(jié)/周期), 缺點(diǎn)：,增加CPU和存儲(chǔ)器之間的連接通路的寬度 CUP和Cache之間有一個(gè)多路選擇器 擴(kuò)充主存的最小增量增加了相應(yīng)的倍數(shù) 寫入有可能變得復(fù)雜, 存儲(chǔ)器的各個(gè)體一般是按字交叉的 交叉存儲(chǔ)器（interleaved memory） 通常是指存儲(chǔ)器的各個(gè)體是按字交叉的。 字交叉存儲(chǔ)器非常適合于處理： Cache讀失效，寫回法Cache中的寫回,性能舉例：(參照前面的假設(shè)) 失效開銷4244444(周期) 帶寬0.4(字節(jié)/周期),假設(shè)四個(gè)存儲(chǔ)體的地址是在字一級(jí)交叉的，即 存儲(chǔ)體0中每個(gè)字的地址對(duì)4取模都是0，體1中每個(gè) 字的地址對(duì)4取模都是1，依此類推。,0 4 8 12,地址 體0,1 5 9 13,地址 體1,2 6 10 14,地址 體2,3 7 11 15,地址 體3,假設(shè)某臺(tái)機(jī)器的特性及其Cache的性能為： 塊大小為1個(gè)字 存儲(chǔ)器總線寬度為1個(gè)字 Cache失效率為3 % 平均每條指令訪存1.2次 Cache失效開銷為32個(gè)時(shí)鐘周期(和上面相同) 平均CPI(忽略Cache失效)為2 試問(wèn)多體交