計算機體系結(jié)構(gòu)cache模擬器實驗報告

1、崔雪瑩Cache實現(xiàn)分析 計算機體系結(jié)構(gòu)Cache模擬器實驗實驗報告 姓名 崔雪瑩 學(xué)號 12281166 班級 計科1202班 老師 董嵐 2015年 06月07日一、閱讀分析附件模擬器代碼21、關(guān)鍵參數(shù)22、關(guān)鍵算法3二、 課后習(xí)題51、習(xí)題內(nèi)容52、題目分析53、計算及結(jié)果64、模擬器上實驗結(jié)果檢驗7三、整體分析81、三種映射方式對Cache效率的的影響82、block塊大小與Cache容量對Cache效率的影響83、Cache容量與相連度對Cache效率的影響94、三種失效類型影響因素9四、實驗思考和感受101、關(guān)于模擬器的思考102、關(guān)于整個實驗的思考10一、 閱讀分析附件模擬器代碼

2、1、關(guān)鍵參數(shù)（1） 用戶可見參數(shù)：（用戶通過命令行輸入?yún)?shù)）參數(shù)名含義值備注choice映像方式選項1/2/31為直接映射，2為組相連映射，3為全相連映射cachesizeCache大小16/64/128/256以字節(jié)為單位blocksizeBlock大小1/2/4以字為單位assoc相連度1/2/4/8/16assoc路組相連（n-way）accesscount請求次數(shù)待輸出等于project.txt的值個數(shù)hitcount命中次數(shù)待輸出成功在Cache找到次數(shù)hitrate命中率待輸出HitRate= hitcount/accesscountmisscount未命中次數(shù)待輸出沒在Cache

3、找到次數(shù)misscount = 1-hitcountmissrate未命中率待輸出MissRate= misscount/accesscountc1c ,c2c ,c3c失效次數(shù)待輸出分別為三種失效類型的次數(shù)（2）程序內(nèi)部主要參數(shù)：（代碼內(nèi)部重要參數(shù)）參數(shù)名含義計算備注blockinbyte塊的字節(jié)大小=blocksize*4每一個塊占多少字節(jié)NOofblock塊個數(shù)=cachesize/blockinbyteCache中多少個塊NOofset組個數(shù)=NOofblock/assoc塊分成了多少個組bytearray要訪問的數(shù)據(jù)的字節(jié)地址=projec.txt中的值project.txt文件數(shù)據(jù)

4、賦給了bytearray數(shù)組wordaddress要訪問的數(shù)據(jù)的字地址=bytearrayj/4blocksize是字為單位的，就是說一個block占多少個字，所以數(shù)據(jù)也要求字地址blockaddress數(shù)據(jù)的塊地址=wordaddress/blocksize數(shù)據(jù)在第幾塊index索引位(組地址)=blockaddressj%NOofset若Noofset=2m，則塊地址低m位為索引位（組地址）。tag標(biāo)識位（組內(nèi)尋址）=blockaddressj/NOofset塊地址高(32-m)位為標(biāo)識位,用于確定組內(nèi)哪塊數(shù)據(jù)，newarrayindexz+1中存放*valid有效位有效為1，失效為0判斷

5、該cache塊數(shù)據(jù)是否有效*是因為沒有真正定義，只是存放newarrayindexz中l(wèi)ruindexz最近未被使用次數(shù)每次加1，被重寫置0替換時，替換掉lruindex值最大的那個塊2、關(guān)鍵算法注：這里不粘貼代碼，只是進行簡單的代碼算法說明（1） 塊地址表示：注：圖是我按照自己的想法自己畫的，可能有些地方并不準(zhǔn)確，望老師指正。圖中以一個例子來解釋cache模擬器中block和數(shù)據(jù)地址的關(guān)系，以及和組地址和標(biāo)志位的關(guān)系。（2） Index與tag：由上面計算：index = blockaddress % NOofsetindex = 16 % 8 = 2tag = blockaddress /

