💵 캐시가 동작하는 아주 구체적인 원리: 하드웨어로 구현한 해시 테이블

<aside> 💡 목차

</aside>

어떻게하면 캐시메모리 탐색을 한 클럭 안에 끝낼수 있을까?

→ Direct-mapped 캐시의 경우

mod % 연산자를 활용하는 방법이 있다

<aside> 💡 0~9 자리를 mod % 3 연산자를 사용해 0~2 자리로 간소화

🔽

그림으로 표현하면 다음과 같다

</aside>

0~9 까지의 메모리 영역이 있다고 가정했을때

일반적인 방법으로 메모리를 탐색하면 10의 시간이 걸릴것이다.

하지만 이를 3으로 나눈 값을 메모리 주소로 쓰면?

0~9 값은 0~2 값으로 간소화되어 탐색시간을 단축시킬 수 있을것이다.

즉, 애초에 들어갈 수 있는 자리를 정해버리는 것이다.

크기를 키워, 아까 메모리의 크기는 8kb 이고 PC는 1워드라 했으니 PC가 탐색해야할 메모리 공간은 2048개가 있었다고 했다. (8kb = 4byte * 2,024)

즉 이는 주소가 2048개라는건데, 전체주소 2048에서 PC값 32를 나누면된다

그러면 인덱스값은 0~31 값을 가지게 될것이며,

같은 인덱스를 가진 값은 64개가 될것이다.

2048 % 32 = 0
2047 % 32 = 1
2046 % 32 = 2
.
.
.
2 % 32 = 2
1 % 32 = 1
0 % 32 = 0

Direct-mapped

1Bit Prediction - ping pong 문제 발생 가능

0	1	2	3	4	5	6	7	8	9

→→ 근데 이는 1Bit Prediction 문제가 있음

Direct-mapped cache는 단순성으로 인해 성능이 좋지만, 메모리 블록 주소가 비슷한 경우 동일한 캐시 블록에 매핑되어 충돌이 발생할 수 있습니다.

Set Associative

<aside> 💡 하지만 그럼에도 불구하고, 한 자리를 두고 경쟁하는 상황히 흔치는 않습니다…

공간적 지역성

에서, 코드는 한줄한줄 실행되기 때문에

메모리에도 순차적으로 다음칸 다음칸 들어가게 되어있음

그래서 나머지 연산자로 나눠도 값은 순차적으로 캐시 메모리 영역을 차지해서 경쟁은 잘 발생하지 않음…

전체 크기를 3으로 정하고

0 1 2 3 4 5 각각의 주소를 가진 코드가 실행된다고 가정했을때

0 1 2 0 1 2 …이런식으로 골고루 실행될것이기 때문에 정상적인 코드 실행 시나리오에서는 각 코드들이 자리를 두고 경쟁하진 않습니다

단! if문과 같은 branch문이 발생하면, 운나쁘게 나머지몫이 같은 값이 연속적으로 나올 수 있어서 메모리 경쟁 확률이 높아진다

</aside>