[컴퓨터 구조] 25. Cache (3) - 성능 개선

캐시를 적용한 CPU 성능

이제 캐시를 적용했을 때 CPU의 성능 (실행 시간)을 한번 생각해보기로 하자.

 

 

먼저 CPU의 실행시간은 (명령어의 개수) * (CPI) * (주기) 로 구할 수 있었다.

이때 명령어의 개수 * CPI 는 결국 프로그램을 실행하는 과정에서 요구하는 총 cycle 수로 볼 수 있으므로

CPU의 실행시간은 (clock cycle) * (주기) 라고 할 수 있다.

 

이때 clock cycle 을 CPU에서 명령어를 실행시키는데 필요한 cycle 과, 메모리를 접근하는데 시간이 오래 걸려서 CPU가 stall 하는 cycle 로 구분해서 생각해보자.

 

이때, 만약 캐시 Hit 가 발생하면 이때는 추가적인 CPU cycle이 필요하지 않다고 해보자.

(즉, 캐시 Hit 가 발생하면 MEM stage 가 1cycle에 실행된다.)

 

그렇다면 Memory-stall clock cycles 는 Cache miss가 발생했을 때 추가적으로 소모되는 사이클 수라고 생각할 수 있다.

이때 Memory-stall clock cycle을 다시 read-stall cycle 과 write-stall cycle로 구분할 수 있다.

 

 

그리고 단순하게 생각히기 위해, Cache Miss가 발생했을 때는 Read miss 나 write miss 모두 같은 miss penalty를 갖는다고 해보자.

(실제로는 read miss에 대한 페널티가 더 크다. 메모리를 읽으려고 하는데 stall 이 발생하면 그 값이 올 때까지 기다려야 처리할 수 있지만, 쓰기는 stall에 걸리더라도 그냥 알아서 쓰라고 명령만 던져두고 그 시긴동안 다른 일을 할 수도 있기 때문이다.)

 

그러면 이제 Memory stall clock cycle 을 파악하기 위해, 프로그램이 갖고 있는 메모리 접근 횟수, 그리고 이 중에서 몇 번의 미스가 발생하는지 Miss Rate, 그리고 각 미스가 발생했을 때 추가되는 miss penalty 를 모두 곱하는 것으로 계산해볼 수 있다.

 

 

예시 1

 

CPU가 위와 같은 구조를 갖는다고 해보자.

이때 아래와 같은 CPU를 가정해보자.

 

Instruction-Cache 는 2% miss rate

Data-Cache 는 0% miss rate (perfect)

miss penalty = 100 cycles

Base CPI = 1 (캐시 hit 했을 때, 메모리에 1cycle에 접근한다.)

 

이때의 n개의 명령어를 갖는 프로그램을 실행하는데 걸리는 CPU time을 계산해보자.

 

CPU time

= (total cycle) x (T)

= (CPU execution clock cycles + memory stall clock cycles) x (T)

 

CPU execution clock cycles = n

(메모리 접근 명령어 실행도 기본적으로 1 cycle 소모, miss 발생시에는 페널티가 '추가' 된다. 명령어를 전체를 실행하는데 필요한 사이클 수가 정확하게 n은 아니지만, 명령어가 많다면 n에 수렴하므로 n으로 표기하였다.)

 

Memory stall clock cycles

= (memory acess 횟수) x (miss rate) x (miss penalty)

= n x 0.02 x 100

= 2n

 

모든 명령어는 instruction fetch 과정을 거치므로 Inst-Cache에 n번 접근한다.

이때 2%의 접근에서는 cache miss가 발생하므로 100 사이클이 '추가로' 소모된다.

 

따라서 명령어를 실행시키는데 필요한 총 사이클 수는 n + 2n = 3n 이다.

 

캐시 miss 가 2% 밖에 없음에도, 워낙 페널티가 커서 100% 캐시 Hit 가 발생했을 때보다 성능이 3배 안 좋아지는 것을 볼 수 있다.

 

예시 2

 

이번엔 똑같이 n개의 명령어를 가진 프로그램을 실행시킬 때 Data-Cache 에서도 Miss가 발생할 수 있다고 가정해보자.

그리고 load, store 명령어는 전체 명령어의 36%를 차지한다고 하자.

 

CPU Time

= (Whole Clock Cycles) * (T)

= (CPU execution clock cycles + Memory-stall Clock Cycles) x (T)

 

CPU execution clock cycles = n

 

Memory-stall Clock Cycles

= Inst Cache stall clock cycles + Data Cache stall clock cycles

= n x 0.02 x 100 + n x 0.36 x 0.04 x 100

= 2n + 1.44n

= 3.44 n

 