6、 Noofsettag = 16/8 = 2以上例，字地址16為例，寫成二進制為0001 0010 B，其中組數(shù)為8，又因為23=8，所以字地址取后3位為：index = 010 B = 2 ，取前29位為：tag = 00010 B = 2 。所以，算法與理論是一致的。（3） Valid：有效位。當(dāng)通過上述方式尋址找到了數(shù)據(jù)存放的數(shù)據(jù)塊，接下來判斷有效位：有效位為1，說明數(shù)據(jù)是有效的，可以從block提取數(shù)據(jù)；有效位為0，說明塊里的數(shù)據(jù)是無效的，所以不能從block提取數(shù)據(jù)，出現(xiàn)miss，此時判斷miss類型，同時需要訪問內(nèi)存或下一級存儲，將數(shù)據(jù)放到cache里。（4） 失效類型及判斷方法：

7、判斷失效類型，函數(shù)misstype（int ba ，int nb ，int l）。Compulsory miss（強制性失效，冷啟動）：當(dāng)?shù)谝淮卧L問某一個塊的時候，數(shù)據(jù)是肯定不在塊中的，此時出現(xiàn)強制性失效，或者說是冷啟動失效。Capacity miss（容量失效）：所需的數(shù)據(jù)不能全部調(diào)入cache中，塊被替換后又被重新訪問，意思就是當(dāng)所有的塊都被占滿了，這樣又有數(shù)據(jù)希望被調(diào)入緩存時，就出現(xiàn)了容量失效。Conflict miss（沖突失效）：在組相聯(lián)或直接映像中，數(shù)據(jù)想要替換進某一組中，組內(nèi)的塊都被占滿了，但是別的組的塊有空余，數(shù)據(jù)只能替換這一組，盡管別的組有空余也不能替換。這樣就出現(xiàn)了沖突失效

8、。（5） LRU算法實現(xiàn)替換：LRU替換算法是采用最近最久未使用的塊，其中Lru數(shù)組存放最近多少次未被使用，因為是采用循環(huán)訪問，當(dāng)循環(huán)訪問到這一組時，把這組所有的塊的Lru值都加1，如果成功訪問到這一塊，數(shù)據(jù)能從其中取出來，就把這一塊的Lru值置0，退出循環(huán)。（6） 直接映射、組相聯(lián)映射、全相聯(lián)映射：直接映射：是特殊的組相聯(lián)映射，就是相聯(lián)度為1的組相聯(lián)映射。所以采取和組相聯(lián)一樣的程序和算法，當(dāng)識別該組第一塊失效時，直接進行替換，因為有且只有一塊。組相聯(lián)映射：當(dāng)識別該組某塊失效時，如果塊都被占滿，要根據(jù)Lru值的大小，判斷哪一塊被替換掉。全相聯(lián)映射：從上到下cache塊存數(shù)據(jù)，則從上到下循環(huán)即可

9、，遇到失效時，要根據(jù)Lru值的大小，判斷哪一塊被替換掉。二、 課后習(xí)題1、 習(xí)題內(nèi)容在CacheSimulator模擬器上模擬如下程序的運行過程：int i,j,c stride,array256 for(i=0;i<10000;i+) for(j=0;j<256;j=j+stride) c = arrayj+5;假設(shè)Cache總大小是256個字節(jié)，且塊大小為16字節(jié)（4個字）。同時假設(shè)內(nèi)存當(dāng)中只有這一個程序在運行，而且整形數(shù)字的長度為一個字長（字長為32位），在直接相連映射下，stribe分別等于132、131時程序的運行結(jié)果，并分析原因。而當(dāng)采用兩路組相連時又會有什么結(jié)果并分析

