高相聯(lián)度cache的性能分析與優(yōu)化

高相聯(lián)度cache的性能分析與優(yōu)化

1虛擬多體cache的提出和實(shí)現(xiàn)在過去10年中，cpu速度顯著增加，平均每年增加55%。但是主存速度的提高卻慢得多，例如，DRAM的速度每年只提高約7%。因此，CPU和主存之間在性能上的差距越來越大?，F(xiàn)代計(jì)算機(jī)一般都采用Cache來解決這個(gè)問題。在影響Cache性能的諸多因素中，相聯(lián)度是非常重要的一個(gè)。相聯(lián)度是指當(dāng)一個(gè)數(shù)據(jù)塊從主存調(diào)入Cache時(shí)，Cache中可用于存放該數(shù)據(jù)塊的位置（稱為候選位置）的個(gè)數(shù)。普遍采用的直接映象Cache的相聯(lián)度為1，其主要優(yōu)點(diǎn)是命中時(shí)間小，但其失效率較高。而組相聯(lián)（相聯(lián)度≥2)Cache則相反，其優(yōu)點(diǎn)是失效率低，Hill和Smith指出，與直接映象相比，兩路組相聯(lián)（相聯(lián)度為2）可以把失效次數(shù)減少30%。但其命中時(shí)間較長，并因此常導(dǎo)致CPU的時(shí)鐘周期變長（因?yàn)榇蠖鄶?shù)微處理器的訪問Cache是處于關(guān)鍵通路上）。近年來，人們一直在致力于研究既能獲得具有較低的失效率，又能保持命中時(shí)間?。ㄅc直接映象Cache相同）的特點(diǎn)的Cache，并已提出了一些方案。但這些方案的相聯(lián)度都只是接近于2，沒有解決高相聯(lián)度的高效實(shí)現(xiàn)問題。相聯(lián)度越高，失效率就越低，而且高相聯(lián)度在許多情況下是非常重要的，例如當(dāng)失效開銷較大或當(dāng)存儲器互連訪問延遲較大時(shí)。在多處理機(jī)中，這兩種情況都可能發(fā)生。在單處理機(jī)中，當(dāng)僅有一級Cache，而Cache與存儲器的速度差距又較大時(shí)，會(huì)出現(xiàn)失效開銷較大的情況。此外，高相聯(lián)度還能減少發(fā)生Cache抖動(dòng)的可能性，當(dāng)重復(fù)訪問m個(gè)映象到同一組（設(shè)相聯(lián)度為n）的不同塊時(shí)，若n<m，就有可能會(huì)導(dǎo)致抖動(dòng)。增大n能有效地減少抖動(dòng)。文章提出了一種能高效地實(shí)現(xiàn)高相聯(lián)度的方案———虛擬多體Cache，這種方案既能有效地實(shí)現(xiàn)高相聯(lián)度，又能保持接近于直接映象Cache的命中時(shí)間。文中首先對相關(guān)的工作進(jìn)行了分析，然后論述虛擬多體Cache的思想和兩種具體實(shí)現(xiàn)方案———順序虛擬多體Cache(SMC-Cache）和并行虛擬多體Cache(PMC-Cache）。最后，對方案進(jìn)行了性能評價(jià)。文中介紹了性能參數(shù)，并對模擬結(jié)果進(jìn)行了分析。2偽相聯(lián)cache與psacache近年來，人們提出了不少改進(jìn)Cache性能的方案，其中與文中工作關(guān)系較大的有：Hash-RehashCache，偽相聯(lián)Cache,PSACache,MRUCache等。Hash-RehashCache所能實(shí)現(xiàn)的相聯(lián)度為2。對于每一次Cache訪問，采用位選擇算法確定兩個(gè)候選位置：第一個(gè)位置的地址通過直接從該訪問的塊地址的低位截取獲得，第二個(gè)位置的地址則是通過把第一個(gè)位置的地址的最高位變反而求得。偽相聯(lián)Cache和PSACache也是按這種映象規(guī)則確定其候選位置。Hash-RehashCache按“第一候選位置→第二候選位置”的順序查找，若在第一個(gè)位置上命中，則把相應(yīng)的數(shù)據(jù)送給CPU，訪問結(jié)束；否則檢測第二個(gè)位置。若在第二個(gè)位置上命中，則把在這兩個(gè)位置上的塊對調(diào)。但是，若在這兩個(gè)位置上都失效，就需從存儲器調(diào)塊。偽相聯(lián)Cache是Hash-RehashCache的改進(jìn)，主要區(qū)別是它給每個(gè)位置增設(shè)了一個(gè)稱為Rehash的標(biāo)志位。當(dāng)處理Cache訪問時(shí)，若第一個(gè)位置的Rehash位為“1”，則不必再往下查找。這樣便可過濾掉不必要的查找。與偽相聯(lián)Cache相比，PSACache的主要區(qū)別是利用訪存指令的相關(guān)信息預(yù)測出第一候選位置的地址（查表）。上述三種都是相聯(lián)度接近于2的方案。模擬結(jié)果表明，在失效率上，Hash-RehashCache比兩路組相聯(lián)Cache高一些，偽相聯(lián)Cache非常接近于（但大于）兩路組相聯(lián)Cache，而PSACache則與兩路組相聯(lián)Cache相同。在平均訪問時(shí)間上，則是偽相聯(lián)Cache最小。因此，在后面的性能分析中，只與偽相聯(lián)Cache進(jìn)行比較。在相聯(lián)度大于2的組相聯(lián)Cache實(shí)現(xiàn)方面，目前已提出的方案主要有兩種MRUCache(MRU是MostRecentlyUsed的縮寫）：一種是由Kessler等人提出，另一種則是由Chang等人提出。在Kessler的方案中，對于同一組中的各候選位置是按某種順序依次串行檢查的。這種順序由一個(gè)稱為MRU表的表格給出。由于在每次訪問Cache（進(jìn)行搜索）之前，都需先用有效地址作為索引從MRU表中讀取相應(yīng)的MRU信息，所以會(huì)延長Cache訪問周期，或者需要專門留出一個(gè)周期用于訪問MRU表。因此，中指出，這種方案對一級Cache不合適。Chang的MRUCache主要是在傳統(tǒng)4路組相聯(lián)的基礎(chǔ)上增加了前瞻性地提供數(shù)據(jù)的機(jī)制。在這種方案中，MRU信息（設(shè)置有一個(gè)MRU表）被用來猜測性地從4個(gè)候選數(shù)據(jù)中選出一個(gè)送給CPU，并同時(shí)進(jìn)行標(biāo)識的比較。如果發(fā)現(xiàn)猜錯(cuò)了，則在下一個(gè)周期重新送出正確的數(shù)據(jù)。這種方案的訪問時(shí)間比直接映象的大，這是由于在其關(guān)鍵的通路上依然存在多路選擇器。此外，由于映射到同一組的所有訪問都共享一個(gè)MRU項(xiàng)，所以猜錯(cuò)的概率較高。這兩種MRU都有一個(gè)嚴(yán)重的缺陷：對于一長串連續(xù)地址的訪問（這種情況經(jīng)常發(fā)生),MRUCache的性能經(jīng)常會(huì)比直接映象的差。在一些極端情況下，MRUCache的所有命中都可能變?yōu)榈趎次命中（其中n為相聯(lián)度。第n次命中是指按順序檢查到第n個(gè)位置才命中）。在這種情況下，其性能急劇下降。3虛擬多件披露3.1基于cache的算法選擇方案虛擬多體Cache在概念上把Cache等分為若干個(gè)邏輯體（如4體，8體等）。對于每一次訪問，采用類似于位選擇算法的映象方法從各邏輯體中選出一個(gè)候選位置。這些候選位置構(gòu)成邏輯上的一個(gè)組。對于這些候選位置，既可以順序查找，也可以并行查找。文章相應(yīng)地提出了兩種設(shè)計(jì)方案：順序虛擬多體Cache（簡稱SMC-Cache）和并行虛擬多體Cache（簡稱PMC-Cache）。這兩種方案都采用了多MRU塊技術(shù)，并采用LRU替換算法。3.2多mru塊技術(shù)在相聯(lián)度大于1的Cache中，對于每一次訪問來說，在其相應(yīng)組中的各候選位置上命中（找到需要的內(nèi)容）的可能性不相同。一般應(yīng)按“從可能性最大的位置到可能性最小的位置”的順序查找。在MRUCache中，每一組只有一個(gè)固定的查找順序。也就是說，對于映象到該組的所有訪問來說，查找時(shí)只有一個(gè)公共的入口，即該組的MRU塊位置（如圖1(a））。這就是MRUCache有時(shí)會(huì)出現(xiàn)首次命中率低的原因。例如，考慮一長串地址跨距為d的連續(xù)訪問，如果這一長串訪問的內(nèi)容都能放入直接映象Cache中，則在第一遍訪問以后，所有的后續(xù)訪問都將是首次命中；但在塊大小為b的MRUCache中，有1/[b/d]的后續(xù)訪問不是首次命中。在最壞的情況下（b=d），所有命中都不是首次命中。出現(xiàn)這個(gè)問題的原因，是由于對于映象到同一組的不同訪問來說，該組中不同的塊有不同的重要性，該組的唯一查找順序無法反映出這一點(diǎn)。為解決上述問題，提出了多MRU塊的技術(shù)。在作者的方案中，對于任何一個(gè)訪問來說，把它按照直接映象規(guī)則映射到的那個(gè)位置稱為主位置，而把相應(yīng)組中的其它位置稱為非主位置。這里把映象到同一邏輯組中的訪問根據(jù)其主位置劃分為若干個(gè)集合，每一個(gè)集合對應(yīng)于一個(gè)主位置。如果對于每一個(gè)集合中的訪問，都提供獨(dú)立的查找順序，則可以達(dá)到最佳效果。但是，考慮到大多數(shù)訪問都會(huì)在MRU塊命中，為了減少復(fù)雜度，只記錄多個(gè)MRU塊（每一個(gè)對應(yīng)于一個(gè)集合）。這樣，映象到同一組中的訪問就有多個(gè)入口（如圖1(b）所示），每一個(gè)入口對應(yīng)該組中的某個(gè)集合。通過采用交換的方法來保證在主位置中的塊為MRU塊。僅當(dāng)發(fā)生非首次命中或失效時(shí)才進(jìn)行交換，這時(shí)把命中的塊或新調(diào)進(jìn)來的塊放到主位置上，而把原來在主位置上的塊交換到其他位置上。為了把交換所需的時(shí)間減少到平均一個(gè)時(shí)鐘周期，采用類似于中的輔助硬件，主要是一個(gè)用于交換的緩沖器，代價(jià)很小。采用多MRU塊技術(shù)后，上述訪問序列中的所有命中都將是首次命中。除文中提出的虛擬多體Cache外，多MRU塊技術(shù)還可應(yīng)用于前述MRUCache，以進(jìn)一步改進(jìn)性能。3.3相關(guān)位置的搜索在這種方案中，是從主位置開始，依次對各候選位置順序進(jìn)行查找。雖然除主位置以外的候選位置的重要性比主位置小得多，但如何高效地對它們進(jìn)行查找，對于整個(gè)方案的性能有很大的影響。對于一次訪問來說，并不是相應(yīng)的組中所有的候選位置都有可能包含所訪問的數(shù)據(jù)?？紤]該組中的任何一個(gè)位置，當(dāng)且僅當(dāng)其中的塊是在以下情況下從主存調(diào)進(jìn)來：先前有一個(gè)與本次訪問具有相同主位置的訪問失效；它才有可能包含本次訪問所要的數(shù)據(jù)?？梢苑Q這些位置為相關(guān)位置。用一些索引表來記錄相關(guān)的位置。這樣，在查找時(shí)，就可以過濾掉那些根本不可能包含所訪問數(shù)據(jù)的塊。相關(guān)位置的地址由兩部分構(gòu)成：邏輯體號（高位），該邏輯體內(nèi)的相對塊號（低位）。相對塊號可由本次訪問的塊地址的低位直接截取獲得，邏輯體號則是根據(jù)索引表中的信息產(chǎn)生。在索引表中，給每一個(gè)主位置分配一個(gè)長度為n的位向量，該向量中每一位對應(yīng)于相應(yīng)組中一個(gè)位置；若值為“1”，則表示該位置是相關(guān)位置，否則就不是。為了便于修改，同一組中各位置的位向量串接為一項(xiàng)。SMCCache的查找算法如圖2所示。在處理一次訪問時(shí)，首先是檢查主位置。與此同時(shí)，從索引表中讀出有關(guān)相應(yīng)組的索引信息，并生成下一個(gè)相關(guān)位置的地址。如果第一次檢查不命中，就檢查下一個(gè)相關(guān)位置，同時(shí)生成再下一個(gè)相關(guān)位置的地址。這個(gè)過程反復(fù)進(jìn)行，直到命中或所有相關(guān)位置都已檢查完（失效）。每一次檢查需要一個(gè)時(shí)鐘周期。在非首次命中以及失效的情況下，都要進(jìn)行交換，把新的MRU塊搬到當(dāng)前訪問的主位置上。為了支持塊的交換，在硬件上需增設(shè)一個(gè)交換緩沖器，這樣在一個(gè)時(shí)鐘周期便可實(shí)現(xiàn)交換（詳見）。3.4數(shù)據(jù)安全訪問在這種方案中，標(biāo)識存儲器的實(shí)現(xiàn)與數(shù)據(jù)存儲器的實(shí)現(xiàn)互相獨(dú)立（而不像傳統(tǒng)的組相聯(lián)Cache中那樣相一致）。數(shù)據(jù)存儲器是作為一個(gè)體，就象在傳統(tǒng)直接映象Cache中那樣，但標(biāo)識存儲器卻是分為幾個(gè)體。對數(shù)據(jù)存儲器的訪問是順序進(jìn)行的，每次只訪問一個(gè)字，但標(biāo)識比較卻是并行進(jìn)行的。數(shù)據(jù)存儲器設(shè)計(jì)為一個(gè)體，免除了出口處的多路選擇器，而且能支持超前發(fā)送數(shù)據(jù)給CPU。PMC-Cache在處理訪問時(shí)，可以直接從數(shù)據(jù)存儲體中讀出主位置的數(shù)據(jù)（這與直接映象Cache相同）。與此同時(shí)，并行讀出相應(yīng)組中的所有數(shù)據(jù)，并進(jìn)行比較（這與傳統(tǒng)的組相聯(lián)類似）。如果主位置上的標(biāo)識匹配，那么這次訪問就是首次命中，訪問時(shí)間為一個(gè)周期；否則，若其它標(biāo)識有匹配的，則就是第2次命中。這時(shí)，需要再次訪問數(shù)據(jù)存儲體。這需要多花一個(gè)周期。如果沒有匹配的標(biāo)識，就是一次失效，需從下一級存儲器調(diào)塊。與SMC-Cache中的情況類似，在失效和第2次命中的情況下，需要進(jìn)行一次交換。4atum地址流通過模擬，把SMC-Cache和PMC-Cache與偽相聯(lián)Cache在性能上進(jìn)行了比較。所采用的地址流為ATUM地址流，它包含了10個(gè)程序的地址流：deco,fora,forf.3,fsxzz,macr,memxx,mul8.3,pasc,spic,ue02。ATUM地址流是由真實(shí)負(fù)載程序構(gòu)成的。包括操作系統(tǒng)和多處理的操作。許多對Cache的研究都采用ATUM作為模擬負(fù)載。對相聯(lián)度為4、8、16三種情況進(jìn)行了模擬，Cache大小的變化范圍為1KB到128KB，塊大小取為16B。4.1訪存次數(shù)的確定失效率和平均訪問時(shí)間是衡量Cache性能的兩個(gè)重要指標(biāo)。在模擬中兩者都采用了。由于平均訪問時(shí)間更直接和更準(zhǔn)確地反映性能，所以應(yīng)該更注重這個(gè)指標(biāo)。假設(shè)M為失效開銷（即處理一次失效所需的時(shí)間），R為一個(gè)地址流中總的訪存次數(shù)，Hi為第i次命中的次數(shù)，F(xiàn)i為第次取的次數(shù)，TPSD、TSMCn、TPMCn分別為偽相聯(lián)Cache、SMC-Cache（相聯(lián)度為n）、PMC-Cache的平均訪問時(shí)間。根據(jù)文獻(xiàn)以及前面論述的搜索算法，可得：在PMC-Cache中，只有一種“取”，設(shè)其次數(shù)為F。為了把虛擬多體Cache與直接映象Cache和偽相聯(lián)Cache的性能進(jìn)行比較，采用了“與直接映象相比，在訪問時(shí)間上的改進(jìn)”指標(biāo)（簡稱為IMP），其定義如下：其中TDIR是直接映象Cache的平均訪問時(shí)間，T是所考慮Cache的平均訪問時(shí)間，T∈邀TPSD,TSMCn,TPMCn妖。通過模擬，統(tǒng)計(jì)出Hi、Fi和R，然后按上述公式計(jì)算各指標(biāo)。4.2smc-cache與偽相聯(lián)的imp比較IMP如圖3和圖4所示。這些數(shù)據(jù)都是ATUM10個(gè)地址流模擬計(jì)算結(jié)果的平均值。從圖3中可以看出，SMC-Cache和PMC-Cache都能有效地減少失效率和平均訪問時(shí)間，在平均訪問時(shí)間上，比直接映象Cache和偽相聯(lián)Cache都有很大的改進(jìn)。例如，對于一個(gè)相聯(lián)度為4、容量為4KB的Cache來說，SMC-Cache、PMC-Cache的IMP分別為9.8%、10.8%。而偽相聯(lián)的IMP則僅為4.3%，。當(dāng)Cache容量為16KB時(shí)，在n=4和n=16的情況下，SMC-Cache的最高IMP分別為12.7%和15.8%。從圖中還可以看出，當(dāng)相聯(lián)度提高到16或更大時(shí)，