따라서 이 프로그램을 실행하는데 필요한 전체 clock cycle 수는

 

n + 3.44n = 4.44n

 

그래도 98% hit rate, 96% hit rate 면 꽤 준수한 hit 성능이라고 생각했는데, hit가 100% 가 되는 이상적인 상황에 비해 무려 4.44배나 느리다는 것을 알 수 있다.

 

---

AMAT ( Average Memory Access Time )

위의 2개 예제에서는 Cache Hit 가 발생했을 때 cycle 이 1 cycle 소모된다고 가정했었다.

그런데 실제로는 꼭 그렇지 않을 수 있다.

예를 들어 인텔 Core 2 Duo 의 경우, L1 캐시의 hit latency 가 3 cycle 이다.

 

그래서 이 Hit time 까지 고려해서 메모리에 접근하는 시간이 얼마나 걸리는지 따지는 지표가 AMAT이다.

AMAT는 다음과 같이 계산한다.

 

 

잘 생각해보면, Hit Time은 Hit 일 때도 존재하고, Miss 일 때도 존재한다.

여기에 Miss가 발생하면, '추가적으로' 페널티 cycle이 들어가는 것이다.

따라서 Miss rate x Miss penalty 를 더해준다.

Miss가 발생하면 메모리에서 block 데이터를 읽어서 캐시에 올려두고, 캐시에서 다시 CPU로 데이터를 전달하는, Cache Hit 와 같은 과정을 Miss 에서도 똑같이 수행하기 때문에 Hit Time 은 Hit, Miss 모두 고려된다.

 

예시

 

다음과 같은 조건이 주어졌을 때, AMAT을 계산해보자.

 

AMAT

= Hit time + Miss rate x Miss penalty

= (1 cycle + 0.05 x 20cycles) x (1ns / cycle)

= 2 cycle x (1 ns / cycle)

= 2 ns

 

이 상황에서는 Hit 가 발생하면 1 cycle 이 소모되고, Miss가 발생하면 21 cycle이 소모된다.

즉, 95% 확률로는 1 사이클, 5% 확률로는 21 사이클이 소모되는 것을 고려하여 계산한 결과가 평균 2 cycle 인 것이다.

(0.95 x 1 + 0.05 x 21 = 2 cycle)

 

---

캐시 성능 개선

그러면 어떻게 했을 때 CPU 성능을 더 끌어올릴 수 있을까?

크게 2가지 관점에서 접근할 수 있다.

 

1. Hit Rate 를 더 끌어올린다.

2. Miss Penalty 를 감소시킨다.

 

Hit Rate 개선

Hit Rate는 어떻게 늘릴 수 있을까?

가장 직관적인 방법은 캐시의 크기를 늘리는 것이다.

캐시의 크기가 늘어날 수록 Miss Rate 가 감소하고, Miss Rate 가 감소하면 CPU Time이 낮아진다.

이 방법은 제일 효과적인 방법이긴 하지만, 캐시 크기를 늘리는게 쉽지는 않다.

지금도 계속 캐시 크기를 늘리려고 노력하고 있고, 최신 CPU일 수록 캐시의 크기가 조금이라도 더 크기는 하다.

하지만 캐시도 결국 CPU 내에 있어야 하니 실리콘을 사용해서 만드는데, 실리콘 땅이 너무 비싸기 때문에 코어의 디자인에 더 높은 우선순위를 두지, 캐시 영역을 넓히는데 쓰기는 쉽지 않다.

또 캐시를 무작정 넓히더라도 너무 크게 만들면서 캐시에 한번 접근하는데 더 오랜 시간이 걸릴 수도 있다.

 

그래서 Hit rate 를 끌어올리는 다른 테크닉으로 Direct mapped Cache 대신 다른 캐시 구조를 사용하는 방법이 있다.

 

1. Direct Mapped Cache

캐시에 가져다 놓아야 할 메인 메모리의 블록이 갈 수 있는 곳이 딱 1군데로 정해져있다. (직접 매핑)

메인 메모리의 블록이 갈 위치는 block address 에서 인덱스를 나타내는 하위 비트를 보고 매핑한다.

 

위 그림과 같이 8개 캐시 블록이 있을 때는, 0부터 7까지 인덱스를 보고 하나를 직접 매핑해서 들어간다.

만약 같은 인덱스를 가리키는 다른 태그를 갖는 메모리 블록이 접근하면, 기존 캐시 블록 내용은 방출되고, 새로 접근한 메모리 블록 내용을 저장한다.

 

2. Fully associative cache

Direct Mapped Cache 의 정반대 방식이다.

메인 메모리의 블록이 캐시의 어디로든 갈 수 있는 방식이다.

