캐시

지역성

좋은 프로그램은 최근에 참조했던 데이터 근처의 데이터나
최근에 자신을 참조했던 데이터를 참조하려는 경향이 있다.

두 가지 지역성

시간 지역성

한 번 참조된 메모리 위치는 가까운 미래에 다시 여러 번 참조될 가능성이 높다.

공간 지역성

특정 메모리 위치가 참조되면, 가까운 미래에 근처의 메모리 위치를 참조할 가능성이 높다.

**  
운영체제 수준에서 지역성의 원리는 시스템이 메인 메미로리르 갖아 최근에 참조한  
가상 주소 공간 블록에 대한 캐시로 사용될 수 있게 해준다.

프로그램 데이터 참조의 지역성

int sumvec(int v[N]) {
    int i, sum = 0;

    for ( i = 0 ; i < N ; i++ ){
        sum += v[i]
    }
    return sum;
}

sum 변수는 for문에서 반복 참조되므로 좋은 시간 지역성을 갖는다.
반면 sum은 물리량이므로 공간 지역성이 존재하지 않는다.
-> sum 이외에 주변 메모리를 참조하지 않음 

v 벡터에 대해서 sumvec 함수는 좋은 공간 지역성을 갖는다.
-> for문을 이용해서 v벡터 주변 메모리에 순차적으로 접근하기 때문

각 v 벡터 원소에 대해서는 나쁜 공간 지역성을 갖는다.
-> 각 원소에 대해서는 단 한 번만 접근하기 때문에 캐시 활용도가 떨어짐 

// 좋은 공간 지역성을 가지고 있음, 즉 메모리를 순차적으로 참조(stride-1)
int sumarrayrows(int a[M][N]) {
    int i, j, sum = 0;

    for( i = 0; i < M; i++) {
        for(j = 0; j < N; j++) {
            sum += a[i][j];
        }
    }
    return sum;
}

// 나쁜 공간 지역성을 가지고 있음, 순차 접근이 아닌 행 단위로 접근 중(stride-N)
int sumarraycols(int a[M][M]) {
    int i, j, sum = 0;

    for(j = 0; j < N; j++)
        for(i = 0; i < M; i++)
            sum += a[i][j]
    return sum;
}

N 숫자가 증가하면 공간 지역성이 감소함  
\-> 1은 바로 옆 참조, N은 그 크기 만큼 이동 후 참조

**  
루프(반복문)는 명령어 선입에 대해 좋은 시간 및 공간 지역성을 갖는다.  
루프 본체가 작을수록, 루프 반복실행의 수는 더 커지고 지역성도 좋다.

메모리 계층 구조

캐시는 보다 크고 느린 디바이스에 저장된 데이터 객체를 위한 준비 영역으로
작고 빠른 저장장치이다.

메모리 계층구조의 중심 개념은 각 K에 대해, 레벨 K에 있는 보다 빠르고 더 작은 저장장치가
K + 1에 있는 더 크고 더 느린 저장장치를 위한 캐시 서비스 제공
Ex)
메인 메모리(DRAM)을 위한 캐시는 SRAM
HDD(Local Disk)를 위한 캐시는 DRAM 

K + 1 레벨의 저장장치는 연속된 데이터 객체 블록으로 나뉜다.
각 블록은 유일한 주소 또는 이름을 가진다. // 블록은 고정 크기(대부분) 혹은 가변 크기를 갖는다.
K 레벨 저장장치는 레벨 K + 1에 있는 블록들과 같은 크기의 더 작은 집합의 블록들로 나뉜다.
시간상 아무 때나 레벨 K에 있는 캐시는 레벨 K + 1에서 온 블록들의 부분집합의 사본을 포함 

** 
데이터는 항상 레벨 K와 K + 1사이에서 블록 크기의 전송 유닛 단위로 복사 된다.
인접한 계층 쌍들은 블록 크기 고정, 다른 레벨의 쌍들은 서로 다른 블록 크기를 가짐 
- SRAM - DRAM (같은 블록 크기), SRAM, HDD(서로 다른 블록 크기)

