使用 LRU 的 Java 缓存模拟给出了不准确的命中率

Question

我正在编写一个模拟各种缓存设计的 Java 程序。我的设计将 Cache 分为两个类，Cache 和 Set，集合的 block 表示为 Queue，以便我可以使用 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();
    }
}

这是我的类(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;
    }
}

还有我的主课

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 Cache，因此问题似乎与 LRU 算法有关，但我不知道是什么。

Answer 1

想通了!事实证明它与LRU无关。当缓存的集合关联性增加时，它不会增加缓存中可用槽的数量。因此

this.sets = new Set[passedNumSets];

应该是

this.sets = new Set[passedNumSets / setAssoc];