HW3

Assume that we have a cache with the following parameters:
1. Total cache size of 64 bytes
2. Cache lines of 16 bytes (16 bytes are retrieved from DRAM and stored in cache on every miss)
3. Cache lines are replaced using a LRU policy
(least recently used, the cache line that with the oldest prior access is replaced)

Now assume we want to perform the following matrix multiplication using 32-bit float precision:

Calculate the cache hit rate (percentage of cache hits for total memory accesses) in two cases:
· The matrix 𝐴 is stored in column-major format
· The matrix 𝐴 is stored in row-major format
Keep in mind that both reads and writes will be cached.

---

캐시가 뭐 하는 물건인가 (비유)

• DRAM(메인 메모리) = 지하 서고. 멀고 느림.
• 캐시 = 내 책상. 가깝고 빠른데 좁음.
• CPU가 숫자 하나를 필요로 하면 → 서고에 다녀와야 함. 그런데 서고 직원은 그 숫자 하나만 주지 않고, 그게 들어있는 16바이트 묶음을 통째로 가져다 줍니다. (= 캐시 라인)
• 내 책상엔 묶음을 4개까지만 올려둘 수 있습니다. (64 B ÷ 16 B = 4)
• 꽉 찼는데 새 묶음이 오면 → 제일 오래 안 쓴 묶음을 반납 (LRU)

히트(hit) = 필요한 숫자가 이미 책상 위 묶음 안에 있음 (서고 안 감)
미스(miss) = 없음 → 서고 다녀옴 → 그 묶음이 책상에 올라옴

float은 4바이트니까, 16바이트 묶음 하나에 숫자 4개가 들어갑니다.

1. "메모리 접근 3번"이 왜 3번인가

$s=Av$를 계산하는 코드는 이겁니다:

for (i = 0; i < 4; i++)
    for (j = 0; j < 4; j++)
        s[i] = s[i] + A[i][j] * v[j];

안쪽 한 줄이 실행될 때 메모리에 있는 변수를 몇 개나 건드리는지 세어봅니다:

• A[i][j]: 읽기 1회
• v[j]: 읽기 1회
• s[i]: 쓰기 1회

→ 한 줄 실행 = 메모리 접근 3회.

여기서 중요한 건, 이 3개가 메모리상 완전히 다른 위치에 있다는 겁니다. A는 A대로, v는 v대로, s는 s대로 떨어져 있어요. 그래서 각각 따로 "이거 지금 캐시에 있나?"를 물어봐야 합니다. 접근 1회 = 히트/미스 판정 1회입니다.

문제에서 "reads and writes will be cached"라고 한 게 바로 이 뜻입니다. s[i]에 쓰는 것도 캐시를 거치니까 세라는 것.

2. 그래서 총 48회

바깥 루프 i : 4번
안쪽 루프 j : 4번
→ 안쪽 문장이 4 × 4 = 16번 실행
→ 16번 × 접근 3회 = 48회

16번은 곱셈 횟수와 같습니다. 4×4 행렬 곱이니까 곱셈 16번, 당연하죠.
48이 분모입니다. 이 48번의 판정 중 몇 번이 히트냐가 답입니다.

3. R₁, A₁ 같은 건 어디서 나왔나

제가 임의로 붙인 묶음 이름표입니다. R은 Row(행), A는 컬럼-major일 때의 A 묶음. 헷갈리게 해서 죄송합니다. 어떻게 나온 건지 설명하면:
행렬은 우리 눈에 2차원이지만, 메모리는 1차원 줄입니다. 16개 숫자를 한 줄로 쭉 늘어놓은 다음, 4개씩 잘라서 묶음을 만듭니다.

Row-major = 행 순서대로 늘어놓기

메모리:  a e i m │ b f j n │ c g k o │ d h l p
         └ 1행 ┘  └ 2행 ┘  └ 3행 ┘  └ 4행 ┘
          묶음1     묶음2     묶음3     묶음4

