我正在编写一个Java程序,模拟各种缓存设计。我的设计将缓存分成两个类Cache和Set,集合的块被表示为队列,以便我可以使用LRU算法进行替换。这是我的Cache类。
这是我的集合类。
似乎在小文件上可以正常工作。我从.dat文件中读取字节地址并将其映射到缓存中。但是当我在此.dat文件上运行它时,应该会出现211414个未命中计数。但是它显示的未命中计数是183099,远少于预期的数量。我尝试使用小文件进行调试,看起来一切正常,但我无法让它在此文件上工作。
注意:此程序可以与1路/直接映射高速缓存一起使用,因此问题似乎出现在LRU算法中,但我不知道具体原因。
import java.io.File;
import java.io.IOException;
import java.util.Scanner;
/**
* Class to simulate a cache with a specified associativity and number of sets
*
* @author Nick Gilbert
*/
public class Cache
{
private Set[] sets;
private int setAssoc, hitCount, missCount, totalCount;
private double hitRate, missRate;
public Cache(int passedNumSets, int passedSetAssoc)
{
this.sets = new Set[passedNumSets];
for(int i = 0; i < this.sets.length; i++)
{
this.sets[i] = new Set(passedSetAssoc);
}
this.setAssoc = passedSetAssoc;
this.hitCount = 0; this.missCount = 0; this.totalCount = 0;
this.hitRate = 0.0; this.missRate = 0.0;
}
/**
* Takes a .dat file name, reads memory addresses from it, and simulates filling the cache
* as it reads each address
*/
public void fillFromFile(String fileName) throws IOException {
Scanner inFile = new Scanner(new File(fileName));
while(inFile.hasNextInt())
{
totalCount++;
int addressToRead = inFile.nextInt(); //Getting next byte address
addressToRead /= 4; //Converting to a word address
int blockAddress = addressToRead / 4;
int location = (blockAddress % sets.length); //Location = (MemoryAddress % CacheSize)
//System.out.println(blockAddress + ": set " + location);
Set setToPlaceAddress = sets[location];
boolean isHit = setToPlaceAddress.checkQueue(blockAddress);
System.out.println(totalCount + "@" + location + ": " + sets[location]);
if(isHit) {
hitCount++;
}
else {
missCount++;
}
System.out.println(isHit);
}
inFile.close();
hitRate = hitCount / (double)totalCount * 100;
missRate = missCount / (double)totalCount * 100;
}
public int getSetAssoc() {
return setAssoc;
}
public void printStats() {
System.out.println("Cache Stats!\n-----------------");
System.out.println(this);
System.out.println("Hit Count: " + hitCount);
System.out.println("Miss Count: " + missCount);
System.out.println("Hit Rate: " + hitRate);
System.out.println("Miss Rate: " + missRate);
}
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("Cache Sets: " + sets.length + "\n");
sb.append("Set Associativity: " + setAssoc + "\n");
sb.append("Block Size: 4");
return sb.toString();
}
}
这是我的集合类。
import java.util.*;
/**
* Class to simulate a set in a cache
* @author Nick Gilbert
*/
public class Set {
private Queue<Integer> blocks; //Data contained in the set
private int setLength; //Set associativity
/**
* Constructor
*/
public Set(int setLength)
{
this.setLength = setLength;
blocks = new ArrayDeque<Integer>();
}
/**
* Check if the block is already there and placing it if it is not
*/
public boolean checkQueue(int blockAddress) {
if(blocks.contains(blockAddress)) { //If the queue contains the address
updateQueue(blockAddress); //Move it to the back (most recently used)
//System.out.println(blockAddress + ": hit");
return true; //It's a hit
}
insertWithLRU(blockAddress); //Insert address with LRU algorithm
//System.out.println(blockAddress + ": miss");
return false; //It's a miss
}
/**
* Method to move address to the back of the queue
*/
private void updateQueue(int mostRecent) {
Iterator<Integer> queueIterator = blocks.iterator(); //Iterator to check through the queue
while(queueIterator.hasNext()) { //Finding the matching address
int addressToCheck = queueIterator.next();
if(addressToCheck == mostRecent) { //When we've found it
queueIterator.remove(); //Remove it to be readded
break;
}
}
blocks.add(mostRecent); //Re-adding it to the back
}
/**
* Algorithm to remove the least recently used address and add a new one
*/
private void insertWithLRU(int address) {
if(blocks.size() >= setLength) { //If queue is full
blocks.remove();
//System.out.println(blocks.remove() + " removed"); //Remove the front one, the least recently used
}
blocks.add(address); //Add new one to the back
}
public String toString() {
String str = "[";
Iterator<Integer> queueIterator = blocks.iterator(); //Iterator to check through the queue
while(queueIterator.hasNext()) { //Finding the matching address
str += queueIterator.next() + ", ";
}
return str;
}
}
我的主要类
import java.io.IOException;
import java.util.Scanner;
/**
* A program to simulate different types of caches for statistical analysis
* on how different cache setups compare to each other
*
* Nick Gilbert
*
* NOTES: Using Byte Addresses
* Take address from file, convert to a word address
* 4 words per block
* block size = 4
* byte / 4 = word
* word / 4 = block
* block % rowsInCache = location
*
* Rows = numSets
* Cols = setAssoc
*/
//TODO FIX LRU ALGORITHM
public class CacheSimulator
{
/**
* Main method
*/
public static void main(String[] args) throws IOException
{
//Creating the cache
Scanner in = new Scanner(System.in);
int numSets, setAssoc;
do
{
System.out.print("Enter number of cache sets (1/32/64/128/256/512): ");
numSets = in.nextInt();
}
while(numSets != 1 && numSets != 32 && numSets != 64 && numSets != 128 && numSets != 256 && numSets != 512);
do
{
System.out.print("Enter set associativity (1/2/4): ");
setAssoc = in.nextInt();
}
while(setAssoc != 1 && setAssoc != 2 && setAssoc != 4);
Cache cache = new Cache(numSets, setAssoc);
System.out.println("Cache created!");
//Getting file to read from
System.out.print("Enter the filename to check: ");
String datFile = in.next();
//Filling cache from file
in.close(); //End of keyboard input
cache.fillFromFile(datFile);
cache.printStats();
}
}
似乎在小文件上可以正常工作。我从.dat文件中读取字节地址并将其映射到缓存中。但是当我在此.dat文件上运行它时,应该会出现211414个未命中计数。但是它显示的未命中计数是183099,远少于预期的数量。我尝试使用小文件进行调试,看起来一切正常,但我无法让它在此文件上工作。
注意:此程序可以与1路/直接映射高速缓存一起使用,因此问题似乎出现在LRU算法中,但我不知道具体原因。
LinkedHashMap
以获得更好的性能、更简单的代码和经过验证的算法。如果直接映射可行,那么可能是关联映射错误。(顺便说一句,我有一个不成熟的跟踪/模拟器包) - Ben Manes