Cache性能解讀課件

Cache性能評(píng)價(jià)提高Cache性能Cache性能本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)Cache性能評(píng)價(jià)Cache性能本章內(nèi)容>>Cache存儲(chǔ)Cache性能評(píng)價(jià)本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能CPU執(zhí)行時(shí)間平均存儲(chǔ)器訪問時(shí)間（AMAT）Cache性能評(píng)價(jià)本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>CacCPU執(zhí)行時(shí)間本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>Cache性能評(píng)價(jià)其中：3之1CPU執(zhí)行時(shí)間本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache例子本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>Cache性能評(píng)價(jià)問：假定有一臺(tái)計(jì)算機(jī)，當(dāng)所有存儲(chǔ)器訪問操作都能在Cache中命中時(shí)，CPI為1.0；數(shù)據(jù)訪問只有l(wèi)oad和store指令，這些指令占全部指令的50%；缺失代價(jià)為25個(gè)時(shí)鐘周期，缺失率為2%。問當(dāng)所有指令都在Cache中命中時(shí)，計(jì)算機(jī)性能能提高多少？答：Cache始終命中時(shí)的計(jì)算機(jī)性能為：3之2例子本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>例子（續(xù)）本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>Cache性能評(píng)價(jià)實(shí)際Cache的計(jì)算機(jī)性能為：兩者的性能比為：結(jié)論：不發(fā)生Cache缺失時(shí)計(jì)算機(jī)性能是原來的1.75倍3之3例子（續(xù)）本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache平均存儲(chǔ)器訪問時(shí)間（AMAT）本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>Cache性能評(píng)價(jià)3之1平均存儲(chǔ)器訪問時(shí)間（AMAT）本章內(nèi)容>>Cache存儲(chǔ)系例子本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>Cache性能評(píng)價(jià)問：一個(gè)由8KB的I-Cache和8KB的D-Cache所構(gòu)成的分立Cache（哈佛結(jié)構(gòu)）與一個(gè)16KB的統(tǒng)一Cache哪一個(gè)具有更低的缺失率？假設(shè)命中所需的開銷為1個(gè)時(shí)鐘周期，不命中的開銷為50個(gè)時(shí)鐘周期，統(tǒng)一Cache的load或store命中需花費(fèi)1個(gè)時(shí)鐘周期的額外開銷。75%的存儲(chǔ)器存取是指令訪問。Cache大小I-Cache缺失率D-Cache缺失率統(tǒng)一Cache缺失率4KB1.78%15.94%7.24%8KB1.10%10.19%4.57%16KB0.64%6.47%2.87%32KB0.39%4.82%1.99%3之2例子本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>答：分立Cache的整體缺失率為：由表中可知，16KB的統(tǒng)一Cache的缺失率為2.87%。因此，統(tǒng)一Cache結(jié)構(gòu)具有較低的缺失率。盡管分立Cache具有較高的缺失率，但其AMAT與統(tǒng)一Cache的AMAT是基本相同的，可見哈佛結(jié)構(gòu)有優(yōu)勢(shì)。大多數(shù)現(xiàn)代處理器都采用分立Cache技術(shù)。例子（續(xù)）本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>Cache性能評(píng)價(jià)3之3答：分立Cache的整體缺失率為：例子（續(xù)）本章內(nèi)容>>提高Cache性能本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能可見主要途徑有：

降低缺失代價(jià)

降低缺失率

通過并行性降低缺失代價(jià)/缺失率

降低Cache命中時(shí)間提高Cache性能本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cac降低缺失代價(jià)本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能多級(jí)Cache關(guān)鍵字優(yōu)先和提前重啟動(dòng)給出讀缺失對(duì)寫的優(yōu)先級(jí)合并寫緩沖區(qū)犧牲者Cache降低缺失代價(jià)本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性多級(jí)Cache本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能>>降低缺失代價(jià)基本思想性能分析設(shè)計(jì)考慮多級(jí)Cache本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache基本思想本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能>>降低缺失代價(jià)>>多級(jí)Cache通過在原始Cache和存儲(chǔ)器之間增加另一級(jí)Cache，第一級(jí)Cache可以小到足以跟上飛快的CPU，而第二級(jí)Cache能夠大到足以捕捉到對(duì)主存進(jìn)行的大多數(shù)訪問，因而可以減少有效缺失代價(jià)?；舅枷氡菊聝?nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>性能分析本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能>>降低缺失代價(jià)>>多級(jí)Cache局部缺失率本級(jí)Cache的缺失數(shù)除以對(duì)本級(jí)Cache的存儲(chǔ)器訪問總數(shù)。例如：第一級(jí)Cache的局部缺失率為缺失率L1，第二級(jí)Cache的局部缺失率為缺失率L2全局缺失率本級(jí)Cache的缺失數(shù)除以CPU產(chǎn)生的存儲(chǔ)器訪問總數(shù)。例如：第一級(jí)Cache的全局缺失率為缺失率L1，第二級(jí)Cache的全局缺失率為缺失率L1×缺失率L2。性能分析本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>設(shè)計(jì)考慮本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能>>降低缺失代價(jià)>>多級(jí)Cache第二級(jí)Cache的容量？采用大容量設(shè)計(jì)。因?yàn)榈谝患?jí)Cache中的所有信息都可能會(huì)出現(xiàn)在第二級(jí)Cache中，所以第二級(jí)Cache應(yīng)該比第一級(jí)Cache大得多。如果第二級(jí)Cache只是稍微大一點(diǎn)，則局部缺失率會(huì)很高。第二級(jí)Cache采用組相聯(lián)映射還是直接映射？采用組相聯(lián)映射比采用直接映射性能要好。2之1設(shè)計(jì)考慮本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>設(shè)計(jì)考慮本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能>>降低缺失代價(jià)>>多級(jí)Cache2之2是否第一級(jí)Cache中所有數(shù)據(jù)都包含在第二級(jí)Cache中？ 有兩種方案：多級(jí)包含 L1中的數(shù)據(jù)通常都出現(xiàn)在L2中。這是通常做法。多級(jí)排除L1中的數(shù)據(jù)從不會(huì)出現(xiàn)在L2中。當(dāng)L2Cache容量略大于L1Cache時(shí)可以采用此法，不浪費(fèi)L2Cache的空間。設(shè)計(jì)考慮本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>關(guān)鍵字優(yōu)先和提前重啟動(dòng)思想因?yàn)镃PU在同一時(shí)刻只需要塊中的一個(gè)字，所以本技術(shù)不必等到全部塊裝入就可以將所需字送出，然后重新啟動(dòng)CPU。方法關(guān)鍵字優(yōu)先首先向存儲(chǔ)器請(qǐng)求缺失的字，一旦它到了就將它發(fā)送到CPU中；讓CPU繼續(xù)執(zhí)行，同時(shí)裝入塊中的其他字。本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能>>降低缺失代價(jià)提前重啟動(dòng)按正常次序獲取字，只要被請(qǐng)求的字一到達(dá)就將它發(fā)送到CPU中，讓CPU繼續(xù)執(zhí)行。2之1關(guān)鍵字優(yōu)先和提前重啟動(dòng)思想關(guān)鍵字優(yōu)先本章內(nèi)容>>C局限性本技術(shù)的收益取決于塊的大?。▔K越大，收益越大）和對(duì)塊中未裝入部分的訪問可能性。本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能>>降低缺失代價(jià)2之2局限性本技術(shù)的收益取決于塊的大小（塊越大，收給出讀缺失對(duì)寫的優(yōu)先級(jí)本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能>>降低缺失代價(jià)問題對(duì)于一個(gè)寫直達(dá)的Cache，需要設(shè)置容量適中的寫緩沖區(qū)（見后圖）。然而寫緩沖區(qū)使得存儲(chǔ)器訪問變的復(fù)雜，因?yàn)槠渲锌赡馨x缺失時(shí)所需要的更新數(shù)據(jù)。SWR3,512(R0);M[512]←R3(CacheIndex0)LWR1,1024(R0);R1←M[1024](CacheIndex0)LWR2,512(R0);R2←M[512](CacheIndex0)R2≠R3？！3之1給出讀缺失對(duì)寫的優(yōu)先級(jí)本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>C給出讀缺失對(duì)寫的優(yōu)先級(jí)本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能>>降低缺失代價(jià)writebufferCPUinout

