Input Cash to get Cache [CSAPP Chap 6]

돈을 많이 쓰면 캐시 메모리를 많이 얻을 수 있다. 그냥 같잖은 라임을 쓴게 짜증난다면 내 의도대로 된거니까 너무 놀라지 마라. 이런걸 어디다간 풀어놓는게 내 다음 생각을 하는데 있어 걸림돌이 되지 않는다.

---

지역성

• 간 지역성 : 방금 접근한 데이터는 곧 다시 접근될 가능성이 높다.
  • "방금 사용된 것 위주"로 데이터를 캐시에 두는 것, 즉 최근에 사용된 데이터를 유지하는 전략을 활용한다. 방금 쓴 변수는 곧바로 다시 쓸 확률이 높을 것이니까!!
• 공간 지역성 : 방금 접근한 데이터의 근처에 있는 데이터가 곧 접근될 가능성이 높다.
  • 만약 프로그램이 배열[0]에 접근했다면, 공간 지역성에 따라 곧 배열[1], 배열[2]... 에 접근할 확률이 매우 높다.

 

캐시 메모리

컴퓨터의 저장장치는 하나가 아니라, 속도, 용량, 가격이 각기 다른 여러 개의 장치들이 피라미드처럼 층을 이루어 구성되어 있다. 극단적으로 요약해보면

• 레지스터 : 졸라 빠른 머리 속
• 캐시 메모리: 책상위의 종이.
• 메인 메모리: 종이를 모아둔 파일철 정도
• 하드 디스크: 방의 책장

그리고 레지스터는 뭘 저장해두기엔 용량이 너무 적어서, Cache에 대한 히트 여부가 중요해진다.

• 캐시 히트: 데이터가 캐시에 있으면 캐시 히트이다. 정말 빠르기 때문에 가장 좋은 경우이다.
• 캐시 미스: 데이터가 캐시에 없으면 캐시 미스이다. 그러면 시스템은 메인 메모리와 같이 더 느린 레벨로 이동하여 데이터 블록을 가져오게 된다.

미스가 발생하면 시스템은 메인 메모리에서 캐시로 데이터 블록을 복사한다.
이미 데이터를 찾았는데도 이렇게 하는 이유는, 어쨌든 사용기록이 있으니 다음 캐시라도 히트를 내기 위한 것이다.

 

캐시 교체 정책

어떤 블록을 내보낼지 결정하는 규칙을 교체 정책이라고 부른다.

LRU (Least Recently Used), 즉 '가장 최근에 사용되지 않은' 블록을 내보내는 방식이다.
FIFO (First-In, First-Out)보다 왜 일반적으로 더 효과적일까?
가장 먼저 들어온 블록이라고 사용 빈도가 직접 연관이 있는 것이 아니기 때문이다.

 

Cache-Friendly Programming

// C언어는 배열을 '행 우선(row-major)' 순서로 저장한다.
// 즉, matrix[i][0], matrix[i][1], matrix[i][2]... 순서로 메모리에 나란히 저장한다.

// 버전 1
int sum_version1(int matrix[N][M]) {
    int sum = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            sum += matrix[i][j];
        }
    }
    return sum;
}

// 버전 2
int sum_version2(int matrix[N][M]) {
    int sum = 0;
    for (int j = 0; j < M; j++) {
        for (int i = 0; i < N; i++) {
            sum += matrix[i][j];
        }
    }
    return sum;
}

2차원 배열은 1차원 배열의 연속이고 배열의 기본 구조는 행 순서 진행이다.
따라서 선행 진행이 더 빠르게 진행 할 수 있다.

CPU가 matrix[0][0]을 요청해서 캐시가 matrix[0][0]부터 matrix[0][7]까지의 블록을 가져왔다고 가정해 봅시다.
곧바로 쓸 matrix[1][0] 을 쓸텐데 이러면 캐시 미스가 일어날 확률이 매우 높아지게 된다.