만약 캐시가 16개의 블록을 갖는다면, 메모리에서 읽어온 블록이 16개 블록 중 아무곳이나 갈 수 있다.

 

위 그림과 같이 8개 캐시 블록이 있을 때는, 인덱스를 보지 않고 직접 바로 이 셋에 접근해서 캐싱한다.

자신이 갖고있는 모든 캐시 블록을 하나의 셋으로 묶어두고, 그 set으로 접근할 수 있는 8개의 way를 둔다.

그러면 8개의 캐시 블록이 모두 차기 전에는 계속 여분 공간이 있으므로, Cache 에 저장된 데이터가 방출될 확률을 낮출 수 있다.

 

 

3. n-way set associative cache

이 방식은 1번과 2번 중간에 있는 방식이다.

way는 메모리에서 가져온 block이 캐시에서 갈 수 있는 길을 말한다.

그리고 각 way가 연결된 캐시 블록의 집합을 set 이라고 한다.

그래서 위 용어를 해석하면, 메모리에서 가져온 블럭은 n개의 길이 존재하는 set으로 매핑될 수 있다는 의미가 된다.

 

위 그림과 같이 8개 캐시 블록이 있을 때는, 인덱스가 가리키는 것이 set 인덱스가 되어, 인덱스가 가리키는 셋으로 가서 적절한 way를 선택해 데이터를 저장한다.

만약 같은 set 인덱스를 가리키는 블록이 추가로 들어오면, 기존 데이터를 방출하는 게 아니라, 그 set에 있는 여분 블록 공간에 새로 들어온 블록을 저장할 수 있으므로 무조건 방출시킬 필요가 없다.

따라서 어떤 면에서는 Miss Rate를 낮출 수도 있다고 볼 수 있다.

 

만약 2-way 라면 메모리에서 가져온 블록이 캐시에서 갈 수 있는 길의 개수가 2개이다.

Direct Mapped Cache는 사실 1-way set associative cache 라고 볼 수 있다.

이 길을 극단적으로 늘려서 캐시 블록 개수만큼 way를 퍼뜨리면 그때는 Fully associative cache가 된다.

 

그리고 종합해보면, 각 set마다 n개 way를 가지고 있기 때문에, set 개수와 way 개수를 곱하면 캐시가 갖고 있는 전체 캐시 블록의 개수가 되는 것도 알 수 있다.

---

그래서 8개의 블록으로 구성된 캐시는 아래와 같이 다양하게 구현될 수 있다.

 

 

가로줄의 개수를 set의 개수로 보고, 세로줄에서 (Tag + Data) 묶음의 개수를 way의 수로 보면, 위 그림은 one-way set associative cache 이며, direct mapped cache와 같다.

(1-way 일 때는 set 라는 개념이 없으니 block 이라는 개념으로 표기한다.)

 

2-way set 방식은 하나의 set 가 2개의 way를 갖는 방식이다.

따라서 8개의 캐시 블록을 2개씩 묶으면 4개의 set가 나온다.

 

 

같은 방식으로 4개의 way로 묶으면 2개의 set가 나올 수 있다.

 

 

8개의 way로 묶으면 하나의 set가 나오며, 이 방식은 fully associative와 같다.

 

---

예시

 

1 block이 4byte 인 16KB 캐시가 있다고 해보자.

이 캐시를 4-way set associatvie cache로 구성한다고 해보자.

 

이 캐시에는 몇 개의 block이 있을까?

16KB = 16 x 1024 byte

4byte 로 나누면 4 x 1024 개의 블록이 있음을 알 수 있다.

 

이때 4-way set 이라는 의미는, 메모리 블록 하나가 자신에게 주어진 인덱스를 보고 선택할 수 있는, 블록으로 갈 수 있는 길이 4개라는 의미이므로, 하나의 set에 4개의 블록이 할당되어 있다.

따라서 set의 관점에서는 1024개의 set이 있다.

 

따라서 다음과 같이 1024개의 셋이 존재한다.

 

따라서 32bit 주소에서 byte offset을 빼고 남은 word address 가 곧 block address 이고, 여기에서 하위 10bit로 인덱스를 구분하면 위와 같은 그림으로 캐시에 접근할 수 있다.

이때 남은 20bit 태그는 해당 인덱스가 가리키는 4개 캐시 블록의 태그, valid bit 를 확인해보며 일치하는 태그를 찾아서 cache hit, cache miss를 판단한다.

 

이를 통해 direct 방식이 제일 저렴하고, n-way 는 디자인할 때 조금 더 비싸고, fully 는 이런 비교 로직이 정말 많이 들어가겠다는 것을 알 수 있다.

 