DRAM(orlowermem)3之2給出讀缺失對(duì)寫的優(yōu)先級(jí)本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>C給出讀缺失對(duì)寫的優(yōu)先級(jí)本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能>>降低缺失代價(jià)解決最簡(jiǎn)單的解決方法：讀缺失等待，直到寫緩沖區(qū)為空為止；但該方法會(huì)增加讀缺失代價(jià)。另一種解決方法：在讀缺失時(shí)查看寫緩沖區(qū)中的內(nèi)容，如果沒有沖突而且存儲(chǔ)器系統(tǒng)可以訪問，就讓讀缺失繼續(xù)；即：使讀缺失優(yōu)先于寫缺失。3之3在寫回法的Cache中，在替換塊時(shí)也要使用一個(gè)簡(jiǎn)單的寫緩沖，同樣處理。給出讀缺失對(duì)寫的優(yōu)先級(jí)本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>C合并寫緩沖區(qū)本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能>>降低缺失代價(jià)思想在寫緩沖區(qū)中，將多個(gè)連續(xù)的數(shù)據(jù)組合起來，加快存儲(chǔ)器的寫速度。合并寫緩沖區(qū)本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性犧牲者Cache本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能>>降低缺失代價(jià)思想在Cache和它的替換路徑之間增加一個(gè)小的、全相聯(lián)的Cache（犧牲者Cache），這個(gè)犧牲者Cache中只包含Cache中因?yàn)槿笔Ф惶鎿Q出的塊（犧牲者），然后在缺失發(fā)生時(shí)，在要訪問下層存儲(chǔ)器之前，先檢查犧牲者Cache，看其中是否包含有期望的數(shù)據(jù)，如果有，則犧牲塊與Cache塊互換（見后圖）。性能依賴于特定的程序，一個(gè)包含4個(gè)存儲(chǔ)字的犧牲者Cache能減少20%～90%的沖突缺失。2之1犧牲者Cache本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cach犧牲者Cache本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能>>降低缺失代價(jià)2之2犧牲者Cache本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cach降低缺失率本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能導(dǎo)致缺失的原因降低缺失率的技術(shù)增加塊容量增加Cache容量增加相聯(lián)度路預(yù)測(cè)和偽相聯(lián)Cache編譯優(yōu)化降低缺失率本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能導(dǎo)致缺失的原因本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能>>降低缺失率

強(qiáng)制（Compulsory）缺失對(duì)一個(gè)塊的第一次訪問一定不在Cache中，所以該塊必須被調(diào)入到Cache中（這也稱為：冷啟動(dòng)缺失、首次訪問缺失等）。

容量（Capacity）缺失如果Cache容納不了一個(gè)程序持續(xù)執(zhí)行所需要的所有塊，將會(huì)發(fā)生容量缺失，某些塊將被放棄，隨后再被調(diào)入。沖突（Conflict）缺失如果采用組相聯(lián)/直接相聯(lián)，則可能有多個(gè)塊映射到同一塊中，發(fā)生沖突缺失。4之1導(dǎo)致缺失的原因本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache3Cs總?cè)笔蔛PEC92；32Bblocks；LRU；DECstation5000；本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能>>降低缺失率4之2MissRateperType0.020.040.060.080.10.120.14CacheSize(KB)

01248163264128Compulsory

Capacity

4-way2-way1-way8-wayConflict3Cs總?cè)笔蔛PEC92；本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)2:1Cache經(jīng)驗(yàn)規(guī)律一個(gè)容量為N的直接映射Cache同容量為N/2的2-路組相聯(lián)Cache有著大致相同的總?cè)笔省?/p>