Column-major = 열 순서대로 늘어놓기

메모리:  a b c d │ e f g h │ i j k l │ m n o p
         └ 1열 ┘  └ 2열 ┘  └ 3열 ┘  └ 4열 ┘
          묶음1     묶음2     묶음3     묶음4

이건 A₁~A₄. 묶음 하나 = 열 하나입니다.
여기에 v와 s도 각자 묶음이 하나씩 있습니다:

v 묶음 (V):  v1 v2 v3 v4     ← 4개가 한 묶음에 다 들어감
s 묶음 (S):  s1 s2 s3 s4

4. 히트/미스 판정하는 법

규칙은 딱 이거 하나입니다.

지금 필요한 숫자가 속한 묶음이, 책상 위 4자리 중에 있나?
있다 → 히트. 없다 → 미스 (서고에서 그 묶음을 가져와 빈 자리에 놓음. 자리 없으면 제일 오래 안 쓴 묶음을 버림)

이제 실제로 해봅시다. 연산(곱셈, 덧셈)은 캐시와 아무 상관 없습니다. 오직 "어떤 순서로 숫자를 만지는가"만 봅니다.

i = 1 (첫 번째 행: $s_1 = av_1 + ev_2 + iv_3 + mv_4$)

만지는 숫자 순서: a, v1, s1 → e, v2, s1 → i, v3, s1 → m, v4, s1

미스 3, 히트 9.
핵심: 4번에서 e가 히트인 이유는, 1번에서 a를 가져올 때 a e i m이 한 묶음으로 통째로 딸려왔기 때문입니다. 첫 행에 필요한 A 원소 4개가 전부 한 묶음 안에 있었던 거죠.

i = 2 (둘째 행: b, f, j, n)

b는 R₂ 묶음 → 책상에 없음 → MISS (빈 4번째 자리에 들어감). 그 다음 f, j, n은 전부 R₂ 안에 있으니 히트. v, s는 계속 책상에 있으니 히트.
→ 미스 1, 히트 11. 책상 = R₁ R₂ V S (꽉 참)

i = 3 (c, g, k, o)

c는 R₃ → MISS. 자리가 없으니 LRU로 하나 버려야 함. 가장 오래 안 쓴 건? R₂·V·S는 방금 2행에서 썼고, R₁은 1행 끝나고 안 썼음 → R₁ 버림. (R₁은 다시 안 쓸 거라 손해 없음)

→ 미스 1, 히트 11.

i = 4 (d, h, l, p)

똑같이 미스 1, 히트 11.

합계

미스=3+1+1+1=6
히트=9+11+11+11=42

Hit rate=42/48=87.5%

6. Column-major 추적

이번엔 첫 행에 필요한 a, e, i, m이 네 개의 서로 다른 묶음에 흩어져 있습니다.

a는 A₁=[a b c d] 안에
e는 A₂=[e f g h] 안에
i는 A₃=[i j k l] 안에
m은 A₄=[m n o p] 안에

미스 6, 히트 6. 책상엔 지금 A₃ A₄ V S가 있습니다.

i = 2 (b, f, j, n)
b는 A₁ 안에 있습니다. 그런데 A₁은 방금 7번에서 버렸습니다. → MISS → 다시 가져오면서 A₃를 버림.
그 다음 f는 A₂ → 이것도 아까 버렸음 → MISS → A₄를 버림.
j는 A₃ → 방금 버렸음 → MISS...

필요할 때마다 직전에 버린 걸 다시 불러오는 최악의 패턴입니다. 이걸 스래싱(thrashing)이라고 합니다.

→ 미스 4, 히트 8. (A는 4번 다 미스, v와 s 8번은 다 히트)
i=3, i=4도 똑같이 미스 4, 히트 8.

합계

미스=6+4+4+4=18,히트=30
Hit rate=30/48=62.5%