완전 연관 캐시 구현

Question

완전 연관 캐시에 대한 코드가 내가 제공 한 추적 파일과 일치하지 않는 이유를 모르겠습니다.

매개 변수는 캐시 라인이 32 바이트이고 총 캐시 크기가 16KB입니다.

2,4,8 및 16의 세트 연관 캐시에 대한 구현은 모두 가장 최근에 사용 된 대체 정책을 사용하여 완벽하게 작동합니다. 그러나 32의 집합 결합으로 설명 될 수있는 완전 결합의 경우에는 추적 파일에 매우 가깝지만 매우 비슷합니다. (적어도 방법 내가 그것을했다)

여기 내 코드의 관련 부분 (비 효율성을 변명)

//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; 

}

,174,개

추적 파일이 있어야하는데 :

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) 

내 출력은 : 당신이 볼 수 있듯이

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

, 완전 결합 하나, 그것은 단지 272 정확한 출력 오프입니다. 16 가지 방법에서 32 가지 모드로 전환 할 때 왜 꺼져 버릴까요?

Answer 1

아, 실수로 32KB 크기의 캐시에 대한 완전 연관 캐시가 실제로는 512 가지 일 때 32 가지 캐시 크기입니다.