[컴퓨터구조]캐시 메모리 성능 향상 (improving cache memory performance) / three placement policy

multiple word direct mapped cache : 일반 direct mapped cache에서 spatial locality를 할 수 있도록 보완한 구조

- 캐시 한 라인의 데이터 block을 한번에 인접한 여러개의 데이터를 가져다 놓음

- 다른 데이터가 miss날 것을 예방

- 4개의 data가 같은 tag와 valid를 공유하고 있다. (절약)

- 추가적으로 block offset이 필요 : 한 block안에서 4개 data중 1개의 data를 구분하여 출력하게함 (mux이용)

-miss가 나면 block 중에 하나의 data만 교체하는 것이 아니라 block단위로 전체를 교체해야한다.

질문) 4개의 word를 한번에 가져오는 것이 과연 이득인가? 

답) 주소를 하나주고 1개의 word를 가져오는 것을 4번 반복하는 것보다, 한번에 4개를 가져오는 것이 완전 이득이다.

메모리에서 데이터를 가져오는데 시간이 많이 소요된다. 그리고 한번에 데이터를 가져오는 경우에는 burst모드가 적용되어 시간이 덜 소요된다.

예시) 1 word가져오는 데 걸리는 시간 100ns 라고 가정

• 4번 반복한 경우: 400ns,
• 한번에 가져온 경우 : 100ns + 30*50ns = 250ns

---

캐시 성능 (performance) : block size 로 성능 향상

실행 시간(execution time) = (계산에 필요한 clock cycle 수(= 계산에 필요한 시간) + stall clock cycles(=miss가 났을 때 새로운 데이터를 가져오는 시간))x cycle time

 

stall clock cycle을 계산하는 방법

• instruction/program (프로그램 당 명령어 수) x miss/instructions (명령어 당 miss의 수) x miss penalty(miss가 났을 때 필요한 clock cycle 수)
• memory access/program (프로그램 당 메모리 접근 횟수) x miss rate (메모리 접근했을 때 miss가 일어날 확률) x miss penalty 

■ miss penalty : 메모리로 부터 block을 가져와서 cache에 다시 넣는 시간 + 다시 넣은 cache를 CPU에 전달하는 시간

■ miss penalty 가 hit time보다 훨씬 많은 시간을 소요한다.

 

성능을 향상시키기 위한 두가지 방법

• miss ratio를 줄인다.
• miss penalty를 줄인다.

block size 크기가 커지면 어떻게 될까? miss가 나는 비율이 감소, 하지만 miss penalty가 커짐

 

block size가 너무 커지면 miss rate는 오히려 증가하게 된다.

왜냐하면, block size의 크기가 cache의 너무 많은 부분을 차지하게 되면 같은 자리를 두고 다투는 주소가 늘게 되고 빈번한 입출력으로 인해 miss가 많이 일어나게 된다.

 

block size가 커지면,

1. cache에 들어가는 block의 개수가 줄어든다.

2. block의 개수가 줄어드니, spatial locality를 지킬정도의 block을 cache에 넣을 수 없다. 공간 지역성이 감소된다.

3.block이 너무 커서 많은 word를 읽어와야하기 때문에, miss penalty가 커진다.

 

block size에 따른 miss rate

1. cache size는 크면 좋다.

2.cache size가 같을 때 , cache block이 커지면 성능이 좋아지다가 나빠진다.

3. cache size가 커질 수록, block size에 따른 향상 속도가 다르다.

---

block을 배열하는 방법 ( Three placement policy) 으로 성능 향상

1. Direct mapped : memory의 주소로 cache의 위치를 정함

• 장점 : cache에 해당 주소를 찾는 것이 간단하다.
• 단점 : 하나의 index에 접근이 몰릴 수 있다.(효율적이지 못함)

Direct mapped

2. Fully Associative : 메모리 주소와 관계없이 cache memory를 이용하는 방법

memory 주소 구조

- tag 가 주소의 모든 부분을 담고있음

- 모든 메모리를 한번에 읽고 비교하는 특수한 메모리가 필요

- 주소를 주면 그 주소랑 cache의 tag값을 비교해서 data가 있는지 확인함

-주소와 tag를 비교하는 것이 동시다발적으로 일어난다.