本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能>>降低缺失率4之3Conflict2:1Cache經(jīng)驗(yàn)規(guī)律一個(gè)容量為N的直接映射Cac3Cs缺失率分布本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能>>降低缺失率4之4Conflict3Cs缺失率分布本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cach增加塊容量五種不同容量Cache的缺失率與塊容量的關(guān)系本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能>>降低缺失率0.49%1.15%3.29%9.51%22.01%2560.49%1.02%2.77%7.78%16.64%1280.51%1.06%2.64%7.00%13.76%640.70%1.35%2.87%7.24%13.34%321.09%2.04%3.94%8.57%15.05%16256641641Cachesize(KB)Blocksize(B)5之1增加塊容量五種不同容量Cache的缺失率與塊容量的關(guān)系本章內(nèi)增加塊容量本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能>>降低缺失率1K4K16K64K256KCacheSizeBlockSize(bytes)MissRate

0%5%10%15%20%25%1632641282565之2增加塊容量本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能分析增加塊容量會(huì)降低/增加缺失率增加塊容量會(huì)降低強(qiáng)制缺失率，這是利用了空間局部性原理。但因?yàn)樗鼫p少了Cache中的塊數(shù)，加重了沖突缺失，如果Cache容量較小時(shí)，甚至?xí)腥萘咳笔?。增加塊容量會(huì)增加缺失代價(jià)本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能>>降低缺失率塊容量應(yīng)為多大AMAT最小？5之3分析增加塊容量會(huì)降低/增加缺失率本章內(nèi)容>>CacAMAT與塊容量本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能>>降低缺失率假設(shè)命中時(shí)間為1個(gè)時(shí)鐘周期，缺失時(shí)系統(tǒng)開銷為80個(gè)時(shí)鐘周期，以后每2個(gè)時(shí)鐘周期傳送16B，缺失率參見前表。結(jié)果顯示：32/64B是目前Cache所通用的塊容量。5之4AMAT與塊容量本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cach塊容量的選擇本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能>>降低缺失率5之5

塊容量的選擇取決于較低層存儲(chǔ)器的延遲和帶寬：低延遲和高帶寬存儲(chǔ)器使得塊容量要大些，因?yàn)檫@樣在每次缺失時(shí)Cache可以獲得更多的字節(jié)，而缺失代價(jià)只有少量的增加；相反，高延遲和低帶寬存儲(chǔ)器希望塊容量要小些，因?yàn)檩^大的塊并不能節(jié)省多少時(shí)間。塊容量的選擇本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性增加Cache容量本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能>>降低缺失率增加Cache容量可以降低容量缺失，但增加了命中時(shí)間和成本。這種技術(shù)在片外Cache中很通用。增加Cache容量本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cac增加相聯(lián)度本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能>>降低缺失率增加相聯(lián)度會(huì)降低缺失率MissRateperType0.020.040.060.080.10.120.14CacheSize(KB)

01248163264128Compulsory

Capacity

4-way2-way1-way8-wayConflict3之1增加相聯(lián)度本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能增加相聯(lián)度本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能>>降低缺失率增加相聯(lián)度會(huì)增加命中時(shí)間3之2增加相聯(lián)度本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能AMAT與相聯(lián)度本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能>>降低缺失率實(shí)驗(yàn)結(jié)果顯示：較高的相聯(lián)度增加了AMAT。3之3AMAT與相聯(lián)度本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cach路預(yù)測(cè)本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能>>降低缺失率思想在Cache中設(shè)置一些特殊位來預(yù)測(cè)下次Cache訪問中可能會(huì)在組中用到的路/塊。特點(diǎn)在降低沖突缺失的同時(shí)，保持直接映象Cache的命中速度。例子Alpha21264在2-路組相聯(lián)指令Cache使用路預(yù)測(cè)，SPEC95仿真結(jié)果顯示：預(yù)測(cè)正確率超過85%。3之1路預(yù)測(cè)本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>偽相聯(lián)Cache本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能>>降低缺失率思想在命中時(shí)，偽相聯(lián)Cache訪問過程同直接映象Cache（命中時(shí)間）；但當(dāng)缺失發(fā)生時(shí)，在訪問下層存儲(chǔ)器之前（缺失代價(jià)），通過檢查另外一個(gè)Cache塊來看看是否在那里命中（偽命中時(shí)間）。3之2偽相聯(lián)Cache本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cach偽相聯(lián)Cache本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能>>降低缺失率特點(diǎn)偽相聯(lián)Cache的AMAT短，但變化的命中時(shí)間會(huì)使流水線CPU設(shè)計(jì)復(fù)雜度增加，因此較適合用于離CPU較遠(yuǎn)的Cache中，例如：L2Caches。這兩個(gè)技術(shù)都綜合了1-路組相聯(lián)（直接相聯(lián)）的命中時(shí)間短和2-路組相聯(lián)的沖突低。3之3偽相聯(lián)Cache本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cach編譯優(yōu)化本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能>>降低缺失率指令缺失性能改善在不影響正確性的前提下重新安排程序代碼，可能會(huì)降低沖突缺失，從而降低指令缺失率。例如：McFarling[1989]在容量2KB、塊容量4B的直接相聯(lián)Cache中使用本方法將Cache的缺失率降低50%，若Cache容量為8KB，則缺失率降低75%。編譯優(yōu)化本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>編譯優(yōu)化本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能>>降低缺失率數(shù)據(jù)缺失性能改善數(shù)據(jù)比指令代碼在位置上的限制甚至更少，這些變換的目標(biāo)是盡力提高數(shù)據(jù)的空間和時(shí)間局部性。下面通過3個(gè)例子進(jìn)行介紹：循環(huán)交換循環(huán)融合分塊編譯優(yōu)化本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>循環(huán)交換一些程序帶有嵌套循環(huán)，它們?cè)L問存儲(chǔ)器中的數(shù)據(jù)是非順序的，簡(jiǎn)單的交換嵌套循環(huán)可以使得代碼按照存儲(chǔ)順序來訪問數(shù)據(jù)。/*Before*/for(k=0;k<100;k=k+1)

