/
/

Cache Memory

CPU는 메모리에 접근해 많은 데이터를 처리한다. 이때, 시간을 줄이기 위해 자주 사용하는 데이터를 임시로 캐시 메모리에 저장한다.
cscacheMemory***
avatar
efforthye
in
CS
2025.05.13
·
11 min read

캐시 메모리

CPU는 메모리에 접근해 많은 데이터를 처리한다. 이때, 시간을 줄이기 위해 자주 사용하는 데이터를 임시로 캐시 메모리에 저장한다.

캐시 메모리와 지역성

캐시 메모리(cache memory)는 CPU와 메인 메모리 간에 데이터 접근 시 속도 차이를 줄이기 위해 사용한다. CPU에서 메인 메모리에 있는 데이터를 가져올 때 자주 사용하는 데이터는 캐시 메모리에 따로 저장한다. 이후 해당 데이터가 필요하면 캐시 메모리에 접근한다. 이러면 메인 메모리에 접근하는 것보다 속도를 향상시킬 수 있다.

캐시 메모리에 어떤 데이터를 저장할 지는 지역성을 바탕으로 결정한다. 지역성(locality)은 CPU가 자주 참조하는 데이터가 고르게 분포되지 않고 특정 부분에 몰려 있는 것을 나타낸다.

캐시 적중률을 높이려면 지역성을 바탕으로 데이터를 저장해야 하며, 지역성은 주로 2가지가 있다.
- 시간 지역성(time locality): 최근 참조한 내용을 다시 참조할 가능성이 높은 것이다.
- 공간 지역성(space locality): 실제 참조한 주소 근처의 내용을 다시 참조할 가능성이 높은 것이다.

until-6057

캐시 메모리의 매핑 방식

메인 메모리와 캐시 메모리를 매핑하는 방식은 크게 3가지다.

- 직접 매핑(direct mapping): 메인 메모리를 일정한 크기로 나누고, 각 영역을 캐시 메모리에 매핑하는 방식이다. 메인 메모리는 캐시 메모리보다 크므로. 나눠진 n개의 메모리 영역이 1개의 캐시 메모리에 매핑된다.

6056

  • [직접 매핑] 메인 메모리 & 캐시 메모리 매핑 예시 코드

    // 직접 매핑 캐시 생성 함수
function createDirectMappedCache(cacheSize) {
  // 캐시 초기화 (모든 라인은 무효 상태)
  const cache = Array(cacheSize).fill(null).map(() => ({ 
    tag: -1, 
    data: null, 
    valid: false 
  }));

  // 메모리 주소를 태그와 인덱스로 분할하는 함수
  function getTagAndIndex(memoryAddress) {
    const index = memoryAddress % cacheSize;  // 캐시 라인 번호 = 주소 % 캐시 크기
    const tag = Math.floor(memoryAddress / cacheSize);  // 태그 = 주소 / 캐시 크기
    return { tag, index };
  }

  // 데이터 읽기 함수
  function read(memoryAddress, mainMemory) {
    const { tag, index } = getTagAndIndex(memoryAddress);

    // 캐시 적중 확인 (태그가 일치하고 유효한 데이터인 경우)
    if (cache[index].valid && cache[index].tag === tag) {
      console.log(`Cache HIT at index ${index}`);
      return { hit: true, data: cache[index].data };
    } 
    // 캐시 미스
    else {
      console.log(`Cache MISS at index ${index}`);
      // 메인 메모리에서 데이터 가져와 캐시에 저장
      cache[index] = { tag, data: mainMemory[memoryAddress], valid: true };
      return { hit: false, data: mainMemory[memoryAddress] };
    }
  }

  // 현재 캐시 상태 반환 함수
  function getState() {
    return [...cache];
  }

  return { read, getState };
}

// 사용 예시
const mainMemory = Array(16).fill(0).map((_, i) => `Data-${i}`); // 16개 메모리 블록
const directCache = createDirectMappedCache(4);

