Java 使用 LRU 的缓存模拟给出了不准确的命中率
Java Cache Simulation with LRU Gives an Inaccurate Hit Rate
我正在编写一个 Java 程序来模拟各种缓存设计。我的设计将一个 Cache 分解为两个 classes，Cache 和 Set，一个 set 的块表示为一个 Queue，这样我就可以使用 LRU 算法进行替换。这是我的缓存 class
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();
}
}
这是我的设置 class
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;
}
}
还有我的主要class
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 文件中读取字节地址并将它们映射到缓存。然而，当我 运行 它在 this .dat file 上时，它应该给出 211414 的未命中计数。相反，它说未命中计数是 183099，这比应该的要少得多。我试过用小文件进行调试，它似乎工作正常，但我无法让它与这个文件一起工作。
注意：此程序确实适用于 1-way/direct-mapped 缓存，因此问题似乎与 LRU 算法有关，但我不知道是什么。
想通了！事实证明它与LRU无关。当缓存的集合关联性增加时，它不会增加缓存中可用槽的数量。因此
this.sets = new Set[passedNumSets];
应该是
this.sets = new Set[passedNumSets / setAssoc];
我正在编写一个 Java 程序来模拟各种缓存设计。我的设计将一个 Cache 分解为两个 classes，Cache 和 Set，一个 set 的块表示为一个 Queue，这样我就可以使用 LRU 算法进行替换。这是我的缓存 class
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();
}
}
这是我的设置 class
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;
}
}
还有我的主要class
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 文件中读取字节地址并将它们映射到缓存。然而，当我 运行 它在 this .dat file 上时，它应该给出 211414 的未命中计数。相反，它说未命中计数是 183099，这比应该的要少得多。我试过用小文件进行调试，它似乎工作正常，但我无法让它与这个文件一起工作。
注意：此程序确实适用于 1-way/direct-mapped 缓存，因此问题似乎与 LRU 算法有关，但我不知道是什么。
想通了！事实证明它与LRU无关。当缓存的集合关联性增加时，它不会增加缓存中可用槽的数量。因此
this.sets = new Set[passedNumSets];
应该是
this.sets = new Set[passedNumSets / setAssoc];