for(j=0;j<100;j=j+1) for(i=0;i<5000;i=i+1) x[i][j]=2*x[i][j];/*After*/for(k=0;k<100;k=k+1)

for(i=0;i<5000;i=i+1) for(j=0;j<100;j=j+1) x[i][j]=2*x[i][j];本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能>>降低缺失率>>編譯優(yōu)化通過提高空間局部性來減少缺失。循環(huán)交換一些程序帶有嵌套循環(huán)，它們?cè)L問存儲(chǔ)器中的數(shù)據(jù)循環(huán)融合本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能>>降低缺失率>>編譯優(yōu)化一些程序有分立的代碼段，這些代碼按照相同的循環(huán)訪問相同的數(shù)組，對(duì)相同的數(shù)據(jù)進(jìn)行不同的計(jì)算。通過“融合”這些代碼到一個(gè)循環(huán)中，使得裝入到Cache中的數(shù)據(jù)在被替換出來之前可以被重復(fù)地利用。2之1循環(huán)融合本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>循環(huán)融合/*Before*/for(i=0;i<N;i=i+1)for(j=0;j<N;j=j+1)

a[i][j]=1/b[i][j]*c[i][j];for(i=0;i<N;i=i+1)for(j=0;j<N;j=j+1) d[i][j]=a[i][j]+c[i][j];/*After*/for(i=0;i<N;i=i+1)for(j=0;j<N;j=j+1) {

a[i][j]=1/b[i][j]*c[i][j]; d[i][j]=a[i][j]+c[i][j];}本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能>>降低缺失率>>編譯優(yōu)化通過提高時(shí)間局部性來減少缺失。2之2循環(huán)融合/*Before*//*After*/本章內(nèi)分塊本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能>>降低缺失率>>編譯優(yōu)化分塊不是對(duì)矩陣中的整行/列進(jìn)行操作，而是對(duì)子矩陣或矩陣塊進(jìn)行操作，目標(biāo)是在調(diào)入到Cache中的塊被替換之前最大限度地利用它。3之1分塊本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>分塊本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能>>降低缺失率>>編譯優(yōu)化/*Before*/for(i=0;i<N;i=i+1) for(j=0;j<N;j=j+1) {r=0; for(k=0;k<N;k=k+1)r=r+y[i][k]*z[k][j];x[i][j]=r;};X[]ijY[]ikZ[]kjNeweraccessesOlderaccessesi循環(huán)一次，要讀取矩陣z的所有N×N個(gè)元素，對(duì)矩陣y一行中的N個(gè)元素進(jìn)行重復(fù)訪問，對(duì)矩陣x一行中的N個(gè)元素進(jìn)行寫操作。3之2分塊本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>分塊/*After*/for(jj=0;jj<N;jj=jj+B) for(kk=0;kk<N;kk=kk+B) for(i=0;i<N;i=i+1) for(j=jj;j<min(jj+B-1,N);j=j+1) {r=0; for(k=kk;k<min(kk+B-1,N);k=k+1)r=r+y[i][k]*z[k][j]; x[i][j]=x[i][j]+r;}B為分塊因子，B×B子矩陣都在Cache中。本技術(shù)是通過提高空間和時(shí)間局部性來減少缺失。本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能>>降低缺失率>>編譯優(yōu)化3之3分塊/*After*/B為分塊因子，B×B子矩陣通過并行性降低缺失代價(jià)/缺失率

本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能用非阻塞Cache減少Cache缺失暫停指令和數(shù)據(jù)硬件預(yù)取編譯控制的預(yù)取通過并行性降低缺失代價(jià)/缺失率本章內(nèi)容>>Cache存儲(chǔ)指令和數(shù)據(jù)硬件預(yù)取本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能>>通過并行性降低缺失代價(jià)/缺失率思想在處理器訪問指令和數(shù)據(jù)之前就將它們預(yù)取到Cache或預(yù)取到可以比主存訪問速度更快的外部緩沖區(qū)中。提示預(yù)取技術(shù)依賴于存儲(chǔ)器帶寬，編譯器可以幫助減少不必要的預(yù)取。2之1指令和數(shù)據(jù)硬件預(yù)取本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cac例:指令硬件預(yù)取本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能>>通過并行性降低缺失代價(jià)/缺失率例子

AXP21064微處理器在缺失時(shí)取兩個(gè)塊：被請(qǐng)求的塊和其后緊挨著的塊。被請(qǐng)求的塊裝入到指令Cache中，而預(yù)取的塊被裝入到指令流緩沖區(qū)中。如果被請(qǐng)求塊在指令流緩沖區(qū)中找到，則原Cache請(qǐng)求被取消，塊被從流緩沖區(qū)中讀入，然后下一個(gè)預(yù)取請(qǐng)求被發(fā)出。性能

Jouppi[1990]研究發(fā)現(xiàn)：對(duì)于容量為4KB、塊容量為16B的直接映象指令Cache來說，單個(gè)的指令流緩沖區(qū)可以捕捉到15%～25%的缺失；如指令流緩沖區(qū)中可保存4個(gè)塊，命中率提高到大約50%，保存16個(gè)塊提高到72%。2之2例:指令硬件預(yù)取本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cach編譯控制的預(yù)取本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能>>通過并行性降低缺失代價(jià)/缺失率思想利用編譯器來插入預(yù)取指令，提前發(fā)出數(shù)據(jù)請(qǐng)求，可以將數(shù)據(jù)預(yù)取到寄存器（寄存器預(yù)取，例如：HPPA-RISC）或?qū)?shù)據(jù)預(yù)取到Cache（Cache預(yù)取，例如：MIPSIV、PowerPC、SPARCv.9）。提示循環(huán)是重要的目標(biāo)；而且生成預(yù)取指令需要時(shí)間，必須注意這些開銷不能超過收益。編譯控制的預(yù)取本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache降低Cache命中時(shí)間