**
계층 구조가 낮은 고세 위치한 장치가 더 긴 접근 시간을 가진다.
접근 시간을 줄이기 위해 더 큰 블록을 사용 

캐시 적중

프로그램이 K + 1레벨에서 특정 데이터 객체 d를 필요로 할 때, 레벨 K에서 d를 먼저 찾는다.
만일 K에 d가 있다면 이를 캐시 적중이라고 함 

캐시 미스

프로그램이 K + 1 레벨에서 특정 데이터 객체 d를 필요로할 때, 레벨 K에서 d를 먼저 찾는다. 
만일 K에 d가 없다면 이를 캐시 미스라고 한다.
이후 K + 1 레벨 캐시에서 객체 d 블록을 찾아 K 레벨 캐시로 가져와 저장한다. 
만일 캐시가 가득 찼다면, 희생블록을 선택해 제거한 후 저장

캐시 미스 종류

캐시가 완전히 비어 있는 경우 - cold cache

**
배치 정책은 중요하며 구현하는데 비용이 큼
→ 랜덤으로 배치한 블록들의 위치를 찾는데 드는 비용이 크기 때문에 
→ 레벨 K + 1의 특정 블록을 레벨 K에 있는 블록의 작은 부분집합으로 제한하는 단순한 배치 정책 사용
Ex) 충돌 미스 배치 전략 
K + 1 레벨의 0, 4, 8, 12 블록은 K 레벨의 0번째 블록에 매핑(여기에만 저장 가능) 

연속된 루프는 동일한 배열의 원소들에 반복적으로 접근
이러한 블록들의 집합은 이 단계의 동작 집합이라고 함  
동작 집합 크기가 캐시 크기 보다 클 때, 용량 미스 발생

캐시를 관리하는 로직은 하드웨어, 소프트웨어 혹은 둘 다 사용될 수 있다. 
L1, L2, L3 캐시들은 캐시에 구현된 하드웨어 로직으로 전적으로 관리됨 
DRAM은 운영체제 소프트웨어와 MMU 조합으로 관리됨
AFS 같은 분산 파일 시스템은 로컬 머신에서 돌아가는 AFS 클라이언트 프로세서에 의해서 관리됨

캐시 메모리

CPU 레지스터와 메인 메모리 사이의 속도 격차를 줄이기 위해서  
L1, L2, L3 캐시가 레지스터와 메인 메모리 사이에 만들어짐

기본 캐시 메모리 구조

M = 2^m 개의 고유 주소로 구성 // m - 32비트, 64비트 
S = 2^s 개의 캐시 집합으로 구성 
E개의 캐시 라인들로 구성 // 각 캐시 집합의 라인들을 의미 
B = 2^b - 각 라인을 구성하는 블록 크기임 
→ 해당 라인이 의미있는 정보를 포함하는지 여부를 나타내는 유효비트 한 개
→ 캐시 라인에 저장된 블록을 유일하게 구분하는 태그 비트로 구성

**

캐시 크기 C는 모든 블록의 크기를 합하는 형태로 설명 
C = S X E X B                    // 태그비트와 유효비트는 포함되지 않음 

CPU가 메인 메모리 주소 A에서 하나의 워드를 읽으라는 load 명령어에 의해 지시를 받을 때
CPU는 주소 A를 캐시로 보냄, 
만일 캐시가 해당 워드의 사본을 주소 A에 가지고 있다면 , 이 워드를 즉시 CPU로 돌려보낸다.
→ 캐시는 어떻게 주소 A에 해당 워드의 사본을 가지고 있는지 알 수 있나 ???
→ 캐시는 요청된 워드를 간단히 주소비트만 조사해서 찾아낼 수 있도록 구성 됨

캐시 찾는 과정