최종적으로 위와 같은 그림으로 Hit 여부와 hit 데이터를 가져오는 모습을 볼 수 있다.

 

Associative Cache 비교

Fully Associative 캐시는 메모리 블록이 캐시의 어떤 블록에든 저장될 수 있도록 하는 방식이다.

따라서 다른 데이터가 방출되는 것을 막아주는 효과가 있을 수 있으나, 대신 하드웨어적으로 매우 비싼 비용을 치루는 것을 알 수 있다. (모든 캐시 블록과 비교하는 하드웨어 로직이 필요하기 때문)

 

n-way 는 fully 보다는 조금 저렴하게 (적은 하드웨어 비용으로) 사용할 수 있음을 알 수 있다.

 

이제 다시 캐시 성능 이야기로 돌아와서, direct mapped cache 에서부터 fully associative cache로 갈수록 Hit Rate가 어떻게 변화하는지 살펴보자.

 

먼저 각각의 캐시는 4개의 1 word block 으로 구성되어 있다. (block 1개의 크기가 1word, 그런 블록 4개로 구성된 캐시, 즉, 4 byte x 4 = 16byte 캐시이다.)

그리고 CPU는 8bit 주소 체계를 사용한다고 하자.

 

그리고 0, 8, 0, 6, 8 의 block address 순서대로 lw 명령어를 통해 메모리에 접근한다고 하자.

 

Direct Mapped Cache

 

먼저 direct mapped cache의 경우, 1-way를 가지므로 위와 같은 캐시 구조를 갖는다.

또한 8 bit 메모리 주소는 다음과 같이 구분된다.

index가 2bit 인 이유는 block 의 개수가 4개 이기 때문이다.

0, 8, 0, 6, 8 의 주소를 차례대로 접근한다면, 각각의 주소값을 8bit로 나타내었을 때 표와 같다.

표에는 8bit byte address 와, 6bit word address ( = block address ) 가 있다.

각각의 cache 인덱스는 block address 의 하위 2bit를 통해 알 수 있다.

 

1. lw 0

0번 주소에 접근하면, cache index 0 에 먼저 접근한다.

이때는 아직 캐시에 데이터가 없으므로 valid 비트부터가 0이다. 따라서 cache miss 가 발생한다.

(이렇게 아직 접근한 적 없는 데이터를 요청해서 발생하는 miss 를 cold miss 라고 한다.)

read 에서 miss 가 발생하는 경우, 메모리에서 데이터를 블록단위로 읽어 캐시에 할당한 뒤, 캐시가 CPU로 서비스한다.

 

따라서 캐시는 아래와 같이 데이터가 저장된다.

 

2. lw 8

8번 주소의 데이터를 읽을 때는 마찬가지로 캐시의 0번 인덱스 블록을 읽으려고 할 것이다.

이때는 캐시에 데이터가 들어있지만 tag가 다르므로 역시 cache miss 가 발생한다.

이 miss 도 cold miss 이다.

비록 캐시에는 데이터가 들어있었지만 전체적 관점으로 봤을 때 8번 주소의 데이터는 처음 요청하는 것이기 때문이다.

 

3. lw 0

다시 0번 주소의 데이터를 읽을 때는 tag가 다르니 miss가 발생한다.

이때는 기존에 0번을 읽어서 캐시에 쓴 적이 있으나, 8번과의 경쟁에 의해 덮어씌워져서 발생한 miss 라고 해서 conflict miss 라고 한다.

 

4. lw 6

다음으로 6번 주소의 데이터를 읽을 때는 index가 2라서 처음 접근하는 인덱스이므로 valid 가 0이다.

이때 발생한 cache miss 도 6번 주소에 대해서는 처음 접근하므로 cold miss 라고 볼 수 있다.

 

5. lw 8

8번 주소는 다시 cache miss 가 발생하며, 이 miss 는 conflict miss 이다.

8번 주소의 데이터는 읽은 적이 있으나 0번과의 경쟁에 의해 밀려났기 때문이다.

 

이렇게 direct mapped cache는 5번의 lw 명령어에 대해 5번의 miss 가 발생했다. (3번의 cold miss, 2번의 conflict miss)

 

2-way set associative cache

 

2-way set associative cache 의 경우, 하나의 인덱스로 접근할 수 있는 길이 2개가 있으므로

위 그림과 같이 4개의 캐시 블록을 2개씩 묶은 2개 set로 구성했다고 볼 수 있다.

 

이제 index가 0, 1 로 2개밖에 없으므로 index bit 는 1개만 있으면 된다.

 

따라서 tag bit의 길이가 1bit 증가한 5bit가 된다.

 