本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能小而簡(jiǎn)單的Cache在Cache索引過程中避免地址變換

流水Cache存取

跟蹤C(jī)ache降低Cache命中時(shí)間本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>三級(jí)存儲(chǔ)系統(tǒng)本章內(nèi)容存儲(chǔ)系統(tǒng)的組織方式：兩個(gè)存儲(chǔ)系統(tǒng)的組織方式一個(gè)存儲(chǔ)系統(tǒng)的組織方式全Cache存儲(chǔ)系統(tǒng)三級(jí)存儲(chǔ)系統(tǒng)本章內(nèi)容存儲(chǔ)系統(tǒng)的組織方式：兩個(gè)存儲(chǔ)系統(tǒng)的

組織方式本章內(nèi)容>>三級(jí)存儲(chǔ)系統(tǒng)有“Cache-主存”和“主存-磁盤”兩個(gè)獨(dú)立的存儲(chǔ)系統(tǒng)，這種結(jié)構(gòu)也稱為物理地址Cache存儲(chǔ)系統(tǒng)。目前的大部分處理機(jī)均采用這種兩級(jí)存儲(chǔ)系統(tǒng)。CPU虛擬

地址MMUCache主存

儲(chǔ)器物理

地址數(shù)據(jù)或指令物理地址CPU虛擬

地址MMUCache主存

儲(chǔ)器物理

地址數(shù)據(jù)或指令物理地址存儲(chǔ)管理部件兩個(gè)存儲(chǔ)系統(tǒng)的

組織方式本章內(nèi)容>>三級(jí)存儲(chǔ)系統(tǒng)一個(gè)存儲(chǔ)系統(tǒng)的

組織方式本章內(nèi)容>>三級(jí)存儲(chǔ)系統(tǒng)將Cache、主存和磁盤組織在一起構(gòu)成一個(gè)“Cache-主存-磁盤”存儲(chǔ)系統(tǒng)，這種結(jié)構(gòu)也稱為虛擬地址Cache存儲(chǔ)系統(tǒng)。如Intel公司的i860等處理機(jī)采用這種組織方式。CPU虛擬地址MMUCache主存

儲(chǔ)器數(shù)據(jù)或指令物理

地址數(shù)據(jù)

或指令一個(gè)存儲(chǔ)系統(tǒng)的

組織方式本章內(nèi)容>>三級(jí)存儲(chǔ)系統(tǒng)全Cache存儲(chǔ)系統(tǒng)本章內(nèi)容>>三級(jí)存儲(chǔ)系統(tǒng)沒有主存儲(chǔ)器，只用Cache和磁盤構(gòu)成“Cache－磁盤”存儲(chǔ)系統(tǒng)。例如：多處理機(jī)中的全Cache存儲(chǔ)系統(tǒng)。全Cache存儲(chǔ)系統(tǒng)本章內(nèi)容>>三級(jí)存儲(chǔ)系統(tǒng)作業(yè)本章內(nèi)容理解基本思想！作業(yè)本章內(nèi)容理解基本思想！Cache性能評(píng)價(jià)提高Cache性能Cache性能本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)Cache性能評(píng)價(jià)Cache性能本章內(nèi)容>>Cache存儲(chǔ)Cache性能評(píng)價(jià)本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能CPU執(zhí)行時(shí)間平均存儲(chǔ)器訪問時(shí)間（AMAT）Cache性能評(píng)價(jià)本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>CacCPU執(zhí)行時(shí)間本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>Cache性能評(píng)價(jià)其中：3之1CPU執(zhí)行時(shí)間本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache例子本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>Cache性能評(píng)價(jià)問：假定有一臺(tái)計(jì)算機(jī)，當(dāng)所有存儲(chǔ)器訪問操作都能在Cache中命中時(shí)，CPI為1.0；數(shù)據(jù)訪問只有l(wèi)oad和store指令，這些指令占全部指令的50%；缺失代價(jià)為25個(gè)時(shí)鐘周期，缺失率為2%。問當(dāng)所有指令都在Cache中命中時(shí)，計(jì)算機(jī)性能能提高多少？答：Cache始終命中時(shí)的計(jì)算機(jī)性能為：3之2例子本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>例子（續(xù)）本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>Cache性能評(píng)價(jià)實(shí)際Cache的計(jì)算機(jī)性能為：兩者的性能比為：結(jié)論：不發(fā)生Cache缺失時(shí)計(jì)算機(jī)性能是原來的1.75倍3之3例子（續(xù)）本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache平均存儲(chǔ)器訪問時(shí)間（AMAT）本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>Cache性能評(píng)價(jià)3之1平均存儲(chǔ)器訪問時(shí)間（AMAT）本章內(nèi)容>>Cache存儲(chǔ)系例子本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>Cache性能評(píng)價(jià)問：一個(gè)由8KB的I-Cache和8KB的D-Cache所構(gòu)成的分立Cache（哈佛結(jié)構(gòu)）與一個(gè)16KB的統(tǒng)一Cache哪一個(gè)具有更低的缺失率？假設(shè)命中所需的開銷為1個(gè)時(shí)鐘周期，不命中的開銷為50個(gè)時(shí)鐘周期，統(tǒng)一Cache的load或store命中需花費(fèi)1個(gè)時(shí)鐘周期的額外開銷。75%的存儲(chǔ)器存取是指令訪問。Cache大小I-Cache缺失率D-Cache缺失率統(tǒng)一Cache缺失率4KB1.78%15.94%7.24%8KB1.10%10.19%4.57%16KB0.64%6.47%2.87%32KB0.39%4.82%1.99%3之2例子本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>答：分立Cache的整體缺失率為：由表中可知，16KB的統(tǒng)一Cache的缺失率為2.87%。因此，統(tǒng)一Cache結(jié)構(gòu)具有較低的缺失率。盡管分立Cache具有較高的缺失率，但其AMAT與統(tǒng)一Cache的AMAT是基本相同的，可見哈佛結(jié)構(gòu)有優(yōu)勢(shì)。大多數(shù)現(xiàn)代處理器都采用分立Cache技術(shù)。例子（續(xù)）本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>Cache性能評(píng)價(jià)3之3答：分立Cache的整體缺失率為：例子（續(xù)）本章內(nèi)容>>提高Cache性能本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能可見主要途徑有：

