【正文】 時，需要被迫騰出其中的某一塊，以接納新調(diào)入的塊。LRU：選擇最近最少被訪問的塊作為被替換的塊。實際實現(xiàn)都是選擇最久沒有被訪問的塊作為被替換的塊。寫直達法：在執(zhí)行寫操作時，不僅把信息寫入Cache中相應(yīng)的塊，而且也寫入下一級存儲器中相應(yīng)的塊。寫回法：只把信息寫入Cache中相應(yīng)塊，該塊只有被替換時，才被寫回主存。按寫分配法：寫失效時，先把所寫單元所在的塊調(diào)入Cache，然后再進行寫入。不按寫分配法：寫失效時，直接寫入下一級存儲器中，而不把相應(yīng)的塊調(diào)入Cache。命中時間：訪問Cache命中時所用的時間。失效率：CPU訪存時，在一級存儲器中找不到所需信息的概率。失效開銷：CPU向二級存儲器發(fā)出訪問請求到把這個數(shù)據(jù)調(diào)入一級存儲器所需的時間。強制性失效：當?shù)谝淮卧L問一個塊時，該塊不在Cache中，需要從下一級存儲器中調(diào)入Cache，這就是強制性失效。容量失效：如果程序在執(zhí)行時，所需要的塊不能全部調(diào)入Cache中，則當某些塊被替換后又重新被訪問，就會產(chǎn)生失效，這種失效就稱作容量失效。沖突失效：在組相聯(lián)或直接映象Cache中，若太多的塊映象到同一組（塊）中，則會出現(xiàn)該組中某個塊被別的塊替換（即使別的組或塊有空閑位置），然后又被重新訪問的情況。2：1Cache經(jīng)驗規(guī)則：大小為N的直接映象Cache的失效率約等于大小為N /2的兩路組相聯(lián)Cache的實效率。相聯(lián)度：在組相聯(lián)中，每組Cache中的塊數(shù)。Victim Cache：位于Cache和存儲器之間的又一級Cache，容量小，采用全相聯(lián)策略。用于存放由于失效而被丟棄（替換）的那些塊。每當失效發(fā)生時，在訪問下一級存儲器之前，先檢查Victim Cache中是否含有所需塊。故障性預(yù)取：在預(yù)取時，若出現(xiàn)虛地址故障或違反保護權(quán)限，就會發(fā)生異常。非故障性預(yù)?。涸陬A(yù)取時，若出現(xiàn)虛地址故障或違反保護權(quán)限，不發(fā)生異常。非阻塞Cache：Cache在等待預(yù)取數(shù)據(jù)返回時，還能繼續(xù)提供指令和數(shù)據(jù)。盡早重啟動：在請求字沒有到達時，CPU處于等待狀態(tài)。一旦請求字到達，就立即發(fā)送給CPU，讓等待的CPU盡早重啟動，繼續(xù)執(zhí)行。請求字優(yōu)先：調(diào)塊時，首先向存儲器請求CPU所要的請求字。請求字一旦到達，就立即送往CPU，讓CPU繼續(xù)執(zhí)行，同時從存儲器調(diào)入該塊的其余部分。虛擬Cache：地址使用虛地址的Cache。多體交叉存儲器：具有多個存儲體，各體之間按字交叉的存儲技術(shù)。存儲體沖突：多個請求要訪問同一個體。TLB：一個專用高速存儲器，用于存放近期經(jīng)常使用的頁表項，其內(nèi)容是頁表部分內(nèi)容的一個副本。 簡述“Cache—主存”層次與“主存—輔存”層次的區(qū)別。答： 存儲層次比較項目“Cache—主存”層次“主存—輔存”層次目的為了彌補主存速度的不足為了彌補主存容量的不足存儲管理的實現(xiàn)全部由專用硬件實現(xiàn)主要由軟件實現(xiàn)訪問速度的比值（第一級比第二級）幾比一幾萬比一典型的塊（頁）大小幾十個字節(jié)幾百到幾千個字節(jié)CPU對第二級的訪問方式可直接訪問均通過第一級不命中時CPU是否切換不切換切換到其它進程 地址映象方法有哪幾種？它們各有什么優(yōu)缺點？答：(1) 全相聯(lián)映象。實現(xiàn)查找的機制復(fù)雜，代價高，速度慢。Cache空間的利用率較高，塊沖突概率較低，因而Cache的失效率也低。（2）直接映象。實現(xiàn)查找的機制簡單，速度快。Cache空間的利用率較低，塊沖突概率較高，因而Cache的失效率也高。（3）組相聯(lián)映象。組相聯(lián)是直接映象和全相聯(lián)的一種折衷。 降低Cache失效率有哪幾種方法？簡述其基本思想。答：常用的降低Cache失效率的方法有下面幾種：（1） 增加Cache塊大小。增加塊大小利用了程序的空間局部性。（2） 增加Cache的容量。（3） 提高相聯(lián)度，降低沖突失效。（4） 偽相聯(lián)Cache，降低沖突失效。當對偽相聯(lián)Cache進行訪問時，首先是按與直接映象相同的方式進行訪問。如果命中，則從相應(yīng)的塊中取出所訪問的數(shù)據(jù)，送給CPU，訪問結(jié)束。如果不命中，就將索引字段的最高位取反，然后按照新索引去尋找“偽相聯(lián)組”中的對應(yīng)塊。如果這一塊的標識匹配，則稱發(fā)生了“偽命中”。否則，就訪問下一級存儲器。（5） 硬件預(yù)取技術(shù)。在處理器提出訪問請求前預(yù)取指令和數(shù)據(jù)。（6） 由編譯器控制的預(yù)取，硬件預(yù)取的替代方法，在編譯時加入預(yù)取的指令，在數(shù)據(jù)被用到之前發(fā)出預(yù)取請求。（7） 編譯器優(yōu)化，通過對軟件的優(yōu)化來降低失效率。（8） “犧牲”Cache。在Cache和其下一級存儲器的數(shù)據(jù)通路之間增設(shè)一個全相聯(lián)的小Cache，存放因沖突而被替換出去的那些塊。每當發(fā)生不命中時，在訪問下一級存儲器之前，先檢查“犧牲”Cache中是否含有所需的塊。如果有，就將該塊與Cache中某個塊做交換，把所需的塊從“犧牲”Cache 調(diào)入Cache。 簡述減小Cache失效開銷的幾種方法。答：讓讀失效優(yōu)先于寫、寫緩沖合并、請求字處理技術(shù)、非阻塞Cache或非鎖定Cache技術(shù)、采用二級Cache。 通過編譯器對程序優(yōu)化來改進Cache性能的方法有哪幾種？簡述其基本思想。答：（1）數(shù)組合并。通過提高空間局部性來減少失效次數(shù)。有些程序同時用相同的索引來訪問若干個數(shù)組的同一維，這些訪問可能會相互干擾，導(dǎo)致沖突失效，可以將這些相互獨立的數(shù)組合并成一個復(fù)合數(shù)組，使得一個Cache塊中能包含全部所需元素。（2）內(nèi)外循環(huán)交換。循環(huán)嵌套時，程序沒有按數(shù)據(jù)在存儲器中的順序訪問。只要簡單地交換內(nèi)外循環(huán)，就能使程序按數(shù)據(jù)在存儲器中的存儲順序進行訪問。（3）循環(huán)融合。有些程序含有幾部分獨立的程序段，它們用相同的循環(huán)訪問同樣的數(shù)組，對相同的數(shù)據(jù)作不同的運算。通過將它們?nèi)诤铣梢粋€單一循環(huán)，能使讀入Cache的數(shù)據(jù)被替換出去之前得到反復(fù)的使用。（4）分塊。通過改進時間局部性來減少失效。分塊不是對數(shù)組的整行或整列進行訪問，而是對子矩陣或塊進行操作。 在“Cache—主存”層次中，主存的更新算法有哪兩種？它們各有什么特點？答：（1）寫直達法。易于實現(xiàn)，而且下一級存儲器中的數(shù)據(jù)總是最新的。（2）寫回法。速度快，“寫”操作能以Cache存儲器的速度進行。而且對于同一單元的多個寫最后只需一次寫回下一級存儲器，有些“寫”只到達Cache，不到達主存，因而所使用的存儲器頻帶較低。 組相聯(lián)Cache的失效率比相同容量直接映象Cache的失效率低。由此能否得出結(jié)論：采用組相聯(lián)一定能帶來性能上的提高？為什么？答：不一定。因為組相聯(lián)命中率的提高是以增加命中時間為代價的，組相聯(lián)需要增加多路選擇開關(guān)。 寫出三級Cache的平均訪問時間的公式。解：平均訪存時間 ＝ 命中時間＋失效率失效開銷只有第I層失效時才會訪問第I＋1。設(shè)三級Cache的命中率分別為HL Hl HL3，失效率分別為MlMlML3，第三級Cache的失效開銷為PL3。 平均訪問時間TA ＝HL1＋Ml1{Hl2＋Ml2(HL3＋ML3PL3)} 假設(shè)對指令Cache的訪問占全部訪問的75%；而對數(shù)據(jù)Cache的訪問占全部訪問的25%。Cache的命中時間為1個時鐘周期，失效開銷為50 個時鐘周期，在混合Cache中一次load或store操作訪問Cache的命中時間都要增加一個時鐘周期，%，%，%。又假設(shè)采用寫直達策略，且有一個寫緩沖器，并且忽略寫緩沖器引起的等待。試問指令Cache和數(shù)據(jù)Cache容量均為32KB的分離Cache和容量為64KB的混合Cache相比，哪種Cache的失效率更低？兩種情況下平均訪存時間各是多少？解：（1）根據(jù)題意，約75%的訪存為取指令。因此，分離Cache的總體失效率為：（75%%）＋（25%%）＝%； 容量為128KB的混合Cache的失效率略低一些，%。 （2）平均訪存時間公式可以分為指令訪問和數(shù)據(jù)訪問兩部分： 平均訪存時間＝指令所占的百分比（讀命中時間＋讀失效率失效開銷）＋ 數(shù)據(jù)所占的百分比（數(shù)據(jù)命中時間＋數(shù)據(jù)失效率失效開銷） 所以，兩種結(jié)構(gòu)的平均訪存時間分別為： 分離Cache的平均訪存時間＝75%（1＋%50）＋25%（1＋%50）＝（75%）＋（25%）＝ 混合Cache的平均訪存時間＝75%（1＋%50）＋25%（1＋1＋%50）＝（75%）＋（25%）＝因此，盡管分離Cache的實際失效率比混合Cache的高，但其平均訪存時間反而較低。分離Cache提供了兩個端口，消除了結(jié)構(gòu)相關(guān)。 給定以下的假設(shè)，試計算直接映象Cache和兩路組相聯(lián)Cache的平均訪問時間以及CPU的性能。由計算結(jié)果能得出什么結(jié)論？（1） ，時鐘周期為2ns，；（2） 兩者Cache容量均為64KB，塊大小都是32字節(jié)；（3） 組相聯(lián)Cache中的多路選擇器使CPU的時鐘周期增加了10％；（4） 這兩種Cache的失效開銷都是80ns；（5） 命中時間為1個時鐘周期；（6） ％，％。解： 平均訪問時間＝命中時間＋失效率失效開銷平均訪問時間1路=+% *80=平均訪問時間2路=*(1+10%)+% *80=兩路組相聯(lián)的平均訪問時間比較低CPUtime=（CPU執(zhí)行+存儲等待周期）*時鐘周期CPU time=IC（CPI執(zhí)行+總失效次數(shù)/指令總數(shù)*失效開銷） *時鐘周期=IC（（CPI執(zhí)行*時鐘周期）+（每條指令的訪存次數(shù)*失效率*失效開銷*時鐘周期））CPU time 1way=IC(*2+**80)＝CPU time 2way=IC(*2+**80)＝相對性能比：。因此這里選擇兩路組相聯(lián)。 假設(shè)一臺計算機具有以下特性：（1） 95％的訪存在Cache中命中；（2） 塊大小為兩個字，且失效時整個塊被調(diào)入；（3） CPU發(fā)出訪存請求的速率為109字/s；（4） 25％的訪存為寫訪問；（5） 存儲器的最大流量為109字/s（包括讀和寫）；（6） 主存每次只能讀或?qū)懸粋€字；（7） 在任何時候，Cache中有30％的塊被修改過；（8） 寫失效時，Cache采用按寫分配法?，F(xiàn)欲給該計算機增添一臺外設(shè)，為此首先想知道主存的頻帶已用了多少。試對于以下兩種情況計算主存頻帶的平均使用比例。（1） 寫直達Cache；（2） 寫回法Cache。解：采用按寫分配（1）寫直達cache訪問命中，有兩種情況：讀命中，不訪問主存；寫命中，更新cache和主存，訪問主存一次。訪問失效，有兩種情況：讀失效，將主存中的塊調(diào)入cache中，訪問主存兩次；寫失效，將要寫的塊調(diào)入cache，訪問主存兩次，再將修改的數(shù)據(jù)寫入cache和主存，訪問主存一次，共三次。上述分析如下表所示。訪問命中訪問類型頻率訪存次數(shù)Y讀95%*75%=%0Y寫95%*25%=%1N讀5%*75%=%2N寫5%*25%=%3一次訪存請求最后真正的平均訪存次數(shù)=(%*0)+(%*1)+(%*2)+(%*3)＝已用帶寬=109/10 9 =%（2）寫回法cache訪問命中,有兩種情況：讀命中，不訪問主存；寫命中，不訪問主存。采用寫回法，只有當修改的cache塊被換出時，才寫入主存；訪問失效,有一個塊將被換出，這也有兩種情況：如果被替換的塊沒有修改過，將主存中的塊調(diào)入cache塊中，訪問主存兩次；如果被替換的塊修改過，則首先將修改的塊寫入主存，需要訪問主存兩次；然后將主存中的塊調(diào)入cache塊中，需要訪問主存兩次，共四次訪問主存。訪問命中塊為臟頻率訪存次數(shù)YN95%*70%=%0YY95%*30%=%0NN5%*70%=%2NY5%*30%=%4所以：一次訪存請求最后真正的平均訪存次數(shù)=％*0＋%*0+%*2+%*4=已用帶寬＝10 9/10 9＝13% 在偽相聯(lián)中，假設(shè)在直接映象位置沒有發(fā)現(xiàn)匹配，而在另一個位置才找到數(shù)據(jù)（偽命中）時，不對這兩個位置的數(shù)據(jù)進行交換。這時只需要1個額外的周期。假設(shè)失效開銷為50個時鐘周期，%，%；%，%。（1） 推導(dǎo)出平均訪存時間的公式。（2） 利用（1）中得到的公式，對于2KBCache和128KBCache，計算偽相聯(lián)的平均訪存時間。解：不管作了何種改進，失效開銷相同。不管是否交換內(nèi)容，在同一“偽相聯(lián)”組中的兩塊都是用同一個索引得到的，因此失效率相同，即：失效率偽相聯(lián)＝失效率2路。偽相聯(lián)cache的命中時間等于直接映象cache的命中時間加上偽相聯(lián)查找過程中的命中時間*該命中所需的額外開銷。命中時間偽相聯(lián)＝命中時間1路＋偽命中率偽相聯(lián)1交換或不交換內(nèi)容，偽相聯(lián)的命中率都是由于在第一次失效時，將地址取反，再在第二次查找?guī)淼?。因?偽命中率偽相聯(lián)＝命中率2路－命中率1路＝（1－失效率2路）－（1－失效率1路）＝失效率1路－失效率2路。交換內(nèi)容需要增加偽相聯(lián)的額外開銷。平均訪存時間偽相聯(lián)＝命中時間1路＋（失效率1路－失效率2路）1＋失效率2路失效開銷1路將題設(shè)中的數(shù)據(jù)帶入計算，得到：平均訪存時間2Kb=1+()*1+( *50 ) =平均訪存時間128Kb=1+()*1+( *50 ) =顯然是128KB的偽相聯(lián)Cache要快一些。 ，主存延遲是40個時鐘周期；傳輸速率為4字節(jié)/時鐘周期，且Cache中50%的塊是修改過的。每個塊中有32字節(jié)，20%的指令是數(shù)據(jù)傳送指令。并假設(shè)沒有寫緩存，在TLB失效的情況下需要20時鐘周期，TLB不會降低Cache命中率。%沒有在TLB中找到。（1） 在理想TLB情