이제 이 캐시에 구조에 대해 아까와 같은 명령어를 실행시켜보자.

참고로 이 상황에서는 모든 주소(0, 6, 8) 에 대해 index 가 0을 가리킨다.

이번엔 설명을 간략화하고 빠르게 과정을 본다.

 

1. lw 0

0번 주소는 접근한 적 없으므로 cold miss 발생

 

0번 인덱스의 첫번째 블록에 데이터를 가져와 저장한다.

 

2. lw 8

8번 주소는 접근한 적 없으므로 cold miss 발생

 

0번 index 가 가리키는 셋에서 남은 블록에 8번 주소의 데이터를 캐싱한다.

 

3. lw 0

0번 주소는 캐싱되어 있으므로 cache hit 발생

 

4. lw 6

이 예제에서는 6번 주소도 index 0 으로 접근한다.

아직 6은 접근한 적이 없었으니 cold miss 가 발생한다.

이때 어떤 데이터를 방출하고 6을 저장해야할까?

 

이때는 캐시 디자인에 따라 다르겠지만 temporal locality 원칙을 고려한다면 8번을 빼게 될 것이다.

왜냐하면 0번은 직전에 접근했었기 때문이다.

가장 최근에 접근한 데이터는 이후에 또 접근할 가능성이 높다고 보는 것이 temporal locality 이다.

 

그러면 위와 같이 캐시에 저장된다.

 

5. lw 8

이때는 conflict miss 가 발생한다.

temporal locality 에 의해 0번 주소의 데이터를 방출하고, 8번 주소의 데이터를 쓴다.

 

이렇게 2-way 방식으로 캐싱하는 경우, conflict miss 가 1회 줄어드는 것을 알 수 있다.

 

Fully Associative cache

 

fully associative 방식의 캐시는 위와 같이 1개의 set로 구성된 4-way associative cache와 같은 구조를 띈다.

이때 메모리 주소를 분할하는 방식을 보면

 

이제는 인덱스 비트가 필요없다는 것을 알 수 있다.

어차피 인덱스는 1개밖에 없기 때문이다.

대신 tag 비트가 6개로 늘어났다는 것을 알 수 있다.

 

1. lw 0

cold miss 가 발생하여 캐싱한다.

 

2. lw 8

cold miss 가 발생하여 캐싱한다.

 

3. lw 0

캐시 히트가 발생한다.

 

4. lw 6

cold miss 가 발생하여 캐싱한다.

 

5. lw 8

캐시 히트가 발생한다.

 

이렇게 fully associative 방식으로 캐시를 구성하는 경우, conflict miss 의 개수가 더 줄어들었음을 알수 있었다.

---

성능 비교

 

이번엔 associative cache 사이에 성능을 비교해보자.

그러면 위 그림과 같은 그래프로 나타낼 수 있다.

 

캐시의 용량이 증가할 수록 miss rate가 감소하는 것은 direct mapped cache와 비슷하다.

여기에 way 개수를 늘리면 miss rate가 감소하는 것을 알 수 있다.

그런데 무작정 way를 늘린다고 항상 감소하지는 않았다. 그대로 유지되거나 오히려 증가하는 경우도 있다.

 

그리고 이렇게 실험적으로 보았을 때, direct mapped cache 에서 2-way 방식으로 캐시를 구성할 때 miss rate가 제일 크게 줄어드는 것을 볼 수 있다. (conflict miss가 크게 줄어들기 때문이다.)

반면 그 이후에는 감소폭이 매우 작은데, 이는 '한계 효용 법칙' 과 비슷한 원리이다.

direct mapped cache가 제일 cache miss 가 자주 발생하기 쉬운 구조이기 때문에, 이 상황에서 way를 조금만 늘려도 크게 miss가 줄어드는 것을 관찰할 수 있고, 어느 정도 줄인 이후에는 way를 늘려도 miss가 줄어드는 폭이 감소한다.

이걸 영어로 표현한다면, 캐시 구조를 바꿔서 얻을 수 있는 gain return이 줄어든다고 해서 dimishing return 이라고 부르기도 한다.

 

---

 

Associative Cache 의 주소 범위

이전 예제를 살펴보면서 관찰했던 내용 중 하나는 캐시의 크기가 고정되어 있을 때 direct mapped cache 에서 fully associative로 갈수록 (associativity가 2배 증가할 때마다) index 비트가 하나씩 줄어들고 tag bit 길이가 하나씩 늘어나는 것을 알 수 있었다.

 

 

이를 그림으로 나타내면 위와 같다.

참고로 block offset 은 블록 내의 워드를 선택하는데 사용된다.

