Thread: cache miss/hit

  1. #1
    essence of digital xddxogm3's Avatar
    Join Date
    Sep 2003
    Posts
    589

    cache miss/hit

    I have been writing this program in C++ and can not figure out what i did wrong.
    I'm trying to write a program that simulates a cache.
    It has to simulate direct mapped cache, n-way, and fully associativity.
    The direct mapped cache part works perfect, but the n-way and fully associative one does not. It is off by about 1000 hits. The results I should be getting
    are
    cache size=1024 block size =32 associativity =4
    hits=1036092
    miss=463908
    miss rate=0.31
    my results are
    hits =1045473
    misses=454527
    miss rate=.303018
    Code:
    #include <vector>
    #include <iostream>
    #include <fstream>
    #include <conio.h>
    #include <string>
    
    using namespace std;
    
    int main(int argc, char *argv[])  // pass in arguments
    { 
        long lgNumberOfBlocks=0;       //used to store total blocks
        long lgBlocksPerSet=0;         //used to store total blocks per set
        long lgByteAddress=0;          //store the byte address after conversion
        long lgByteAddressConverted=0; //store the memory saving byte address
        long lgBlockSize=0;            //store the block code
        long lgAssociativity=0;        //store the passed in associativity 
        long lgCacheSize=0;            //store the cache size
        long lgHit=0;                   //store total hits on the cache    
        long lgMiss=0;                 //store total misses on the cache
        long lgCacheAddress=0;         //store the cache address (i.e. modulo)
        long lgBlockAddress=0;         //store the block address (i.e. division)
        long lgCacheTag=0;             //store the cache tag
        long lgLRUCount=0;             //counter for the LRU incrementation
        long lgSetAddress=0;           //store the set address (i.e. modulo)
        long lgFullAssociativityCount=0;  //increment the associativity
        unsigned long unlgTotalLoads=0;   //store the total of all hits and misses
    
        if (argc != 9)    //test to see if user passed 9 parameters
        {
            cout<<"!!Invalid Number of arguments.\nUsage: "<< argv[0] <<" -t <file_name> -s <cache_size> -b <block_size> -a <associativity>!!\n";
            exit(1);
        }
    
        ifstream inTraceFile(argv[2], ios::in);    //open the file for read only
    
        if(!inTraceFile.is_open())      //test to see if the read was successful
        {
            cout<<"!!Unable to open file "<<argv[2]<<"!!\n";
            exit(2);
        }
    
        string stFileName(argv[2]);       //grab the file name parameter
        string stProgramName(argv[0]);    //grab the program name and store it
        lgBlockSize = atoi(argv[6]);      //parse and grab the block size parameter
        lgCacheSize = atoi(argv[4]);      //parse and grab the cache size parameter
        lgAssociativity = atoi(argv[8]);  //parse and grab the associativity parameter
    
        lgNumberOfBlocks = lgCacheSize/lgBlockSize;          //calculate the total number of blocks
        lgBlocksPerSet = lgNumberOfBlocks/lgAssociativity;   //calculate the total number blocks per set
    
        /*
        DMC Calculations
        Exact Details:
        Reconstructs the byte address from a memory saving scheme.
        Constructs the cache address and cache tag.
        Records hit or miss with DMC.
        */
    
        if (lgAssociativity == 1)    //test for associativity of DMC or Associativity == 1
        {
            vector < unsigned long > vecCache(lgBlocksPerSet);  //create a one demensional vector
    
            while(inTraceFile>>lgByteAddress)   //read line by line of the load trace file
            {
                lgByteAddressConverted=lgByteAddressConverted+lgByteAddress;    //convert from memory save scheme to byte address
                
                lgBlockAddress = lgByteAddressConverted/lgBlockSize;   // calculate the lgBlockAddress by using division
                lgCacheAddress = lgBlockAddress%lgNumberOfBlocks;     // calculate the cache address by using modulo
                lgCacheTag = lgBlockAddress/lgNumberOfBlocks;        //caclulate the cache tag by using division
            
                if(vecCache[lgCacheAddress]==lgCacheTag)          // check to see if cache tag is stored in memory
                {
                    lgHit++;             // if stored in memory we have a hit
                }
                else
                {
                    lgMiss++;       // if not stored in memory we have a miss
                    vecCache[lgCacheAddress]=lgCacheTag;   // store cache address in vector at the cache address
                }
                 unlgTotalLoads++;   // record the total loads
            }
        }
        else  //any other associativity is calculated here
        {
            vector < unsigned long > vecAssociativity;   //first dimension of the "associativity" vector
            vector < vector <unsigned long> > vecCache;   //second dimension of the "cache" vector
            
            for(int i=0; i<lgAssociativity; i++)    //insert a dimension for each level of associativity
            {
                vecCache.push_back(vecAssociativity);      //push the associativity vector into the cache vector
            }
    
            while(inTraceFile>>lgByteAddress)  // read in one line at a time of the load trace file
            {
                lgByteAddressConverted=lgByteAddressConverted+lgByteAddress;  //convert from memory save scheme to byte address
    
                lgBlockAddress = lgByteAddressConverted/lgBlockSize;  //calculate the block address by using division
                lgSetAddress = lgBlockAddress%lgAssociativity;   // calculate the set address by using modulo
                lgCacheTag = lgBlockAddress/lgAssociativity;   // calculate the cache tag by using division
    
                if (vecCache[lgSetAddress].size()!=0)    // check to see if vector size is 0
                {    
                    for(unsigned long x=0;x<vecCache[lgSetAddress].size();x++)   //if vector was bigger then 0 cycle through values
                    {    
                        if(vecCache[lgSetAddress][x]==lgCacheTag)   //check to see if the values you are cycling through are a memory hit
                        {
                            lgHit++;      //record the hit
    
                            //Description of next 2 lines of code:
                            //Least Recently Used Scheme. Erase the vector location of the hit and push on the bottom of stack.
                            //Used to track the most recent used and least recent used vector hit.
                            vecCache[lgSetAddress].erase(vecCache[lgSetAddress].begin()+x);  //Realign the most recently used.
                            vecCache[lgSetAddress].push_back(lgCacheTag);  // place back in line as most recently used
                            
                            break;    // break out of loop due to hit was successful.
                        }
                        if(vecCache[lgSetAddress].size()-1 == x && vecCache[lgSetAddress][x]!=lgCacheTag && vecCache[lgSetAddress].size()==lgBlocksPerSet)  //test for end of vector, maxed out vector, and cache miss
                        {//record a conflict miss
    
                            lgMiss++;  //record cache miss
    
                            //Description of next 2 lines of code:
                            //Least Recently Used Scheme. Erase the vector location of the least recently used and push the new value on the bottom of vector.
                            //Used to track the most recent used and least recent used vector value.
                            vecCache[lgSetAddress].erase(vecCache[lgSetAddress].begin()); //erase the least recently used vector value
                            vecCache[lgSetAddress].push_back(lgCacheTag); //push value on to the vector in order of recently used
    
                            break;  // break out of loop due to a miss was found
                        }    
                        if(vecCache[lgSetAddress].size()-1==x && vecCache[lgSetAddress][x]!=lgCacheTag) //test for reaching the last value of the vector, and a miss
                        {//record a compulsory miss
    
                            lgMiss++; // record the miss
                            vecCache[lgSetAddress].push_back(lgCacheTag); //due to no overflow and a miss do a push onto the vector
    
                            break; //break due to a miss was recorded
                        }                    
                    }                
                }
                else //record the compulsory misses
                {
                    lgMiss++;  //record a miss
                    vecCache[lgSetAddress].push_back(lgCacheTag); //push value on the vector in order 
                }
                
                unlgTotalLoads++;  //record the total amount of loads.
            }
        }
    
        //display all the calculated data.
        cout<<"Program Name:    "<<stProgramName<<endl;
        cout<<"Trace File Name: "<<stFileName<<endl;
        cout<<"Cache Size:      "<<lgCacheSize<<endl;
        cout<<"Block Size:      "<<lgBlockSize<<endl;
        cout<<"Associativity:   "<<lgAssociativity <<endl;
        cout<<"Total Loads:     "<<unlgTotalLoads<<endl;
        cout<<"Total Hits:      "<<lgHit<<endl;
        cout<<"Total Misses:    "<<lgMiss<<endl;
        cout<<"Miss Rate:       "<<((double)lgMiss/(double)unlgTotalLoads)<<endl;
    
        return 0;
    }
    "Hence to fight and conquer in all your battles is not supreme excellence;
    supreme excellence consists in breaking the enemy's resistance without fighting."
    Art of War Sun Tzu

  2. #2
    Registered User
    Join Date
    May 2007
    Posts
    88
    Use functions / classes. If the problem still isn't clear, try a debugger.

  3. #3
    essence of digital xddxogm3's Avatar
    Join Date
    Sep 2003
    Posts
    589
    does anyone have an idea?
    my head is going to explode due to I'm unable to see where i went wrong.
    "Hence to fight and conquer in all your battles is not supreme excellence;
    supreme excellence consists in breaking the enemy's resistance without fighting."
    Art of War Sun Tzu

  4. #4
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    I agree with UMR_Student. Your problem is that your code is unreadable and impenetrable. You simply lost track of what's going on, because you have one big block of code.

    Organize the code properly and you'll have a far easier time searching for the error.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Difference between ARP Cache and DNS cache?
    By namasteall2000 in forum Networking/Device Communication
    Replies: 9
    Last Post: 06-26-2009, 08:49 AM
  2. need help with cache simulator!
    By dtogers123 in forum C Programming
    Replies: 3
    Last Post: 04-30-2008, 06:18 PM
  3. ideas requested for a CACHE.
    By bean66 in forum C Programming
    Replies: 2
    Last Post: 02-21-2008, 11:01 AM
  4. Resource manager tree
    By VirtualAce in forum Game Programming
    Replies: 23
    Last Post: 09-07-2007, 10:27 PM
  5. added start menu crashes game
    By avgprogamerjoe in forum Game Programming
    Replies: 6
    Last Post: 08-29-2007, 01:30 PM