6.3-The_Memory_Hierarchy

프로그램이 k + 1 레벨 장치의 d 데이터가 필요할 때,
k 레벨에 이미 d 데이터가 있는 경우, 이라고 부른다.
프로그램은 더 빠르게 d 데이터를 k 레벨 장치에서 읽게 된다.

반대로, k 레벨 장치에서 찾지 못한 경우, 라고 한다.
Miss 가 발생한 경우, k 레벨 장치는 해당 데이터를 포함하는 block 을 Caching 한다.
이 과정에서 기존의 block 에서 덮어씌울 수도 있다.

덮어씌우는 과정은 , the Block 이라고 한다.
이 때 덮어씌워지는 Block 은 이라고 불린다.
어떤 Block 이 덮어씌워질지는 에 의해 결정된다.

그저 무작위로, 혹은 사용한지 가장 오래된 Block 등 다양한 정책이 존재한다.

덮어씌우는 과정을 통해 해당 데이터는 미래에 다시 접근이 일어나길 기대하면서,
k 레벨 장치에 남게 된다.

Cache Miss 에는 다양한 요인이 있다.

만약 k 레벨 장치가 비어있다면, 어떤 데이터에 대해서도 Miss 가 발생한다.
이러한 비어있는 상태를 혹은 라고 한다.
Cold Miss 는 중요한데, 이 Miss 는 보통 일시적인 현상이기 때문이다.
특히 안정된 상태 즉, 반복된 메모리 접근에 의해 Cache 가 Warmed up 된 상태에서는 잘 일어나지 않는다.

Miss 가 발생할 때, k 레벨 장치는 Placement Policy 에 따라 해당 데이터를 Caching 해야한다.
가장 유연한 방법은 모든 k + 1 레벨의 Block 에 대해 모든 k 레벨의 Block 에 저장할 수 있도록 허용하는 것이다.
하지만, 무작위적으로 저장하는 방법은 높은 레벨의 장치(CPU에 가까운) 에서 허용하기엔 너무 비싸다.

그래서, 하드웨어적 Cache 는 보통 더 간단하고, 제한적인 Placement Policy 를 채택한다.
예를 들어, "k + 1 레벨 장치의 Block i 는 k 레벨 장치의 i mod 4 에 저장한다" 가 있다.
이에 따르면, 0, 4, 8, 12 Block 은 0 에만 저장될 수 있다.

이러한 종류의 제한 정책은 를 일으킬 수 있다.
이는 Cache 가 충분히 Hit 할 수 있을 정도로 크지만, 정책에 의해 같은 Block 에 저장되서
실패하는 경우이다.

예를 들어, 0, 8, 0, 8 순서로 Block 에 접근하고자 한다면,
i mod 4 에서는 계속 다른 Block 을 Caching 하게 되어, Miss 가 발생하게 된다.

프로그램은 Loop 같이 Sequence of Phases 로 작동하며,
특히 각 Phase 는 일정한 수의 고정된 Cache Block 에 접근하는 경우가 있다.
예를 들어, Loop 는 같은 배열을 계속 참조하는 경우가 많다.
이러한 고정된 Cache Block 집합을 라고 부른다.

이 Working Set 의 크기가 Cache 의 크기를 초과할 때,
를 겪게 된다.
즉, 이 Miss 는 Cache 가 해당 Working Set 을 다루기엔 너무 작아서 생기는 문제이다.

메모리 계층구조는 각각의 저장장치는 다음 레벨의 장치의 Cache 역할을 한다는 것이다.
각 레벨에서는 이 Cache 를 관리하는 무언가가 필요하다.
이 무언가는 Cache 장치를 Block으로 나누고, 다른 레벨간에 Block 을 전달하고, Hit 또는 Miss 가 발생했는지 결정하고, 그 결과에 따라 처리한다.
이 무언가는 하드웨어적 혹은 소프트웨어적 또는 2개 모두를 합친 방식으로 구현된다.

예를 들어, 컴파일러는 레지스터 파일을 관리한다.
L1, L2, L3 는 Cache 안에 존재하는 하드웨어적 논리 회로가 관리한다.
Virtual Memory 는 OS의 소프트웨어와 CPU의 주소변환 하드웨어에 의해 관리된다.
대부분의 경우, Cache 는 자동적으로 작동하여, 프로그램에서 특별히 조작할 필요가 없다.