10、原因。2、 題目分析當(dāng)stribe = 132/131 時，程序相當(dāng)于循環(huán)訪問內(nèi)存偏移地址為0和地址132/131的內(nèi)容，循環(huán)10000次，也就是訪問了2000次存儲。結(jié)合cache機制，cache大小為256個字節(jié)，塊大小為16個字節(jié)，所以塊的個數(shù)為256/16 = 16個。若為2路組相連，則有16/2 = 8組。當(dāng)?shù)谝淮卧L問塊時，一定會發(fā)生強制性失效，計一次miss。3、 計算及結(jié)果1） 直接映像時：l stride=132array0的塊地址為0，映射到cache的塊號為0：0 mod 16 = 0array132的塊地址為132/4 = 33，映射到cache的塊號為1：33 mod

11、16 = 1因為第一次訪問cache，0和1一定會發(fā)生強制性失效，之后因為調(diào)入cache，不會發(fā)生失效。則失效次數(shù)為2，則失效率為： 2/20000 = 0.01%命中次數(shù)為19998次，命中率為：19998/20000 = 99.99% = 1（近似）失效類型為強制性失效，次數(shù)為2。l stride=131array0的塊地址為0，映射到cache的塊號為0：0 modulo 16 = 0array131的塊地址為131/4 = 32，映射到cache的塊號為0：32 modulo 16 = 0因為第一次訪問cache，0一定會發(fā)生強制性失效，之后cache里塊號為0的塊不斷地被替換寫入替換

12、寫入，此時發(fā)生沖突失效。則失效次數(shù)為20000，則失效率為：20000/20000 = 1 = 100%命中率為0。失效類型為強制性失效次數(shù)1，沖突失效次數(shù)為19999。2） 2路組相聯(lián)：l stride=132array0的塊地址為0，映像到cache的組號為0：0 modulo 8 = 0array132的塊地址為132/4 = 33，映像到cache組號為1：33 modulo 8 = 1因為第一次訪問cache，0和1一定會發(fā)生強制性失效，之后因為調(diào)入cache，不會發(fā)生失效。則失效次數(shù)為2，則失效率為：2/20000 = 0.01%命中次數(shù)為19998次，命中率為：19998/200

13、00 = 99.99% = 1（近似）失效類型為強制性失效，次數(shù)為2。l stride=131array0的塊地址為0，映像到cache組號為：0 modulo 8 = 0array131的塊地址為131/4 = 32，映像到cache組號為：32 modulo 8 = 0因為第一次訪問cache，0和1一定會發(fā)生強制性失效，之后因為是2路組相聯(lián)，array0與array131都在0組，不會發(fā)生失效，則失效次數(shù)為2，失效率為：2/20000 = 0.01%命中次數(shù)為19998次，命中率為：19998/20000 = 99.99% = 1（近似）失效類型為強制性失效，次數(shù)為2。4、 模擬器上實驗

14、結(jié)果檢驗注：因為例題的循環(huán)次數(shù)為10000，為了便于實驗，我將循環(huán)次數(shù)設(shè)置為100，結(jié)果參照100的計算，原理是一致的。因為實際131/132都是字地址，而project.txt設(shè)置的是字節(jié)地址，所以將project.txt里值設(shè)置為0 和 132*4/131*4 循環(huán)100次，設(shè)置cache大小為256，block大小為4，可以分別看到直接映射和2路組相連映射的結(jié)果為：直接映射stride=132stride=131miss count2200miss rate0.011.00hit count1980hit rate0.990access count200200c1c(強制性失效)22c2

15、c（容量性失效）00c3c（沖突性失效）01982路組相連映射stride=132stride=131miss count22miss rate0.010.01hit count198198hit rate0.990.99access count200200c1c(強制性失效)22c2c（容量性失效）00c3c（沖突性失效）00可以看到實驗結(jié)果與計算是一致的（因為循環(huán)次數(shù)100，所以實驗結(jié)果小數(shù)點要后移兩位）。同時對習(xí)題1的思考（見后）也證明是正確的。（1） 直接映射：stride = 132 截圖（2） 直接映射：stride = 131 截圖（3） 2路組相連：stride = 132 截

