《計(jì)算機(jī)體系結(jié)構(gòu)》第六次實(shí)驗(yàn) cache

1、Cache實(shí)驗(yàn)報(bào)告姓名：王宇航學(xué)號(hào)：09283020 安全0901Cache實(shí)驗(yàn)報(bào)告一、實(shí)驗(yàn)要求：1.閱讀分析附件模擬器代碼要求：1）讀懂 2）關(guān)鍵注釋 3）總結(jié)關(guān)鍵參數(shù)和算法的實(shí)現(xiàn)方法2.通過(guò)讀懂代碼加深了解cache的實(shí)現(xiàn)技術(shù)3.結(jié)合書(shū)后習(xí)題1進(jìn)行測(cè)試4.通過(guò)測(cè)試和進(jìn)行實(shí)驗(yàn)設(shè)計(jì)了解參數(shù)和算法選擇的特點(diǎn)和相互關(guān)系（比較，組合等），需要定性和量化結(jié)合說(shuō)明，可以用數(shù)字或圖表等多種描述手段配合說(shuō)明。二、實(shí)驗(yàn)代碼：1. LRU頁(yè)面置換算法程序一共有3中模式：Direct_mapped 2 Set_associate 3 Fully_associate對(duì)于第一種，直接映射，顯然用不到LRU算法，因?yàn)槊?/p>

2、一個(gè)地址在cache中只有一個(gè)地方可以去。對(duì)于后兩種，組相聯(lián)映射和全相聯(lián)映射，就需要用到LRU算法了。其中，全相聯(lián)映射等于是只有一個(gè)set的Set_associate，而LRU正是用在一個(gè)set中，所以，后面兩種模式的LRU問(wèn)題可以歸結(jié)為一種：一個(gè)set中，來(lái)了一個(gè)沒(méi)有的頁(yè)面，需要置換出一個(gè)，應(yīng)該置換出哪一個(gè)的問(wèn)題。那么，具體過(guò)程如下：1 這個(gè)set中的每一個(gè)block都有一個(gè)lru值，初始為0。2 每次訪問(wèn)這個(gè)set的時(shí)候，不管是否命中，這個(gè)set中的所有block的lru值都+1。3 當(dāng)需要置換出去一個(gè)頁(yè)面的時(shí)候，選擇一個(gè)lru值最大的那個(gè)置換出入，用來(lái)放入剛剛進(jìn)來(lái)的。4 不管是否命中，剛

3、剛訪問(wèn)過(guò)的，或者加入的那個(gè)block的lru值置為0。if(x<lruindexz)/選擇lru值最大的一個(gè)x=lruindexz;y=z;if(z=(assoc*2)-2)/沒(méi)有命中時(shí)newarrayindexy+1=tag; /把lru值最大的替換掉misscount+;c=misstype(blockaddressj,NOofblock,j);cc=1;for(m=0;m<(assoc*2);m=m+2)/所有的lru值+1lruindexm+;lruindexy=0;/把lru值最大的替換掉z=z+2;2. 用于判斷缺頁(yè)類(lèi)型的算法在程序中，體現(xiàn)了3中缺頁(yè)的類(lèi)型：Compul

4、sory Miss：之前沒(méi)有出現(xiàn)的地址，肯定不會(huì)命中Conflict Miss：由于沖突而產(chǎn)生的不命中Capacity Miss：由于容量不足而導(dǎo)致的不命中在函數(shù)int misstype(int ba, int nb, int l)中。ba：表示當(dāng)前不命中的地址nb：表示NOofblock，即cache中block的數(shù)目l：表示當(dāng)前ba在訪問(wèn)序列bytearray數(shù)組中的位置before數(shù)組，用來(lái)表示當(dāng)前已經(jīng)訪問(wèn)過(guò)了那些頁(yè)面。blarray數(shù)組，表示相鄰兩次訪問(wèn)ba之間，訪問(wèn)過(guò)的地址。變量b，表示blarray數(shù)組的大小。Compulsory Miss：那么，只要當(dāng)前訪問(wèn)的頁(yè)面，在之前沒(méi)有訪問(wèn)

