[컴퓨터 구조] 5-2. Associative Caches

 

 

 

 

Direct mapped caches : 메모리 블록을 캐시에 넣을 때 각 블록이 캐시의 딱 한 곳에만 들어갈 수 있는 배치 방법

direct mapped방식은 빠르다는 장점이 있지만miss를 발생시키고 성능을 저하시킨다.

 

 

 

 

Associateve cashes

• n-way set associative

- 각 메모리블록이 들어갈 수 있는 장소의 개수가 적어도 n곳 정해져 있는 캐시구조이다.

- 전체 캐시 칸 중 n칸을 하나의 묶음단위로 함

- 특정 index의 set 안에 있는 n개의 엔트리를 한번에 검색한다.

- direct mapped caches보다 miss율 낮고 태그 비교 횟수는 증가

 

 

 

 

• Fully associative

- 각 메모리 블록이 캐시의 어느 곳에나 자유롭게 들어갈 수 있는 캐시구조이다.

- 전체 캐시 칸들을 하나의 묶음단위로 함

- 모든 엔트리들이 한번에 검색될 수 있어야 하므로 찾는 데 오래 걸린다.

- 캐시가 꽉차면 내보내야 할 것 찾는 데도 오래걸림

- n-way set associative보다 miss율 낮고 태그는 비교횟수는 증가.

위의 그림은 전부 용량이 동일한 캐시들이다. tag-data set이 모두 8개로 동일하다.

set개수가 증가하면서 index는 달라지고, way수가 증가할수록 인덱스 비트는 1개씩 감소한다.

ex) 1024 line → 10비트

       2 way → 9비트

       4 way → 8비트

 

 

 

 

 

 

Associativity Example

 

Block access sequence : 0,8,0,6,8

• Direct mapped : miss 5번

0 : 00 00

8 : 10 00

6 : 01 10

Block address	Cache Index	Hit/Miss	Cache content after access
			0	1	2	3
0	0	miss	mem[0]
8	0	miss	mem[8]
0	0	miss	mem[0]
6	2	miss	mem[0]		mem[6]
8	0	miss	mem[8]		mem[6]

 

• 2-way set associative

0 : 000 0

8 : 100 0

6 : 011 0

Block address	Cache index	Hit/Miss	Cache content after access
			Set0		Set1
0	0	miss	mem[0]
8	0	miss	mem[0]	mem[8]
0	0	hit	mem[0]	mem[8]
6	0	miss	mem[0]	mem[6]
8	0	miss	mem[8]	mem[6]

 

• Fully associative

Block address	Hit/Miss	Cache content after access
0	miss	mem[0]
8	miss	mem[0]	mem[8]
0	hit	mem[0]	mem[8]
6	miss	mem[0]	mem[8]	mem[6]
8	hit	mem[0]	mem[8]	mem[6]

 

associativity ↑ , Miss rate↓

 

 

 

 

 

Set associative cache organization

비교기로 선택된 집합을 어느 원소가 태그와 같은지를 비교한다.

valid date값이 1인지 0인지에 따라 and 게이트의 출력을 결정한다.

or게이트를 통해 and게이트의 출력값 중 하나라도 1이라면 hit로 판단.

4 to 1 mux에서 4개의 and게이트의 출력값 중 1인 것들 중 하나를 결과값으로 출력

 

 

 

 

 

 

Replacement Policy

 

direct mapping 방식에서는 miss가 발생하면 블록은 캐시의 한 칸으로만 갈 수 있으므로 그 자리를 먼저 차지하고 있던 블록을 교체해주기만 하면 된다.

하지만 set associative block에서는 요구된 블록을 어디에 넣을 지 선택해야 하며, replace할 블록을 선택해주어야 한다.

locality의 temporal locality 특성은 지금 사용한 건 나중에 또 사용할 것이라는 특성이었다. 이 특성을 이용한 것이 LRU이다. 

• set associative → LRU(Least-recently used)

LRU : 가장 오랫동안 사용되지 않은 블록을 교체. 가장 최근에 액세스 된 것은 남기고, 사용한 지 오래된 것은 내보냄

• Fully associative → Random

무작위로 액세스 된 것을 내보냄. 의외로 성능이 좋다.

• FIFO(First in First out)

가장 오래된 것은 내보냄

 

 

 

 

 

 

Multilevel Caches

 

메모리는 빠르면 빠를수록 용량이 작고 비싸진다. 옛날에 비해 프로그램의 크기는 점점 커지고 있고 그에 따른 부하도 많이 걸리게 된다. cpu는 계속해서 속도가 빨라지고 있기 때문에 dram과의 속도차가 생기고 있다.

sram은 0.5ns dram은 50ns이므로 100배정도의 속도차가 있는데 이런 속도차를 완충해 줄 중간영역의 속도를 갖는 장치가 필요하다.

• Primary cache (1차 캐시) 
• Secondary cache (2차 캐시) : 마이크로 프로세서와 같은 칩에 있으며, 1차캐시에서 miss가 발생하면 접근한다. 

1차,2차 캐시를 두어 cpu가 stall하지 않으며 메인메모리로 접근하는 것을 줄여 속도를 빠르게 만들어주는 역할을 한다.

2차캐시에서도 miss가 발생하면 메인메모리로 접근한다. 더 큰 손실이 발생한다.

필요에 따라 3차 캐시를 두기도 한다.

상위레벨로 갈수록 용량은 작아지고 속도는 빨리진다. 하위 레벨로 갈수록 용량은 커지고 속도는 느려진다.

 

 

 

 

 

 

 

 

 

출처

chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/https://www.cs.princeton.edu/courses/archive/fall15/cos375/lectures/16-Cache-2x2.pdf

https://www.researchgate.net/figure/Example-multi-level-cache-organisation_fig4_228638286