cache模擬器一、實驗目標：程序運行時，都會對內存進行相關操作，所訪問的內存地址可以被記錄下來，形成memory trace文件。在本實驗中，你將使用benchmark程序產生的memory trace文件來測試cache命中率，文件可以在/classes/fa07/cse240a/proj1-traces.tar.gz上獲得。每次存儲器訪問都包含了三個信息：1. 訪問類型，l表示load操作，s表示store操作；2. 地址。采用32位無符號的十六進制表示；3. 存儲器訪問指令之間的間隔指令數。例如第5條指令和第10條指令為存儲器訪問指令，且中間沒有其他存儲器訪問指令，則間隔指令數為4。 通過寫一段程序，模擬cache模擬器的執行過程。二、實驗要求：寫一段程序模擬cache模擬器的執行過程，并對5個trace文件進行測試，完成以下目標：1. 請統計load類型指令和store類型指令在這5個trace文件中的指令比例。2. 設cache總容量為32kb，對以下所有參數進行組合（共有72種組合），測量相應5個文件的cache命中率。通過對命中率的分析，可以發現什么規律。行大小：32字節、64字節、128字節 相連度：8路相聯、4路相聯、2路相聯、1路相聯替換策略：fifo，隨機替換，lru寫策略：寫直達、寫回 3. 給出5個文件的最佳cache命中率的參數組合。針對不同的trace文件，最佳配置是否相同。4. 測量各種組合下cache和主存之間的數據傳輸量。5. 給出5個文件的最小數據傳輸量的參數組合。這個組合和第3問中得到的組合是否一致。針對不同的trace文件，最佳配置是否相同。6. cache缺失有三種原因：1）強制缺失；2）容量缺失；3）沖突缺失。分析這三種缺失并說明你的分析方法。7. 請給出5個trace文件在最優cache命中率的情況下，這三種缺失所占的比例，并和教材圖c.8給出的比例進行比較。三、程序設計與實現：本程序我打算采用java進行編寫，因為java能夠很好地體現面向對象編程的優點。首先需要定義相關的數據類型。 將指令定義為一個單獨的指令類，好方便操作和記錄統計，其中屬性包括該指令的類型，比如是load指令還是store指令，還包括指令的地址。class instruction string type;string addrs; 將cache定義為一個類，cache中的字段包括tag標識字段，用于查找到相應組后進行比較看是否命中。dirty字段用于寫回策略中判斷是否數據已經被修改了，如果修改了則在置換的時候需要寫回，在統計cache與主存的數據傳輸量時需要用到。最后一個字段是count，該字段用于記錄該cache塊最近被訪問的頻度，用于組相連時lru替換策略時判斷哪個塊最長時間沒被訪問到。class cache int tag;int dirty;int count; 最后定義一個cache模擬器類。用一個二維數組來模擬cache，因為二維數組可以很好地表示組相連cache，而直接相連和全相聯cache都是組相連的特殊情況，當第一維為1時，表示全相連cache，當第二維為1時，表示直接相連cache。public class cachesimulator public long size;/ cache大小public int line_size;/ 塊大小public int set_associativity;/ 相聯度public static long set_count;/ 組數public int set_indexs;/ 用于fifo中記錄需替換的塊號public cache caches;public static arraylist instrs = new arraylist();public static hashset compulsory = new hashset();/ 記錄強制缺失public static long conflict;/ 記錄沖突缺失public boolean write_method = false;/false表示寫回，true表示寫直達public int replace_method = 0;/ 0為random，1為fifo，2為lrupublic static hitrationtype hitrations = new hitrationtype72;public static int communication_times;random rand = new random(set_associativity);/ 用于隨機替換策略static int offset = 0;static int read_misses = 0, read_hits = 0;static int reads = 0;static int write_misses = 0, write_hits = 0;static int writes = 0;static int others = 0;static int totals = 0;接下來需要定義幾個輔助方法，首先第一個是readfile（）方法，通過讀入trace文件來將數據提取出來，保存到指令list中，同時統計讀操作和寫操作的指令數目，以及總的指令數目。具體如下所示：static void readfile(string path) throws ioexception file file = new file(path);bufferedreader br = new bufferedreader(new inputstreamreader(new fileinputstream(file);string s;string sts;while (s = br.readline() != null) sts = s.split( );instruction inst = new instruction();/將數據保存到指令類中if (sts0.endswith(l) /統計指令類型數目reads+;inst.type = l; else writes+;inst.type = s;inst.addrs = sts1;others += integer.parseint(sts2);instrs.add(inst);string tmp = + getindex(inst.addrs);compulsory.add(tmp);totals = reads + writes + others;br.close(); 定義一個函數getindex（）和gettag（），輸入一個十六進制的指令，然后分別返回其對應的索引字段和tag字段。要求索引字段和tag字段，首先得分別算出地址中tag字段、索引字段和塊內偏移字段的位數，而這與cache的映射策略、cache的大小以及塊大小有關。static int getindex(string addr) string to = tobinarystring(addr);string index_add = to.substring(int) (to.length() - offset - (int) log(set_count, 2), to.length()- offset);int index = integer.parseint(index_add, 2);return index;static int gettag(string addr) string to = tobinarystring(addr);string tag_add = to.substring(0, to.length() - offset- (int) (to.length() - offset - (int) log(set_count, 2);int tag = integer.parseint(tag_add, 2);return tag; 在getindex（）函數中用到了一個自定義的log函數，該函數能夠通過將一個數據返回其以2為基值的對數值，比如cache塊大小為32，則log（32,2）返回5。public static double log(double value, double base) return math.log(value) / math.log(base); 由于java中所實現的將十六進制數轉換為2進制數的函數并不完善，比如當十六進制數字最高幾位為0時，java api中的函數默認不將其進行轉換，而是直接忽略。因此，在程序中需要自定義一個函數來實現將十六進制的指令轉換為2進制表示。static string tobinarystring(string addr) string sub = addr.substring(2);stringbuffer sb = new stringbuffer();for (int i = 0; i sub.length(); i+) switch (sub.charat(i) case 0:sb.append(0000);break;case 1:sb.append(0001);break;。/太長而且重復，此處就省略了default:system.out.println(數據有誤！);break;return sb.tostring();程序主體執行過程很簡單，對每一條保存在指令list中的指令進行如下操作。首先通過getindex（）和gettag（）函數獲取指令的index字段和tag字段，然后通過該index字段作為第一維的索引去查找cache二維數組，然后進行tag字段的比較，如果改組中有匹配的tag，則說明該指令在cache中，命中了。否則說明不命中，此時判斷該cache行是否已經滿了，如果沒滿，則將該指令所在的那一塊加載到cache中，如果滿了，則根據設定好的替換策略，調用相應的替換策略進行替換。具體如下所示：void run() for (int i = 0; i instrs.size(); i+) instruction instr = instrs.get(i);if (instr = null) break;int index1 = getindex(instr.addrs);int tag1 = gettag(instr.addrs);boolean hit = false;int index2 = -1;for (int j = 0; j set_associativity; j+) cache c1 = cachesindex1j;if (c1 = null) index2 = j;break;if (c1.tag = tag1) / 如果命中了if (instr.type.equals(s) write_hits+;if (write_method) / 如果是寫直達writethrough(); else cachesindex1j.dirty = 1; else read_hits+;hit = true;index2 = j;/ 保存是那一路命中break;if (hit) / 如果命中int count = cachesindex1index2.count;/ 保存原來的count值，為lru提供條件for (int j = 0; j count) cachesindex1j.count-;cachesindex1index2.count = set_associativity - 1; else / 沒有命中if (instr.type.equals(s) write_misses+;communication_times+; else read_misses+;communication_times+;/ 如果讀缺失則需要從內存讀數據if (index2 != -1) / 如果沒命中并且組沒滿cache cache = new cache();cache.count = set_associativity - 1;cache.dirty = 0;cache.tag = tag1;cachesindex1index2 = cache;for (int j = 0; j index2; j+) cachesindex1j.count-; else / 如果沒命中且組已經滿了，則調用相應的替換策略conflict+;if (replace_method = 0) rand(instr); else if (replace_method = 1) fifo(instr); else lru(instr);具體的替換策略，如lru（）、rand（）和fifo（）以及寫回策略的實現請參看源代碼，此外程序中還有很多輔助函數，由于篇幅原因，在文檔中只給出了幾個直接相關的輔助函數，詳細的請參看源代碼。4、 結果分析：1. 請統計load類型指令和store類型指令在這5個trace文件中的指令比例？結果如下所示：gcc.trace:load指令數為：318197 , load指令在該trace文件中的指令比例為：0.206599store指令書為:197486 , store指令在該trace文件中的指令比例為：0.128224gzip.trace:load指令數為：320441 , load指令在該trace文件中的指令比例為：0.295786store指令書為:160603 , store指令在該trace文件中的指令比例為：0.148246mcf.trace:load指令數為：5972 , load指令在該trace文件中的指令比例為：0.005891store指令書為:721258 , store指令在該trace文件中的指令比例為：0.711504swim.trace:load指令數為：220668 , load指令在該trace文件中的指令比例為：0.187610store指令書為:82525 , store指令在該trace文件中的指令比例為：0.070162twolf.trace:load指令數為：351403 , load指令在該trace文件中的指令比例為：0.242175store指令書為:131421 , store指令在該trace文件中的指令比例為：0.0905712. 設cache總容量為32kb，對以下所有參數進行組合（共有72種組合），測量相應5個文件的cache命中率。通過對命中率的分析，可以發現什么規律？由于cache的命中率與具體的寫策略無關，因此在這題中的程序實現中，我固定了寫策略，即隨便選了一種寫策略，這樣能夠減少一般的循環次數，提高程序執行的效率。所以，總共在程序中執行了36種組合分別對5個trace文件進行測試cache的命中率。以gcc.trace文件為例，其結果如下所示：行大小組相連替換策略寫策略命中率328rand-0.998948328fifo-0.998941328lru-0.998948324rand-0.998578324fifo-0.998584324lru-0.998601322rand-0.997777322fifo-0.997795322lru-0.997915321rand-0.994477321fifo-0.994477321lru-0.994477648rand-0.999309648fifo-0.999305648lru-0.999313644rand-0.999047644fifo-0.999016644lru-0.999065642rand-0.998444642fifo-0.998471642lru-0.998619641rand-0.995793641fifo-0.995793641lru-0.9957931288rand-0.9995441288fifo-0.9995321288lru-0.9995481284rand-0.9992981284fifo-0.9992451284lru-0.9993441282rand-0.9987681282fifo-0.9988131282lru-0.9989891281rand-0.9953341281fifo-0.9953341281lru-0.995334從結果圖表中可以看出，一般而言，當固定cache行大小以及相同相連度的條件下，采用不同的替換策略會對命中率帶來輕微的影響，對不同的trace文件最優的替換策略可能會有所不同，從結果中的數據結果看來，一般情況下lru都能取得不錯的效果。當固定替換策略和cache行大小的條件下，隨著相連度的增加，cache的命中率也有所增加，這種情況下，相連度越大，沖突缺失會越少，因此能獲得較高的命中率。當固定替換策略和相連度的時候，隨著cache行大小的增加，cache的命中率也有所增加，隨著cache行的增大，能有效地減少強制缺失數，因此也能提高命中率。3. 給出5個文件的最佳cache命中率的參數組合。針對不同的trace文件，最佳配置相同嗎？結果如下：gcc.trace:該文件中最佳的參數組合為：行大小=128字節 組相連=8路 替換策略=lrugzip.trace:該文件中最佳的參數組合為：行大小=128字節 組相連=8路 替換策略=randmcf.trace:該文件中最佳的參數組合為：行大小=128字節 組相連=8路 替換策略=lruswim.trace:該文件中最佳的參數組合為：行大小=128字節 組相連=8路 替換策略=lrutwolf.trace:該文件中最佳的參數組合為：行大小=128字節 組相連=8路 替換策略=rand從上述結果來看，5個trace文件的最佳cache命中率的參數組合基本一致，只是替換策略可能會有所差異而已，但由替換策略引起的對命中率的影響并不大，因此可以基本認為5個trace文件的最佳cache命中率的參數組合一致。可以看出，cache行大小和組相連度都取了測試值的最大值，因此，在一般情況下，隨著cache行大小和組相連度的增加，cache的命中率也相應的增大。4. 測量各種組合下cache和主存之間的數據傳輸量。以gcc.trace為例：行大小組相連替換策略寫策略通信量328rand寫回法17440328rand寫直達6328480328fifo寫回法17696328fifo寫直達6328576328lru寫回法17728328lru寫直達6328480324rand寫回法24128324rand寫直達6332000324fifo寫回法24000324fifo寫直達6331872324lru寫回法23776324lru寫直達6331648322rand寫回法41824322rand寫直達6337792322fifo寫回法42176322fifo寫直達6337728322lru寫回法39808322lru寫直達6336576321rand寫回法123584321rand寫直達6366304321fifo寫回法123584321fifo寫直達6366304321lru寫回法123584321lru寫直達6366304648rand寫回法23104648rand寫直達12652032648fifo寫回法23424648fifo寫直達12652160648lru寫回法23232648lru寫直達12652032644rand寫回法33216644rand寫直達12657152644fifo寫回法35584644fifo寫直達12657856644lru寫回法33216644lru寫直達12656768642rand寫回法63232642rand寫直達12667264642fifo寫回法63296642fifo寫直達12667008642lru寫回法57280642lru寫直達12663744641rand寫回法192192641rand寫直達12722304641fifo寫回法192192641fifo寫直達12722304641lru寫回法192192641lru寫直達127223041288rand寫回法307201288rand寫直達252965121288fifo寫回法326401288fifo寫直達252972801288lru寫回法308481288lru寫直達252962561284rand寫回法529921284rand寫直達253072641284fifo寫回法606721284fifo寫直達253091841284lru寫回法519681284lru寫直達253047041282rand寫回法1077761282rand寫直達253277441282fifo寫回法1066241282fifo寫直達253251841282lru寫回法924161282lru寫直達253163521281rand寫回法4096001281rand寫直達255040001281fifo寫回法4096001281fifo寫直達255040001281lru寫回法4096001281lru寫直達25504000由于篇幅受限，因此此處只給出gcc.trace文件的測試結果。從結果中可以看出，寫回法和寫直達對cache與主存的數據的傳輸的數據量影響十分大，采用寫回策略能夠有效地減少與主存的數據傳輸量。5. 給出5個文件的最小數據傳輸量的參數組合。這個組合和3）得到的組合一致嗎？針對不同的trace文件，最佳配置相同嗎？這5個文件的最小數據傳輸量的參數組合和命中率最高的最佳參數組合分別如下所示：gcc.trace:該文件中與主存通信量最少的最佳的參數組合為：行大小=32字節 組相連=8路 替換策略=lru寫策略=寫回法gzip.trace:該文件中與主存通信量最少的最佳的參數組合為：行大小=32字節 組相連=8路 替換策略=rand 寫策略=寫回法mcf.trace:該文件中與主存通信量最少的最佳的參數組合為：行大小=32字節 組相連=8路 替換策略=lru 寫策略=寫回法swim.trace:該文件中與主存通信量最少的最佳的參數組合為：行大小=32字節 組相連=8路 替換策略=lru 寫策略=寫回法twolf.trace:該文件中與主存通信量最少的最佳的參數組合為：行大小=32字節 組相連=8路 替換策略=rand 寫策略=寫回法從上述結果可以看見，對每個trace文件，其最小數據傳輸量的參數組合和命中率最高的最佳參數組合并不一致，其行大小都選擇了最小值，與3）中的結果相反，在3）中都選擇了最大的行大小。對5個