byte offset은 워드 내에 몇번째 바이트를 보고 있는지 파악하는데 사용된다.

 

direct mapped cache 의 경우, comparator가 1개만 있으면 되기 때문에 하드웨어 설계 비용이 제일 적다고 볼수 있다.

 

Replacement Policy

이 내용은 캐시에서 꽤 중요한 내용이다.

캐시는 자주 사용될 것으로 예측되는 데이터를 담아두려고 하지만, 그럼에도 불구하고 miss가 발생할 수 있다.

이때 set 안에 남은 블록이 없어서 기존에 캐싱한 블록을 방출하고, 새로 데이터를 캐싱해야 할 때, 어떤 블록을 방출할지 결정하는 방법에 대해 정리해보자.

 

우선 direct mapped cache는 하나의 index 가 하나의 캐시 블록을 직접 가리키므로, 어떤 블록을 방출할지 고민할 필요가 없다. 인덱스가 가리키는 블록을 바로 방출하면 된다.

그리고 이런 점때문에 conflict miss가 자주 발생한다.

 

set associative 캐시부터는 고민이 필요하다.

만약 valid 비트가 세팅되지 않은 캐시 블록이 있다면, 우선 그 곳에 캐싱을 하면 된다.

하지만 만약 valid 비트가 모두 세팅되어 있다면 이제 어떻게 방출할지 policy를 고민해야 한다.

 

위에 예제에서는 temporal locality 원칙에 따라 가장 최근 사용된 데이터를 남기고 나머지를 방출하는 방식을 사용했다.

이 방법을 조금 더 구체적으로 정의한 방법으로 LRU (Least Recently Used) 방식이 있다.

말 그대로, 사용된지 가장 오래된 블록부터 방출하는 방법이다.

이 방식은 locality 측면에서 볼 때는 제일 합리적인 방법이다.

 

그런데 어떻게 가장 오래된 블록을 확인할 수 있을까?

사용된지 가장 오래된 블록을 알려면 각각의 블록이 어떤 순서대로 쓰였었는지 그 순서를 트래킹해야한다.

 

그렇다면 2-way 일 때, LRU 방식을 구현하려면 몇 개의 비트가 필요할까?

1개 비트만 있으면 충분하다. 누가 가장 오래전에 쓰엿는지만 파악하면 나머지 하나가 가장 최근에 쓰인 블록이기 때문이다.

 

반면 4-way 일 때는 몇 개의 비트가 필요할까?

얼핏 생각하면 사용된지 가장 오래된 블록을 4개의 블록 중에 지정하면 되니까 2bit만 있으면 될 것 같다.

하지만 우리가 트래킹해야하는 것은 '순서' 이다.

따라서 가장 오래된 블록, 그 다음으로 오래된 블록, .... 과 같이 순서를 기억하고 있어야 한다.

 

4-way 에서 등장할 수 있는 순서의 조합은 4! = 24 가지이다.

따라서 이 각각의 조합을 모두 구분해서 저장하려면 5개의 bit가 필요하다.

 

아직 4-way 밖에 안되었는데도 벌써부터 bit 오버헤드 비용이 빠르게 증가했다.

8-way로만 증가해도 LRU를 완벽하게 구현하도록 디자인하는 것은 쉽지 않다는 것을 알 수 있다.

 

그래서 실제로 CPU를 디자인할 때는, 특히 way의 개수가 많다면, LRU를 완벽하게 디자인하지 않는다.

LRU를 완벽하게 디자인하지 않는 또 다른 이유는, 실제로 구현해보니 그냥 랜덤하게 방출해도 LRU 대비 그렇게 나쁘지 않다는 것을 실험적으로 알 수 있었다.

 

앞선 예시에서도 LRU를 완벽하게 적용했을 때 오히려 conflict miss가 확률적으로 일어나는 경우도 볼 수 있었다.

따라서 LRU가 수학적으로 가장 합리적일 것 같지만, 실제로는 LRU는 하드웨어를 디자인하는 비용을 많이 요구하는 것 대비, 성능을 그렇게 향상시키지 않는다는 것을 알 수 있었다.

 

참고로 자주 사용하는 policy 중에는, not most recently used 라는 기법도 있다.

이 기법은 locality를 쓰기는 쓰되, 가장 오래된 것을 방출하는 것에 집중하기보다, 최근 것을 내보내지 않는 것에 집중하자는 정책이다.

 

LRU 예시

 

LRU를 사용하는 경우, 이렇게 각 set 마다 LRU 비트가 추가적으로 붙는다.

지금처럼 2-way 의 경우에는 1bit씩 추가로 붙는 것을 알 수 있다.

---

Miss Penalty 개선