降低缺失代價(jià)

降低缺失率

通過并行性降低缺失代價(jià)/缺失率

降低Cache命中時(shí)間提高Cache性能本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cac降低缺失代價(jià)本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能多級(jí)Cache關(guān)鍵字優(yōu)先和提前重啟動(dòng)給出讀缺失對(duì)寫的優(yōu)先級(jí)合并寫緩沖區(qū)犧牲者Cache降低缺失代價(jià)本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性多級(jí)Cache本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能>>降低缺失代價(jià)基本思想性能分析設(shè)計(jì)考慮多級(jí)Cache本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache基本思想本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能>>降低缺失代價(jià)>>多級(jí)Cache通過在原始Cache和存儲(chǔ)器之間增加另一級(jí)Cache，第一級(jí)Cache可以小到足以跟上飛快的CPU，而第二級(jí)Cache能夠大到足以捕捉到對(duì)主存進(jìn)行的大多數(shù)訪問，因而可以減少有效缺失代價(jià)?；舅枷氡菊聝?nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>性能分析本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能>>降低缺失代價(jià)>>多級(jí)Cache局部缺失率本級(jí)Cache的缺失數(shù)除以對(duì)本級(jí)Cache的存儲(chǔ)器訪問總數(shù)。例如：第一級(jí)Cache的局部缺失率為缺失率L1，第二級(jí)Cache的局部缺失率為缺失率L2全局缺失率本級(jí)Cache的缺失數(shù)除以CPU產(chǎn)生的存儲(chǔ)器訪問總數(shù)。例如：第一級(jí)Cache的全局缺失率為缺失率L1，第二級(jí)Cache的全局缺失率為缺失率L1×缺失率L2。性能分析本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>設(shè)計(jì)考慮本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能>>降低缺失代價(jià)>>多級(jí)Cache第二級(jí)Cache的容量？采用大容量設(shè)計(jì)。因?yàn)榈谝患?jí)Cache中的所有信息都可能會(huì)出現(xiàn)在第二級(jí)Cache中，所以第二級(jí)Cache應(yīng)該比第一級(jí)Cache大得多。如果第二級(jí)Cache只是稍微大一點(diǎn)，則局部缺失率會(huì)很高。第二級(jí)Cache采用組相聯(lián)映射還是直接映射？采用組相聯(lián)映射比采用直接映射性能要好。2之1設(shè)計(jì)考慮本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>設(shè)計(jì)考慮本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能>>降低缺失代價(jià)>>多級(jí)Cache2之2是否第一級(jí)Cache中所有數(shù)據(jù)都包含在第二級(jí)Cache中？ 有兩種方案：多級(jí)包含 L1中的數(shù)據(jù)通常都出現(xiàn)在L2中。這是通常做法。多級(jí)排除L1中的數(shù)據(jù)從不會(huì)出現(xiàn)在L2中。當(dāng)L2Cache容量略大于L1Cache時(shí)可以采用此法，不浪費(fèi)L2Cache的空間。設(shè)計(jì)考慮本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>關(guān)鍵字優(yōu)先和提前重啟動(dòng)思想因?yàn)镃PU在同一時(shí)刻只需要塊中的一個(gè)字，所以本技術(shù)不必等到全部塊裝入就可以將所需字送出，然后重新啟動(dòng)CPU。方法關(guān)鍵字優(yōu)先首先向存儲(chǔ)器請(qǐng)求缺失的字，一旦它到了就將它發(fā)送到CPU中；讓CPU繼續(xù)執(zhí)行，同時(shí)裝入塊中的其他字。本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能>>降低缺失代價(jià)提前重啟動(dòng)按正常次序獲取字，只要被請(qǐng)求的字一到達(dá)就將它發(fā)送到CPU中，讓CPU繼續(xù)執(zhí)行。2之1關(guān)鍵字優(yōu)先和提前重啟動(dòng)思想關(guān)鍵字優(yōu)先本章內(nèi)容>>C局限性本技術(shù)的收益取決于塊的大?。▔K越大，收益越大）和對(duì)塊中未裝入部分的訪問可能性。本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能>>降低缺失代價(jià)2之2局限性本技術(shù)的收益取決于塊的大?。▔K越大，收給出讀缺失對(duì)寫的優(yōu)先級(jí)本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能>>降低缺失代價(jià)問題對(duì)于一個(gè)寫直達(dá)的Cache，需要設(shè)置容量適中的寫緩沖區(qū)（見后圖）。然而寫緩沖區(qū)使得存儲(chǔ)器訪問變的復(fù)雜，因?yàn)槠渲锌赡馨x缺失時(shí)所需要的更新數(shù)據(jù)。SWR3,512(R0);M[512]←R3(CacheIndex0)LWR1,1024(R0);R1←M[1024](CacheIndex0)LWR2,512(R0);R2←M[512](CacheIndex0)R2≠R3？！3之1給出讀缺失對(duì)寫的優(yōu)先級(jí)本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>C給出讀缺失對(duì)寫的優(yōu)先級(jí)本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能>>降低缺失代價(jià)writebufferCPUinout

