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