- hit 여부를 바로 알 수 있음

 

3. Set Associative 

- Direct mapped 방식은 낭비가 심함

- Fully Associative 방식은 너무 극단적이고 비쌈

- 이 둘의 절충안이 Set Associative 임

 

■ 쉽게 말하자면, direct mapped를 여러개 두는 방식임

Direct mapped : 8개 중에 1개만 사용가능

Set associative (2way) : 8개 중에 2개 사용 가능 ( 4개 중 1개)

Fully associative : 다 사용 가능

set associative

- index에 따라 cache 4개에서 해당 index에 접근

- 4개 중에 한 군데만 매칭되어야 한다. (2개 이상 매칭 불가능)

캐시 크기와 way 수에 따른 miss 발생률

- 역시 캐시크기가 크면 캐시에 원하는 데이터가 있을 확률이 크다. (miss rate가 줄어든다.)

- way 수를 늘리면 miss 발생률이 줄어드는 것을 볼 수 있다. (캐시공간이용률이 좋아짐, 성능향상)  ☞캐시가 작을 수록 더욱 성능이 좋아짐

- 하지만, 용량이 큰 캐시일때는 way수를 늘려도 성능 변화가 없다( 캐시가 크면 어차피 데이터 분산률이 좋아서 way를 여러 개 만들어도 큰 변화가 없다.)

 

질문) way수를 최대한 많이 늘려서 쓰면되는데 왜 상용은 2~4 way 만 사용하나요?

답) way 수를 늘리면 캐시 수가 늘어나고 way 수 만큼 mux에 입력된다. mux에 너무 많은 데이터가 한번에 들어오면, 그 데이터를 다 구분하고 출력하는데 너무 시간이 걸리게 되고, 그러면 캐시를 사용하는 의미가 사라진다.

☞hit일 때 시간이 너무 걸려서 way수를 한정적으로 사용한다.

추가적으로, way수를 fully로 사용하면 너무 비쌈

 

 

---

replacement 정책으로 성능 향상

여러개의 cache를 사용하고 이 캐시들이 다 차있을 때, 이 중 어느 캐시에 data를 넣을지 정하는 정책이다.

 

1. random 

- 말 그대로 랜덤하게 cache를 정해서 그 캐시에 원래 있던 데이터를 버리고 새 data 삽입

- 어중간한 알고리즘 보다는 좋은 성능을 낸다.

 

2.FIFO(First In First Out)

- 먼저 데이터를 넣은 캐시를 먼저 뺀다.

- 이를 위해서 언제 각 캐시에 데이터가 삽입되었는지 time stamp를 찍어야 한다.

- 위험성 : 가장 오래된 캐시는 가장 많이 사용하는 데이터일 수 있어서, 가장 먼저(오랜)데이터를 빼는 것은 위험할 수 있다.

 

3.Least Recently Used(LRU)

-제일 오랫동안 안쓰인 데이터를 가장 먼저 뺀다.

- 얼마나 오래 안쓰였는지를 체크하기위해서는 time stamp를 찍어야 한다.

-FIFO와 다르게 access할때마다 time stamp를 찍어야 한다.

- 심지어, access를 하지않아도, 시간 지난 것을 체크하기 위해 time stamp를 찍어야한다.

- cache의 모든 entry에 대하여 다 시간을 세는 것은 만만치 않다.

 

4.Least Frequestly Used(LFU)

-가장 적게 사용된 데이터를 먼저 뺀다.

- 사용 횟수를 기록하는 counter 필요

- 위험성 : 가장 최근에 들어온 데이터가 억울하게 빠져나갈 수 있다.

 

가장 이상적인 replacement algorithm은 무엇인가? 

: 미래에 안쓰일만한 것을 쫒아내는 게 가장 이상적 -> LRU

 

결론 : replacement 정책 중에 가장 이상적인 것은 LRU이다.

 

 

---

multi level cache로 miss penalty 감소시키기

- cache를 하나 더 두는 것 (L1, L2)

- L1에서 miss가 났을 때 바로 main memory에서 데이터를 가지고 오는 것이 아니라 L2를 이용

- L1이 L2보다 block size 작음, L2는 block size 큼(miss ratio를 줄이기 위해)