5、過(guò)，那么，就是Compulsory Miss這種類(lèi)型。代碼上就是：遍歷before數(shù)組，看看有沒(méi)有和ba相同的，沒(méi)有的話就是Compulsory Miss，同時(shí)不要忘記把ba加入到before數(shù)組，供下次使用。Conflict Miss：在統(tǒng)計(jì)相鄰兩次訪問(wèn)ba之間的不同的地址數(shù)目時(shí)，數(shù)組blarray的大小b就是這個(gè)值。那么只要和nb比較一下，只要b<nb，表示其實(shí)還有多余的空間可以使ba在之前不被調(diào)出，就說(shuō)明其實(shí)是ba由于沖突而被調(diào)出，即Conflict Miss。Capacity Miss：反之，如果b>nb，就表示，相鄰兩次訪問(wèn)ba之間的地址數(shù)目過(guò)大，導(dǎo)致空間不夠使用，即Ca

6、pacity Miss。三、實(shí)驗(yàn)過(guò)程：1. 原始代碼測(cè)試第一個(gè)測(cè)試：Direct mapped第二個(gè)測(cè)試：two-way set associative第三個(gè)測(cè)試：fully associative可見(jiàn)三次測(cè)試的結(jié)果是相同的，因?yàn)槲覀兘o的三組輸入數(shù)據(jù)是相同的。下面我們用書(shū)上的例子進(jìn)行測(cè)試：第一個(gè)測(cè)試：Direct mapped：如圖，和課本的結(jié)果吻合。全部miss，由于其中有3種不同的地址，所以Compulsory miss的數(shù)目是3.第二個(gè)測(cè)試：two-way set associative如圖，和課本的結(jié)果吻合。只有一個(gè)hit，由于其中有3種不同的地址，所以Compulsory miss的

7、數(shù)目是3.第三個(gè)測(cè)試：fully associative如圖，和課本的結(jié)果吻合。有2個(gè)hit，由于其中有3種不同的地址，所以Compulsory miss的數(shù)目是3.綜上，上述三種模式的miss率如下：左：direct 中：2-way 右：fullhit 0%miss 100%miss 80%hit 20%hit 40% miss 60%2. 代碼測(cè)試依據(jù)課后題進(jìn)行代碼測(cè)試：為了測(cè)試block的大小和n-way中n的大小對(duì)miss率的影響，需要反復(fù)實(shí)驗(yàn)。所以，就需要一種策略來(lái)生成訪問(wèn)序列地址，但是又不能隨便生成，因?yàn)樾蛄行枰獫M足一定的空間局部性和時(shí)間局部性。在源代碼中加入一小段測(cè)試代碼如下：（

8、網(wǎng)上找的測(cè)試代碼，且將源代碼中的指定打開(kāi)文件注釋掉，改為由以下函數(shù)生成：頁(yè)面訪問(wèn)序列生成函數(shù)）int num, e, N;int Gen(int que) double t = (rand() % 100) * 0.01; int m = (rand() % (N / 2) + 1; int p = rand() % (N / 2); int cnt = 0; while(true) e = rand() % (N / 2) + 1; for(int i = 0; i < m; i+) quecnt+ = rand() % e + p; if (quecnt - 1 > N - 1

9、) quecnt - 1 = N - 1; if (cnt = num) break; if (cnt = num) break; double r = (rand() % 100) * 0.01; if (r < t) p = rand() % N; else p = (p + 1) % N; return cnt;那么，為了兼顧到3種模式，下面將按照A Direct mapped模式下，僅BlockSize大小增加。B 僅n-way的n改變，從116C 僅采用全相聯(lián)都用相同的數(shù)據(jù)測(cè)試1000次觀察效果（1）Direct mapped直接映射，BlockSize大小增加Cache大小固定為128，序列長(zhǎng)度為100當(dāng)BlockSize = 1的時(shí)候：當(dāng)BlockSize = 2的時(shí)候：當(dāng)BlockSize = 4的時(shí)候：由此可見(jiàn)，在直接映射下，當(dāng)blocksize從1、2、4依次的增長(zhǎng)時(shí)，缺頁(yè)率在減少。（2）組相聯(lián)映射中n對(duì)缺頁(yè)率的影響測(cè)試實(shí)驗(yàn)：Cache大小固定為64，BlockSize為1，序列長(zhǎng)度為100，n從1變到16，看結(jié)果：n=1時(shí)：n=2n=4n=8n=16由此可知，隨著n的增大，缺頁(yè)率是逐步減小的。3. 全相聯(lián)映射：Cache大