使用LRU進行Java高速緩存仿真導致命中率不準

Question

我正在編寫模擬各種高速緩存設計的Java程序。我的設計將Cache分成兩個類，Cache和Set，將一個集合中的塊表示爲Queue，以便我可以使用LRU算法進行替換。這裏是我的Cache類

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文件中讀取字節地址並將它們映射到緩存。然而，當我在this .dat file上運行它時，它應該計算錯誤計數211414.相反，它表示錯誤計數是183099，遠遠低於應該計算的數量。我試過用小文件調試，它似乎工作正常，但我無法讓它與這個文件一起工作。

注意：此程序可以與單向/直接映射緩存一起使用，所以問題似乎與LRU算法有關，但我不知道是什麼。

Answer 1

想通了！原來它與LRU無關。當緩存的集合關聯性增加時，它不會增加緩存中可用槽的數量。因此

this.sets = new Set[passedNumSets]; 

應該

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