Miss Penalty가 큰 이유는 Miss 가 발생했을 때 바로 메모리를 거쳐서 데이터를 가져오기 때문에 큰 페널티가 필요했다.

따라서 Miss Penalty를 개선하는 제일 간단한 방법은 L1 캐시와 Main Memory 사이에 계층을 두껍게 두는 것이다.

중간중간에 L2, L3 와 같은 캐시를 두어서 Miss 가 발생했을 때 Main Memory 보다는 조금 더 빠르게 데이터를 얻어올 수 있도록 설계해서 Miss Penalty를 개선할 수 있다.

 

 

이렇게 다양한 계층을 사이에 두어서 Miss Penalty를 감소시킬 수 있다.

L1 캐시에 대한 페널티를 줄이기 위해 L2 캐시를 두고, L2 캐시의 페널티를 줄이기 위해 L3 캐시를 둔다.

 

위 그림에 한해서 각 계층의 특징을 살펴보면

L1 캐시 (Primary Cache) 는 작지만 매우 빠르게 만드는 것이 중요하고,

L2 캐시는 이보다 느리지만 조금 더 용량이 커지도록,

L3 캐시는 이보다 느리지만 조금 더 용량이 커지도록 설계한다.

 

그리고 이 그림에서는 (꼭 그래야 하는 것은 아니지만) L2 캐시부터 unified cache 로 디자인되어있다.

L1 캐시가 분리되어 있는 이유는 strucutural hazard 에 대응 하기 위함이었다.

하지만 그 밑에서부터는 명령어와 데이터의 비중이 얼마나 다른지를 알기 힘들기 때문에 하나로 합쳐서 unified cache 구조로 디자인한다.

 

 

만약 코어가 여러개 들어있는 경우에는 위와 같이 디자인할 수도 있다.

L2는 instruction cache와 data cache를 하나로 합친다는 의미로 unified cache 이고, 동시에 코어 내에서만 사용되기 때문에 private cache 이다. (L1 캐시도 private cache)

L3는 여러 코어가 공유하는 캐시라는 의미에서 shared cache라고 부른다.

 

성능 계산 예시

기본적인 CPI 가 1이고 (명령어가 매우 많을 때)

clock 주파수가 4GHz, main memory access time 이 100ns 인 CPU가 있다고 해보자.

주파수로부터 클락의 주기를 구하면 2^-2 x 10^-9 = 0.25ns 가 1사이클 주기임을 알 수 있다.

따라서 메모리에 접근하는 시간이 100ns 라는 뜻은 사이클 수로 환산하면 400 cycle이 필요하다는 것을 알 수 있다.

(그리고 이게 곧 miss penalty가 된다.)

 

이때 Miss Rate 가 2% 로 주어진다면, CPI를 다시 계산할 수 있다.

일단 명령어를 가져와서 실행하는데 1cycle이 필요하고, 2% 확률로 400 cycle의 추가 페널티가 들어가므로

명령어 하나를 실행하는데 1 + 0.02 x 400 = 9 cycle 이 평균적으로 필요하다.

(또는 0.98 x 1 + 0.02 x 401 사이클이 소모된다고 봐도 된다. cache hit time 은 hit, miss 공통으로 사용된다.)

 

이때 만약 L2 캐시가 추가되었다고 해보자.

L2 캐시는 접근하는데 5ns 의 시간이 소모되고, 전체적으로 main memory에 대한 miss rate가 0.5% 라고 해보자.

이 말은 L1 캐시에서도 실패하고, L2 캐시에서도 miss가 발생하는 확률이 0.5% 라는 뜻이다.

2% x ? = 0.5% 가 되므로, L2 캐시에서는 25% 확률로 miss가 발생한다는 것을 알 수 있다.

 

이제 L1 캐시에 대한 miss penalty를 다시 계산할 수 있다.

만약 L1 에서 miss가 발생했는데, L2에서 hit가 발생한다면, 이때 캐시에서 데이터를 가져오기까지 필요한 사이클 수는 5ns 를 주기인 0.25 ns 로 나누면 20cycle이 필요하다는 것을 알 수 있다.

 

만약 L1에서 miss가 발생하고, L2에서도 miss가 발생한다면, L2에 접근하는 5ns가 추가적으로 소모되므로 페널티가 증가한다.

20cycle + 400cycle = 420 cycle이 페널티로 들어간다.

 

이때의 CPI를 구하면

0.98 x 1 + 0.02 x 0.25 x 420 + 0.02 x 0.75 x 20 

= 1 + 0.02 x 20 + 0.005 x 400

= 3.4

 