16、圖（4） 2路組相連：stride = 131 截圖三、 整體分析1、 三種映射方式對Cache效率的的影響其他相同條件：block大小為2，組相連相連度為4，project.txt為200個01000的隨機數(shù)。cache容量（字節(jié)）映射方式直接映射組相連全相連640.940.9350.9251280.870.8750.8652560.790.790.7855120.680.630.6110240.500.500.50 生成圖表：此時可以看到：1. 直接映射的失效率高，組相連失效率中等，全相連失效率最低2. 隨著cache容量的增加，失效率越小。3. 當(dāng)cache容量為1024時，因為數(shù)據(jù)取值

17、的原因，三種方式失效率相等，說明當(dāng)cache容量足夠大，三種方式失效率是一樣的。2、 block塊大小與Cache容量對Cache效率的影響其他相同條件：直接映射，相連度為1，project.txt為200個01000的隨機數(shù)。塊大?。ㄗ郑〤ache容量（字節(jié)）64128256512102410.940.8850.830.770.6920.940.870.790.680.5040.950.9050.800.6350.3080.9450.890.7850.5750.155生成圖表：此時可以看到：1. 對于給定的cache容量如64字節(jié)，當(dāng)塊大小增加時，失效率先是下降，后來反而上升了。2. Cac

18、he容量越大，使其失效率達(dá)到最低的塊的大小就越大。3. 因為取得數(shù)據(jù)樣本是隨機的，不是連續(xù)的，實驗數(shù)據(jù)并不是十分準(zhǔn)確，比如cache容量128時，塊大小出現(xiàn)兩次失效率3、 Cache容量與相連度對Cache效率的影響其他相同條件：組相連，塊大小2，project.txt為200個01000的隨機數(shù)。Cache容量（字節(jié)）相連度/路1248640.940.930.9150.9051280.8750.870.860.872560.7850.7650.800.785120.6450.640.670.6610240.5350.5350.5350.535生成圖表：此時可以看到：1. 提高相連度會使失效率

19、下降。2. 因為取得數(shù)據(jù)樣本是隨機的，不是連續(xù)的，實驗數(shù)據(jù)并不是十分準(zhǔn)確。3. 當(dāng)容量為1024時，也就是cache一定大時，失效率沒什么區(qū)別。4、 三種失效類型影響因素（1）相連度對三種失效類型影響：其他相同條件：cache大小為256，block大小為2，組相連，project.txt為200個01000的隨機數(shù)。相連度（路）總失效率總失效次數(shù)失效類型強制性失效容量失效沖突失效10.78156107381120.80160107401340.76515310741580.785157107455160.785157107464 可以看出：1. 強制性失效，即冷啟動，不受相連度的影響。2.

20、容量失效基本不受相連度影響，但因為數(shù)據(jù)偶然性，出現(xiàn)增大趨勢。3. 沖突失效隨著相連度的增加而降低。（2）Cache容量對三種失效類型影響：其他相同條件：block大小為2，組相連度為4，project.txt為200個01000的隨機數(shù)。cache容量（字節(jié)）總失效率總失效次數(shù)失效類型（相對百分比）強制性失效容量失效沖突失效640.931861077811280.871741076522560.7651531074155120.6412810713810240.53510710700可以看出：1. 容量越大，失效率越小。2. 強制性失效不受容量大小的影響。3. 容量失效隨著容量的增加而大大減小。4. 沖突失效不受容量大小的影響。四、 實驗思考和感受1、關(guān)于模擬器的思考 Cache大小可選為16/64/128/256，因為代碼寫了，但是沒有增加選項。但是，我考慮因為16實在太小了，沒什么意義。 打開文件 名字為project.txt，修改文件名。 個人感覺有地方不太合適，