console.log(directCache.read(0, mainMemory));  // 주소 0, 인덱스 0에 저장
console.log(directCache.read(4, mainMemory));  // 주소 4, 인덱스 0에 저장 (충돌 발생)
console.log(directCache.read(0, mainMemory));  // 주소 0, 인덱스 0 접근 (미스, 덮어쓰기됨)

    • 실행 결과

      Cache MISS at index 0
{ hit: false, data: 'Data-0' }
Cache MISS at index 0
{ hit: false, data: 'Data-4' }
Cache MISS at index 0
{ hit: false, data: 'Data-0' }

      위와 같이 직접 매핑 방식은 메모리 주소를 주소 % 캐시크기 공식으로 단일 위치에 매핑하는 방식으로, 구현이 단순하고 검색이 O(1)로 매우 빠르지만 같은 인덱스에 매핑되는 주소들끼리 심한 충돌이 발생한다.

  • 연관 매핑(associative mapping): 메모리 영역을 캐시 메모리에 규칙 없이 매핑하는 방식이다. 메모리 영역을 캐시 메모리에 적재할 때는 간단하지만, 캐시 메모리에서 필요한 메모리 영역을 찾을 때는 비효율적일 수 있다.

    6055

    • [연관 매핑] 메인 메모리 & 캐시 메모리 매핑 예시 코드

    // 연관 매핑 캐시 생성 함수
function createFullyAssociativeCache(cacheSize) {
  // 캐시 초기화
  const cache = Array(cacheSize).fill(null).map(() => ({ 
    tag: -1, 
    data: null, 
    valid: false 
  }));

  // 연관 매핑에서는 주소 자체가 태그
  function getTag(memoryAddress) {
    return memoryAddress; // 전체 주소가 태그로 사용됨
  }

  // 데이터 읽기 함수
  function read(memoryAddress, mainMemory) {
    const tag = getTag(memoryAddress);

    // 모든 캐시 라인 검색 (O(n) 연산)
    for (let i = 0; i < cacheSize; i++) {
      if (cache[i].valid && cache[i].tag === tag) {
        console.log(`Cache HIT at line ${i}`);
        return { hit: true, data: cache[i].data };
      }
    }

    // 캐시 미스: 빈 캐시 라인 찾기
    console.log('Cache MISS');

    // 빈 캐시 라인 찾기
    const emptyIndex = cache.findIndex(entry => !entry.valid);

    if (emptyIndex !== -1) {
      // 빈 라인이 있으면 그곳에 저장
      cache[emptyIndex] = { tag, data: mainMemory[memoryAddress], valid: true };
    } else {
      // 빈 라인이 없으면 첫 번째 라인 교체 (실제로는 LRU 등 교체 알고리즘 사용)
      cache[0] = { tag, data: mainMemory[memoryAddress], valid: true };
    }

    return { hit: false, data: mainMemory[memoryAddress] };
  }

  function getState() {
    return [...cache];
  }

  return { read, getState };
}

// 사용 예시
const mainMemory = Array(16).fill(0).map((_, i) => `Data-${i}`);
const associativeCache = createFullyAssociativeCache(4);

console.log(associativeCache.read(0, mainMemory));
console.log(associativeCache.read(4, mainMemory));
console.log(associativeCache.read(8, mainMemory));
console.log(associativeCache.read(12, mainMemory));
console.log(associativeCache.read(0, mainMemory)); // 히트 (충돌 없음)

    • 실행 결과

      Cache MISS
{ hit: false, data: 'Data-0' }
Cache MISS
{ hit: false, data: 'Data-4' }
Cache MISS
{ hit: false, data: 'Data-8' }
Cache MISS
{ hit: false, data: 'Data-12' }
Cache HIT at line 0
{ hit: true, data: 'Data-0' }

      위와 같이 연관 매핑의 경우 메모리 주소를 캐시의 어느 위치에나 자유롭게 저장할 수 있어 충돌이 없고 캐시 활용도가 높지만, 데이터 검색 시 모든 캐시 라인을 비교해야 하므로 검색 속도가 O(n)으로 느리다.

  • 집합 연관 매핑(set associative mapping): 직접 매핑과 연관 매핑을 결합해 단점을 보완한 방식으로, 범용적으로 사용된다.

    6054

    • [집합 연관 매핑] 메인 메모리 & 캐시 메모리 매핑 예시 코드

    // 집합 연관 매핑 캐시 생성 함수
