Java Cache Simulation с LRU дает неточную скорость попадания

Question

Я пишу программу Java, которая имитирует различные схемы кеша. Мой проект разбивает Cache на два класса, Cache и Set, с блоками набора, представленными как очередь, так что я могу использовать алгоритм 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, что намного меньше, чем предполагается. Я пробовал отладку с небольшими файлами и, похоже, работает нормально, но я не могу заставить его работать с этим файлом.

ПРИМЕЧАНИЕ. Эта программа работает с кешем 1-way/direct-mapped, поэтому проблема связана с алгоритмом LRU, но я не знаю, что.

Answer 1

Выяснил это! Оказывается, это не имеет никакого отношения к LRU. Когда ассоциативность набора кеша увеличивается, он не увеличивает количество доступных слотов в кэше. Поэтому

this.sets = new Set[passedNumSets]; 

Должно быть

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