가 된다. L2에 접근하는 20cycle의 '추가' 패널티, 여기에서도 실패하면 메인 메모리에 접근하는 400 cycle의 '추가' 패널티가 들어가기 때문에 두번째 등식과 같이 계산할 수도 있다.

 

기존에 L2 캐시가 없었던 CPI 인 9에 비해 3.4는 대략 2.6배의 성능이 향상된 CPI 이다.

 

L1, L2 캐시의 설계시 고려사항

L1 캐시와 L2 캐시를 모두 넣는다면, 디자인할 때 고려 사항이 조금 다르다.

L1 캐시의 경우, hit time을 줄이는 것이 최우선 목표이다.

왜냐하면 항상 100% 확률로 접근되기 때문에 hit가 발생할 확률도 꽤 높기 때문이다.

 

반면 L2 캐시의 경우, 자기보다 아랫 단계의 메모리 계층으로 넘어가는 상황을 막아주는 것이 매우 중요하다.

따라서 Miss Rate를 줄여서 메인 메모리로 가는 걸 막고, L1 캐시의 miss penalty를 줄여주는 것이 최우선 목표이다.

 

그래서 L2, L3 캐시는 보통 direct mapped cache로 디자인하지 않는다.

set associative cache 형태로 디자인한다.

그리고 용량도 최대한 키워서 miss rate를 감소시키려고 한다.

 

 

이 이미지는 인텔과 AMD의 CPU 스펙을 간단하게 나타낸 것이다.

이 그림에서 ~LRU 는 슈도 LRU 라는 의미이다.

LRU를 완벽하게 구현하지는 않았다는 뜻이다.

AMD는 2-way 로 설계해서 완벽한 LRU를 구현한 경우도 있지만, 그 밑에서 way가 늘어나는 경우 ~LRU로 구현하였다.

 

---

Software 테크닉

지금까지는 하드웨어를 개선해서 캐시의 성능을 끌어올리고자 하였다.

이번에는 하드웨어를 그대로 두고, 소프트웨어의 코드를 수정해서 캐시의 성능을 (캐시의 사용을) 극대화하는 방법을 살펴보자.

 

이때 사용할 수 있는 대표적인 방법이 2가지가 있다.

Loop Interchange 와 Loop Blocking 이다.

 

Loop Interchange 는 중첩 반복문에서 내부 반복문과 바깥 반복문을 서로 바꿔서 반복문을 도는 것을 말한다.

Loop Blocking 은 루프를 구성하는 블록 크기를 줄여서 캐시 사이즈에 맞추는 것을 말한다.

(캐시 크기를 감안해서 배열의 크기를 조정하는 것)

 

예시 - Loop Interchange

C언어에서는 2차원 배열 데이터를 저장할 때 row-major 순서로 저장한다.

row를 고정해두고, column이 변화하는 순서대로 메모리에 차곡차곡 저장하는 것이다.

 

이 그림이 row major 방식으로 저장한 모습이다.

반대로 column을 고정해두고, row가 변화하는 순서대로 저장하는 것을 column major order 라고 한다.

 

이 ordering 방식은 언어에 따라 다르다. (하드웨어 x, 코드 스타일 x)

C언어, 파이썬과 같은 언어는 보통 row major ordering을 사용한다.

따라서 메모리에는 이렇게 row가 같은 데이터들이 연속해서 저장될 것이다.

 

 

그러면 캐시에도 데이터가 block 단위로 저장될 때 위와 같이 같은 row를 갖는 데이터들이 같은 block에 속할 확률이 높을 것이다.

 

따라서 위와 같은 방식으로 코드를 작성하면, cache friendly 하게 작성한 코드라고 볼 수 있다.

row-major ording에 따라서 배열에 접근하고 있어서 cache의 블록 내에 있는 데이터를 하나씩 순회하고, 한 블록의 데이터 순회가 끝나면 그 다음 블록에 있는 데이터를 읽기 때문이다.

 

 

하지만 이런 코드는 row-major-ordering 언어에서는 cache friendly 하지 않다.

 

이렇게 캐시 블록을 가로질러서 접근하기 때문에, 매 반복마다 캐시 블록을 메모리에서 불러오고 교체하는 작업을 반복해야 한다. (특히 direct mapped cache 라면 제일 심할 것이다. spatial locality를 활용하지 못한다.)

이렇게 되는 이유는 현재 언어가 row major ordering을 따르기 때문이다.

이런 경우는 conflict miss가 발생할 확률이 매우 높다.

 

 

이 코드를 아까 본 것처럼 row major ordering에 맞게 바꿔주면 cache friendly하게 작성되었다고 볼 수 있다.

 

이렇게 그림과 같이 spatial locality를 활용할 수 있기 때문이다.