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<Instruction> instrs= new ArrayList<Instruction>();public static HashSet<String> compulsory= new HashSet<String>();// 记录强制缺失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 HitRationType[72];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 (sts[0].endsWith("l")) {//统计指令类型数目reads++;inst.type = "l";} else {writes++;inst.type = "s";}inst.addrs = sts[1];others += Integer.parseInt(sts[2]);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 中，如果满了，则根据设定好的替换策略，调用相应的替换策略进行替换。