s 집합 인덱스 비트는 S 집합 배열의 인덱스를 구성 
→ 집합 인덱스 비트는 워드가 어떤 집합에 저장되어야 하는지 알려줌 
→ 이를 알게 되면 A의 t 태그 비트는 집합의 몇 번째 라인이 워드를 포함하고 있는지 알려줌 
→ 집합의 라인은 유효비트가 1이고, 해당 줄의 태그 비트가 주소 A의 태그비트와 일치할 때만 해당 워드를 포함 
→ 집합 인덱스에 의해 식별된 집합 내의 태그로 라인을 찾았다면, b 블록 오프셋 비트를 사용하면 B-바이트 데이터 블록 내 워드의 오프셋을 알 수 있음

직접 매핑 캐시

각 캐시 집합 내에 단 하나의 캐시 라인만 존재하는 구조 
특정 메모리 주소는 캐시의 특정 집합에만 저장될 수 있음 
구조가 간단하고, 매핑 규칙이 정해져 있어 빠르게 특정 주소가 캐시에 있는지 확인 가능 
같은 캐시 라인에 여러 블록이 경쟁하므로 자주 캐시 미스 발생

집합 결합성 캐시

캐시가 여러 개의 집합으로 나뉘고, 각 집합엥 여러 개의 캐시 라인이 존재 
메모리 주소는 특정 해시 함수를 통해 특정 집합에 매핑되지만,
해당 집합 내에서는 여러 라인 중 어느 라인에 저장될지 자유로움 

장점
직접 매핑 캐시에 비해 캐시 충돌이 줄어든다. // 동일한 집합에 여러 개의 라인을 저장할 수 있기 때문
충돌이 줄어들어 캐시 미스가 감소하고 캐시 효율이 높아짐

단점 
구조가 복잡해지므로, 태그 비교에 필요한 하드웨어 비용 증가

완전 결합성 캐시

캐시 전체가 하나의 집합으로 간주되며, 모든 메모리 블록이 캐시의 어느 라인에 저장될 수 있는 구조
특정 메모리 블록이 캐시에 저장될 때, 전체 캐시 내 어느 라인에든 자유롭게 배치될 수 있음 
태그 비교를 캐시 전체 라인에 대해 수행해야함 

장점
캐시 내의 어느 라인에든 데이터를 저장할 수 있어, 캐시 충돌이 거의 발생하지 않으므로 매우 높은 캐시 효율을 가진다.
작은 용량의 캐시에 적합

단점
모든 라인의 태그를 비교해야하므로, 하드웨어 비용이 매우 높고 속도가 느릴 수 있다.
비용과 복잡성 때문에 큰 용량의 캐시에는 거의 사용되지 않고 TLB와 같은 작은 캐시에서 사용됨

인덱스가 중간 비트인 이유

상위 비트를 인덱스로 사용하면, 동일한 연속적인 메모리 블록들은 동일한 캐시 집합으로 매핑됨  
연속적인 배열 원소가 같은 집합에 속하게 되면 캐시를 계속 변경해줘야하는 경우가 발생할 수 있음

Ex)회색부분(0100 ~ 0111)을 순차적으로 접근했을 때, 캐시 01라인을 계속 변경해줘야함

캐시 크기의 영향

더 큰 캐시는 적중 비율을 높여주는 경향이 있음 
크기가 너무 크면, 메모리가 빨리 동작하기 어려움 ( 적중 시간이 길어짐 )

블록 크기의 영향

블록의 크기가 크면 공간 지역성을 활용하여, 적중 비율을 높여줄 수 있다.
- 더 큰 블록들을 더 적은 캐시 라인 수를 의미
- 더 큰 블록은 더 긴 전송 시간을 필요로 하므로 미스 비용에 안 좋은 영향을 미친다.
- 액세스 시간이 오래 걸리는 경우에 사용하는게 적합

결합도의 영향

집합당 캐시 라인 수의 선택이 미치는 영향을 의미 
E 값, 즉 라인 수가 많은 경우 캐시가 충돌 미스로 인한 쓰래싱 위험을 감소시킨다.
하지만 높은 결합도를 얻기 위해서는 많은 비용과 시간 소요 
→ 증가한 복잡성 때문에 적중 시간이 길어짐 
**** 결합도의 선택은 결국 미스 비용과 적중 시간 간의 절충에 의해 결정 됨