DRAM(orlowermem)3之2給出讀缺失對(duì)寫的優(yōu)先級(jí)本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>C給出讀缺失對(duì)寫的優(yōu)先級(jí)本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能>>降低缺失代價(jià)解決最簡(jiǎn)單的解決方法：讀缺失等待，直到寫緩沖區(qū)為空為止；但該方法會(huì)增加讀缺失代價(jià)。另一種解決方法：在讀缺失時(shí)查看寫緩沖區(qū)中的內(nèi)容，如果沒有沖突而且存儲(chǔ)器系統(tǒng)可以訪問，就讓讀缺失繼續(xù)；即：使讀缺失優(yōu)先于寫缺失。3之3在寫回法的Cache中，在替換塊時(shí)也要使用一個(gè)簡(jiǎn)單的寫緩沖，同樣處理。給出讀缺失對(duì)寫的優(yōu)先級(jí)本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>C合并寫緩沖區(qū)本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能>>降低缺失代價(jià)思想在寫緩沖區(qū)中，將多個(gè)連續(xù)的數(shù)據(jù)組合起來，加快存儲(chǔ)器的寫速度。合并寫緩沖區(qū)本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性犧牲者Cache本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能>>降低缺失代價(jià)思想在Cache和它的替換路徑之間增加一個(gè)小的、全相聯(lián)的Cache（犧牲者Cache），這個(gè)犧牲者Cache中只包含Cache中因?yàn)槿笔Ф惶鎿Q出的塊（犧牲者），然后在缺失發(fā)生時(shí)，在要訪問下層存儲(chǔ)器之前，先檢查犧牲者Cache，看其中是否包含有期望的數(shù)據(jù)，如果有，則犧牲塊與Cache塊互換（見后圖）。性能依賴于特定的程序，一個(gè)包含4個(gè)存儲(chǔ)字的犧牲者Cache能減少20%～90%的沖突缺失。2之1犧牲者Cache本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cach犧牲者Cache本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能>>降低缺失代價(jià)2之2犧牲者Cache本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cach降低缺失率本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能導(dǎo)致缺失的原因降低缺失率的技術(shù)增加塊容量增加Cache容量增加相聯(lián)度路預(yù)測(cè)和偽相聯(lián)Cache編譯優(yōu)化降低缺失率本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能導(dǎo)致缺失的原因本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能>>降低缺失率

強(qiáng)制（Compulsory）缺失對(duì)一個(gè)塊的第一次訪問一定不在Cache中，所以該塊必須被調(diào)入到Cache中（這也稱為：冷啟動(dòng)缺失、首次訪問缺失等）。

容量（Capacity）缺失如果Cache容納不了一個(gè)程序持續(xù)執(zhí)行所需要的所有塊，將會(huì)發(fā)生容量缺失，某些塊將被放棄，隨后再被調(diào)入。沖突（Conflict）缺失如果采用組相聯(lián)/直接相聯(lián)，則可能有多個(gè)塊映射到同一塊中，發(fā)生沖突缺失。4之1導(dǎo)致缺失的原因本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache3Cs總?cè)笔蔛PEC92；32Bblocks；LRU；DECstation5000；本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能>>降低缺失率4之2MissRateperType0.020.040.060.080.10.120.14CacheSize(KB)

01248163264128Compulsory

Capacity

4-way2-way1-way8-wayConflict3Cs總?cè)笔蔛PEC92；本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)2:1Cache經(jīng)驗(yàn)規(guī)律一個(gè)容量為N的直接映射Cache同容量為N/2的2-路組相聯(lián)Cache有著大致相同的總?cè)笔省?/p>

本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能>>降低缺失率4之3Conflict2:1Cache經(jīng)驗(yàn)規(guī)律一個(gè)容量為N的直接映射Cac3Cs缺失率分布本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能>>降低缺失率4之4Conflict3Cs缺失率分布本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cach增加塊容量五種不同容量Cache的缺失率與塊容量的關(guān)系本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能>>降低缺失率0.49%1.15%3.29%9.51%22.01%2560.49%1.02%2.77%7.78%16.64%1280.51%1.06%2.64%7.00%13.76%640.70%1.35%2.87%7.24%13.34%321.09%2.04%3.94%8.57%15.05%16256641641Cachesize(KB)Blocksize(B)5之1增加塊容量五種不同容量Cache的缺失率與塊容量的關(guān)系本章內(nèi)增加塊容量本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能>>降低缺失率1K4K16K64K256KCacheSizeBlockSize(bytes)MissRate

0%5%10%15%20%25%1632641282565之2增加塊容量本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能分析增加塊容量會(huì)降低/增加缺失率增加塊容量會(huì)降低強(qiáng)制缺失率，這是利用了空間局部性原理。但因?yàn)樗鼫p少了Cache中的塊數(shù)，加重了沖突缺失，如果Cache容量較小時(shí)，甚至?xí)腥萘咳笔?。增加塊容量會(huì)增加缺失代價(jià)本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能>>降低缺失率塊容量應(yīng)為多大AMAT最??？5之3分析增加塊容量會(huì)降低/增加缺失率本章內(nèi)容>>CacAMAT與塊容量本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能>>降低缺失率假設(shè)命中時(shí)間為1個(gè)時(shí)鐘周期，缺失時(shí)系統(tǒng)開銷為80個(gè)時(shí)鐘周期，以后每2個(gè)時(shí)鐘周期傳送16B，缺失率參見前表。結(jié)果顯示：32/64B是目前Cache所通用的塊容量。5之4AMAT與塊容量本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cach塊容量的選擇本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能>>降低缺失率5之5

塊容量的選擇取決于較低層存儲(chǔ)器的延遲和帶寬：低延遲和高帶寬存儲(chǔ)器使得塊容量要大些，因?yàn)檫@樣在每次缺失時(shí)Cache可以獲得更多的字節(jié)，而缺失代價(jià)只有少量的增加；相反，高延遲和低帶寬存儲(chǔ)器希望塊容量要小些，因?yàn)檩^大的塊并不能節(jié)省多少時(shí)間。塊容量的選擇本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性增加Cache容量本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能>>降低缺失率增加Cache容量可以降低容量缺失，但增加了命中時(shí)間和成本。這種技術(shù)在片外Cache中很通用。增加Cache容量本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cac增加相聯(lián)度本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能>>降低缺失率增加相聯(lián)度會(huì)降低缺失率MissRateperType0.020.040.060.080.10.120.14CacheSize(KB)