function createSetAssociativeCache(numSets, waysPerSet) {
  // 2차원 배열로 캐시 초기화: [집합][웨이]
  const cache = Array(numSets).fill(null).map(() => 
    Array(waysPerSet).fill(null).map(() => ({ 
      tag: -1, 
      data: null, 
      valid: false 
    }))
  );

  // 주소를 태그와 집합 번호로 분할하는 함수
  function getTagAndSet(memoryAddress) {
    const setIndex = memoryAddress % numSets;  // 집합 번호 = 주소 % 집합 수
    const tag = Math.floor(memoryAddress / numSets);  // 태그 = 주소 / 집합 수
    return { tag, setIndex };
  }

  // 데이터 읽기 함수
  function read(memoryAddress, mainMemory) {
    const { tag, setIndex } = getTagAndSet(memoryAddress);
    const set = cache[setIndex];

    // 해당 집합 내에서 모든 웨이 검색 (O(k) 연산)
    for (let way = 0; way < waysPerSet; way++) {
      if (set[way].valid && set[way].tag === tag) {
        console.log(`Cache HIT at set ${setIndex}, way ${way}`);
        return { hit: true, data: set[way].data };
      }
    }

    // 캐시 미스: 빈 웨이 찾기
    console.log(`Cache MISS for set ${setIndex}`);

    // 빈 웨이 찾기
    const emptyWay = set.findIndex(entry => !entry.valid);

    if (emptyWay !== -1) {
      // 빈 웨이가 있으면 그곳에 저장
      set[emptyWay] = { tag, data: mainMemory[memoryAddress], valid: true };
    } else {
      // 빈 웨이가 없으면 첫 번째 웨이 교체 (실제로는 LRU 등 교체 알고리즘 사용)
      set[0] = { tag, data: mainMemory[memoryAddress], valid: true };
    }

    return { hit: false, data: mainMemory[memoryAddress] };
  }

  function getState() {
    return JSON.parse(JSON.stringify(cache)); // 깊은 복사
  }

  return { read, getState };
}

// 사용 예시: 2-way 집합 연관 캐시 (2개 집합, 각 집합당 2개 웨이)
const mainMemory = Array(16).fill(0).map((_, i) => `Data-${i}`);
const setAssociativeCache = createSetAssociativeCache(2, 2);

console.log(setAssociativeCache.read(0, mainMemory));  // 집합 0 저장
console.log(setAssociativeCache.read(2, mainMemory));  // 집합 0 저장
console.log(setAssociativeCache.read(1, mainMemory));  // 집합 1 저장
console.log(setAssociativeCache.read(3, mainMemory));  // 집합 1 저장
console.log(setAssociativeCache.read(4, mainMemory));  // 집합 0 저장 (충돌, 교체)
console.log(setAssociativeCache.read(2, mainMemory));  // 집합 0 히트 (아직 남아있음)

    • 실행 결과

      Cache MISS for set 0
{ hit: false, data: 'Data-0' }
Cache MISS for set 0
{ hit: false, data: 'Data-2' }
Cache MISS for set 1
{ hit: false, data: 'Data-1' }
Cache MISS for set 1
{ hit: false, data: 'Data-3' }
Cache MISS for set 0
{ hit: false, data: 'Data-4' }
Cache HIT at set 0, way 1
{ hit: true, data: 'Data-2' }

      캐시 메모리 매핑 방식 중 집합 연관 방식은 위와 같이 캐시를 여러 집합으로 나누고 주소를 주소 % 집합수 공식으로 특정 집합에 매핑하되 집합 내에서는 자유롭게 배치하는 방식으로, 직접 매핑의 속도와 연관 매핑의 유연성을 절충해 O(k) 검색 속도와 적절한 충돌 관리가 가능하다.

- 컬렉션 아티클