Fully Associative Cache implementation

Question

I don't understand why my code for the fully associative cache doesn't match the trace files that I'm given.

The parameters are each cache line is 32 bytes and the total cache size is 16KB.

My implementations for set associative caches of 2,4,8,and 16 all work perfectly (using least recently used replacement policy). But for fully associative, which could also just be described as a set associative of 32, is VERY close to the trace file but not quite. Frankly, I don't know how to debug this one since there's a vast amount of steps (at least the way I did it)

Here's the relevant parts of my code (excuse the inefficiency)

//Fully Associative
    int **fullyAssoc;

    fullyAssoc = new int*[64]; //where fullyAssoc[0][index] is way 0, fullyAssoc[2][index] is way 1 etc..

    int **LRU32;
    LRU32 = new int*[32];

    for (int i = 0; i < 64; ++i){ //Initialize all entries in fullyAssoc to 0
            fullyAssoc[i] = new int[16 * CACHE_LINE / 32];
    }
    for (int i = 0; i < 16; i++){ //Initialize LRU array
            LRU32[0][i] = 0;
            LRU32[1][i] = 1;
            LRU32[2][i] = 2;
            LRU32[3][i] = 3;
            LRU32[4][i] = 4;
            LRU32[5][i] = 5;
            LRU32[6][i] = 6;
            LRU32[7][i] = 7;
            LRU32[8][i] = 8;
            LRU32[9][i] = 9;
            LRU32[10][i] = 10;
            LRU32[11][i] = 11;
            LRU32[12][i] = 12;
            LRU32[13][i] = 13;
            LRU32[14][i] = 14;
            LRU32[15][i] = 15;
            LRU32[16][i] = 16;
            LRU32[17][i] = 17;
            LRU32[18][i] = 18;
            LRU32[19][i] = 19;
            LRU32[20][i] = 20;
            LRU32[21][i] = 21;
            LRU32[22][i] = 22;
            LRU32[23][i] = 23;
            LRU32[24][i] = 24;
            LRU32[25][i] = 25;
            LRU32[26][i] = 26;
            LRU32[27][i] = 27;
            LRU32[28][i] = 28;
            LRU32[29][i] = 29;
            LRU32[30][i] = 30;
            LRU32[31][i] = 31;
    }
    int fullyAssocLRU = 0;
    int memCount = 0;

    while(getline(fileIn, line)){
            stringstream s(line);
            s >> instruction >> hex >> address;

            int indexFull;
            int tagFull;
            unsigned long long address, addressFull;
            address = address >> 5; //Byte offset
            addressFull = address;

            indexFull = addressFull % 16;
            tagFull = addressFull >> 4;

    if (assocCache(fullyAssoc, indexFull, 32, tagFull, LRU32) == 1){
                    fullyAssocLRU++;
    }

}

void LRU_update(int **lru, int index, int way, int ways){
    int temp = 0;
    int temp2[ways];
    int temp_index = 0;
    int i = 0;
    while(i < ways){
            if (lru[i][index] == way/2){
                    temp = lru[i][index];
                    i++;
                    continue;
            }
            else{
                    temp2[temp_index] = lru[i][index];
                    temp_index++;
            }
            i++;
    }
    for (int j = 0; j < ways - 1; j++){
            lru[j][index] = temp2[j];
    }
    lru[ways - 1][index] = temp;

}

bool assocCache(int **block, int index, int ways, int tag, int **lru){
    bool retVal = false;
    for(int i = 0; i < 2*ways; i = i + 2){
            if (block[i][index] == 0){
                    block[i][index] = 1;
                    block[i+1][index] = tag;
                    LRU_update(lru, index, i, ways);
                    return retVal;
            }
            else{
                    if (block[i+1][index] == tag){
                            retVal = true;
                            LRU_update(lru, index, i, ways);
                            return retVal;
                    }
                    else{
                            continue;
                    }
            }

    }
    int head = 2 * lru[0][index];
    block[head][index] = 1;
    block[head+1][index] = tag;
    LRU_update(lru, index, head, ways);

    return retVal;

}

The trace files is supposed to be:

837589,1122102; 932528,1122102; 972661,1122102; 1005547,1122102; //For direct mapped
993999,1122102; 999852,1122102; 999315,1122102; 1000092,1122102; //For set associative
1000500,1122102; //For fully associative (LRU)

My output is:

837589,1122102; 932528,1122102; 972661,1122102; 1005547,1122102;
939999,1122102; 999852,1122102; 999315,1122102; 1000092,1122102; 
1000228,1122102; 

As you can see, for the fully associative one, it's only 272 off the correct output. Why would it be off when switching from 16 ways to 32 ways?

Answer 1

Ah, I mistakenly though a fully associative cache for a 32 line size cache of 16KB cache size is 32 ways, when it's actually 512 ways.