01248163264128Compulsory

Capacity

4-way2-way1-way8-wayConflict3之1增加相聯(lián)度本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能增加相聯(lián)度本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能>>降低缺失率增加相聯(lián)度會(huì)增加命中時(shí)間3之2增加相聯(lián)度本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能AMAT與相聯(lián)度本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能>>降低缺失率實(shí)驗(yàn)結(jié)果顯示：較高的相聯(lián)度增加了AMAT。3之3AMAT與相聯(lián)度本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cach路預(yù)測(cè)本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能>>降低缺失率思想在Cache中設(shè)置一些特殊位來預(yù)測(cè)下次Cache訪問中可能會(huì)在組中用到的路/塊。特點(diǎn)在降低沖突缺失的同時(shí)，保持直接映象Cache的命中速度。例子Alpha21264在2-路組相聯(lián)指令Cache使用路預(yù)測(cè)，SPEC95仿真結(jié)果顯示：預(yù)測(cè)正確率超過85%。3之1路預(yù)測(cè)本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>偽相聯(lián)Cache本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能>>降低缺失率思想在命中時(shí)，偽相聯(lián)Cache訪問過程同直接映象Cache（命中時(shí)間）；但當(dāng)缺失發(fā)生時(shí)，在訪問下層存儲(chǔ)器之前（缺失代價(jià)），通過檢查另外一個(gè)Cache塊來看看是否在那里命中（偽命中時(shí)間）。3之2偽相聯(lián)Cache本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cach偽相聯(lián)Cache本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能>>降低缺失率特點(diǎn)偽相聯(lián)Cache的AMAT短，但變化的命中時(shí)間會(huì)使流水線CPU設(shè)計(jì)復(fù)雜度增加，因此較適合用于離CPU較遠(yuǎn)的Cache中，例如：L2Caches。這兩個(gè)技術(shù)都綜合了1-路組相聯(lián)（直接相聯(lián)）的命中時(shí)間短和2-路組相聯(lián)的沖突低。3之3偽相聯(lián)Cache本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cach編譯優(yōu)化本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能>>降低缺失率指令缺失性能改善在不影響正確性的前提下重新安排程序代碼，可能會(huì)降低沖突缺失，從而降低指令缺失率。例如：McFarling[1989]在容量2KB、塊容量4B的直接相聯(lián)Cache中使用本方法將Cache的缺失率降低50%，若Cache容量為8KB，則缺失率降低75%。編譯優(yōu)化本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>編譯優(yōu)化本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能>>降低缺失率數(shù)據(jù)缺失性能改善數(shù)據(jù)比指令代碼在位置上的限制甚至更少，這些變換的目標(biāo)是盡力提高數(shù)據(jù)的空間和時(shí)間局部性。下面通過3個(gè)例子進(jìn)行介紹：循環(huán)交換循環(huán)融合分塊編譯優(yōu)化本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>循環(huán)交換一些程序帶有嵌套循環(huán)，它們?cè)L問存儲(chǔ)器中的數(shù)據(jù)是非順序的，簡(jiǎn)單的交換嵌套循環(huán)可以使得代碼按照存儲(chǔ)順序來訪問數(shù)據(jù)。/*Before*/for(k=0;k<100;k=k+1)

for(j=0;j<100;j=j+1) for(i=0;i<5000;i=i+1) x[i][j]=2*x[i][j];/*After*/for(k=0;k<100;k=k+1)

for(i=0;i<5000;i=i+1) for(j=0;j<100;j=j+1) x[i][j]=2*x[i][j];本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能>>降低缺失率>>編譯優(yōu)化通過提高空間局部性來減少缺失。循環(huán)交換一些程序帶有嵌套循環(huán)，它們?cè)L問存儲(chǔ)器中的數(shù)據(jù)循環(huán)融合本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能>>降低缺失率>>編譯優(yōu)化一些程序有分立的代碼段，這些代碼按照相同的循環(huán)訪問相同的數(shù)組，對(duì)相同的數(shù)據(jù)進(jìn)行不同的計(jì)算。通過“融合”這些代碼到一個(gè)循環(huán)中，使得裝入到Cache中的數(shù)據(jù)在被替換出來之前可以被重復(fù)地利用。2之1循環(huán)融合本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>循環(huán)融合/*Before*/for(i=0;i<N;i=i+1)for(j=0;j<N;j=j+1)

a[i][j]=1/b[i][j]*c[i][j];for(i=0;i<N;i=i+1)for(j=0;j<N;j=j+1) d[i][j]=a[i][j]+c[i][j];/*After*/for(i=0;i<N;i=i+1)for(j=0;j<N;j=j+1) {

a[i][j]=1/b[i][j]*c[i][j]; d[i][j]=a[i][j]+c[i][j];}本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能>>降低缺失率>>編譯優(yōu)化通過提高時(shí)間局部性來減少缺失。2之2循環(huán)融合/*Before*//*After*/本章內(nèi)分塊本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能>>降低缺失率>>編譯優(yōu)化分塊不是對(duì)矩陣中的整行/列進(jìn)行操作，而是對(duì)子矩陣或矩陣塊進(jìn)行操作，目標(biāo)是在調(diào)入到Cache中的塊被替換之前最大限度地利用它。3之1分塊本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>分塊本章內(nèi)容>>Cache存儲(chǔ)系統(tǒng)>>Cache性能>>提高Cache性能>>降低缺失率>>編譯優(yōu)化/*Before*/for(i=0;i<N;i=i+1) for(j=0;j<N;j=j+1) {r=0; for(k=0;k<N;k=k+1)