[컴퓨터 구조] 5-1. Direct mapped Cache

 

 

 

내장형 프로그램 방식인 폰노이만 방식의 컴퓨터를 사용하고 난 이후로 메모리에 저장된 명령어를 가져오고 변수에 할당된 값 메모리로부터 읽어온다. 이 때 메모리는 excess time이 존재해 프로세서에 비해 메모리 동작이 상대적으로 느리다.

 

 

Memory technology

       1ns = 1GHZ, 20ns = 50MHZ

• Static RAM(SRAM) : 0.5ns - 2.5ns, $2000 - $5000 per GB
• Dynamic RAM(DRAM) : 50ns - 70ns, $20 - $75 per GB
• Mgnetic disk(HDD) : 5ms - 20ms, $0.20 - $2 per GB
• Ideal Memory : SRAM의 access time을 가지고 disk의 용량과 가격을 가지는 메모리

 

 

Principle of Locality

프로그램은 어떤 특정 시간에 주소 공간 내의 비교적 작은 부분만을 접근한다는 원칙이다.

• Temporal locality (시간적 지역성) : 한 번 참조된 데이터는 곧바로
• 다시 참조될 가능성이 높다는 원칙.
• Spatial locality (공간적 지역성) : 하나의 데이터가 참조되면 곧바로 그 주위의 데이터가 참조될 가능성이 높다는 원칙. 

 

 

 

 

 

memory hierarchy 

여러 계층의 메모리를 사용하는 구조. 프로세서로부터 거리가 멀어질수록 메모리의 크기와 접근시간은 증가하고 비트 당 가격은 내려간다.

프로세서와 상위레벨 메모리(캐시) 하위레벨 메모리(메인메모리)가 순서대로 계층을 구성하고 있는 모습이다.

메인메모리는 메모리 전체의 고유한 주소를 가지고 있고 캐시는 메인 메모리의 주소와 내용을 저장해야 한다.

메모리 전체 영역 중 자주 액세스 하는 일부분을 작고 빠른 메모리 안에 넣어둠으로써 프로그램을 수행하는 동안 대부분은 위에 작고 빠른 메모리를 위주로 사용한다. → 최근에 접근했던 데이터들을 프로세서 가까이 적재함으로써 시간적 지역성을 이용한다.

 

 

 

 

 

 

 

Direct Mapped Cache

각 메모리 워드에 캐시 내의 위치를 할당하는 가장 간단한 방법은 그 워드의 메모리 주소를 이용하는 것이다.

각 메모리 위치가 캐시 내의 정확히 한 곳에만 사상되는 캐시구조를 direct mapped라 한다.

메모리주소 인덱스별로 다이렉트 매핑된 캐시의 모습

캐시 안에 있는 블럭의 갯수는 2의 거듭제곱 꼴이다. 각 캐시 엔트리는 여러 주소의 메모리 내용을 갖고 있을 수 있다.

MIPS 또는 ARM의 instruction은 1개로 32비트, 즉 4바이트이기 때문에 메모리 4칸에 대응된다.

따라서 캐시 한 칸은 4바이트에 대응된다.

 

예를 들어 2장에서 beq명령을 실행할 때, PC값은 바이트단위의 주소에 해당하며 뛰어넘어야 할 instruction 갯수는 워드단위였었다. 따라서 워드 단위를 바이트단위로 맞춰주기 위해 shift left2해준 뒤 PC값에 더해 바이트단위로 맞춰주어야 한다.

메모리 주소는 바이트단위이다.

 

메모리 주소 중 하위에 있는 log2(캐시 전체 블록 수) 비트수 만큼을 캐시 엔트리의 인덱스로 사용한다.

 

캐시주소는 바이트 단위의 주소를 워드단위로 만들어야 하기 때문에 워드만큼 해당되는 비트를 잘라내고 나머지를 이용해 캐시 인덱스를 생성한다.

 

 

 

 

 

 

Tag and Valid bits

메모리 1칸이 캐시 1칸에 direct mapped될 때, 캐시 1칸에 들어가는 메모리 4칸이 중복되므로 메모리 주소도 함께 저장해주어야 한다.

따라서 메모리주소 오른쪽 끝에서 캐시 인덱스만큼을 잘라낸 나머지를 Tag로 저장한다.

(메모리 주소 중 캐시 인덱스로 사용되지 않은 주소의 상위 부분 비트들로 이루어짐)

 

Tag : 찾은 블록이 요청한 워드에 해당하는 지 아닌지를 식별하는 데 필요한 주소정보를 담고 있는 필드

 

컴퓨터 전원을 켜면 하드디스크에는 grabage값 이 저장되어있고 캐시는 비어있다. 많은 명령어를 수행한 이후에도 일부 캐시 엔트리는 비어있을 수 있다. 따라서 비어있는 엔트리의 태그들을 무시하기 위해 각 캐시 엔트리에 valid bit을 1비트씩 추가해서 엔트리에 유효한 주소가 있는지를 표시한다.

 

컴퓨터 전원이 켜지면 모든 valid bit을 0으로 표시.

→ CPU가 메모리를 액세스 하려할 때 valid bit 비트값이 0이면 그 캐시 메모리에 garbage값이 있다 생각

→ 해당 메인메모리로 가서 값을 읽어와 캐시 엔트리를 채움

→ valid bit값 1로 변경

→ 그다음에 CPU가 메모리를 액세스 하려할 때 valid bit 비트값이 1이면 액세스 하려는 메인메모리 주소의 Tag값이 캐시에 저장되어있는 메모리 주소의 Tag값과 같은지 다른지 비교(같으면 HIt, 다르면 Miss)

 

 

valid bit : 해당 블록이 유효한 데이터를 가지고있는지 아닌지를 표시하는 필드

 

캐시는 예측기법을 사용하는 중요한 예시이다. Locality를 이용해 메모리 상위계층에서 필요한 데이터를 찾는다. 상위계층에서 예측이 틀린다면 하위계층에서 적합한 데이터를 찾도록 한다.

 

 

 

 

Cache example

1. word address 22번지로 액세스

Word address	Binaresy address	Hit/Miss	Cache block
22	10 110	Miss	110

Index	V	Tag	Data
000	N
001	N
010	N
011	N
100	N
101	N
110	Y	10	Mem[10110]
111	N

 

다음과 같이 변환해 준 후 index 110으로 가서 valid bit가 N임을 확인한 후 Y로 변경해주고 Tag칸을 10으로 채우고 Data칸을 mem[10110]으로 채운다.

 

 

2. word address 26번지로 액세스

Word address	Binary address	Hit/Miss	Cache block
26	11 010	Miss	010

Index	V	Tag	Data
000	N
001	N
010	Y	11	mem[11010]
011	N
100	N
101	N
110	Y	10	mem[10110]
111	N

 

다음과 같이 변환해 준 후 index 010으로 가서 valid bit가 N임을 확인한 후 Y로 변경해주고 Tag칸을 11으로 채우고 Data칸을 mem[11010]으로 채운다.

 

 

3. word address 16 → 3 → 16 액세스

Word address	Binary address	Hit/Miss	Cache block
16	10 000	Miss	000
3	00 011	Miss	011
16	10 000	Hit	000

Index	V	Tag	Data
000	Y	10	mem[10000]
001	N
010	Y	11	mem[11010]
011	Y		mem[00011]
100	N
101	N
110	Y	10	mem[10110]
111	N

다음과 같이 변환해 준 후 index 000으로 가서 valid bit가 N임을 확인한 후 Y로 변경해주고 Tag칸을 10으로 채우고 Data칸을 mem[10000]으로 채운다.

다음과 같이 변환해 준 후 index 011으로 가서 valid bit가 N임을 확인한 후 Y로 변경해주고 Tag칸을 00으로 채우고 Data칸을 mem[00011]으로 채운다.

 

word address 16번지를 또 액세스 하는 경우, valid bit가 Y임을 확인하고 Tag가 10으로 같음을 확인한 후 Hit이므로 메인메모리로 가지않는다.

 

 

 

4.word address 18 액세스

16	10 000	Miss	cache block
18	10 010	Miss	010

Index	V	Tag	Data
000	Y	10	mem[10000]
001	N
010	Y	11	mem[11010]
011	Y		mem[00011]
100	N
101	N
110	Y	10	mem[10110]
111	N

다음과 같이 변환해 준 후 index 010으로 가서 valid bit가 Y임을 확인한 후 word address의 Tag와 기존 Tag가 다르기 때문에 Miss이므로 최신의 Tag와 data로 mem[10010]으로 갱신한다. (temporal locality)

 

 

 

 

 

 

 

 

Adress subdivision

메모리주소가 바이트 단위 구조로 있을 때

 

1.프로세서에서 메모리를 액세스 하면 액세스한 메모리의 주소번지가 나온다.

2.byte address형태이므로 byte offset을 해주고 index비트와 일치하는 위치를 찾아간다.

3.valid bit를 확인한다.

4.최신 Tag와 기존Tag끼리 비교 한다.

(XOR)

이 때 같으면 Hit이므로 메인메모리를 거치지 않고 캐시메모리에서 프로세서로 바로 32비트를 전달한다.

같지 않으면 Miss이므로 일단 명령어를 정지한 후 메인메모리로 가서 32비트를 가져와(fetch) 캐시에다 집어넣는다. 이 때 손실이 발생한다.

 

 

 

Write Through

write가 항상 캐시와 다음 하위계층을 동시에 갱신하는 방식. 항상 두 계층의 데이터가 일치함을 보장해준다.

write 명령어가 왔을 경우 메인메모리까지 가서 기록 → write작업이 끝날 때까지 stall시켜야 하므로 메모리속도가 매우 느리다

 

해결 : write buffer를 사용

기록할 내용과 메모리번지를 플립플롭에 저장 → 파이프라인은 계속 진행됨 & stall 할 필요x → 파이프라인 진행되는 동안 write buffer가 천천히 메모리로 가서 write → write buffer내용 지워짐

새로운 문제점 : store 명령어가 반복됨 → write buffer가 꽉차게 되면 빈 공간이 생길 때까지 멈춰 있어야 한다. →  write buffer를 queue형태로 만들어 길이를 늘려야 함.

 

 

 

 

Write Back

write할 때는 캐시블록의 값만을 갱신하고, 나중에 그 블록이 교체될 때 하위계층 메모리에 변경된 블록을 쓰는 방식

Dirty bit : 캐시 한 칸 당 1비트씩 더 추가. 맨 처음엔 전부 0인 상태 → write 명령어가 왔을 경우 메인 메모리까지 가서 write하지 않고 data에 써놓은 뒤 dirty bit를 1로 변경

→  다음번에 같은 인덱스에 write가 왔을 때 dirty bit가 1이면 이전에 data에 써놓은 값 메모리에 write

동일한 인덱스에 해당하는 다른 주소 액세스가 와서 최신의 것으로 덮어쓰려는 순간에만 한번 write해주면 됨

 

 

 

 

 

 

Measuring Cache Performance

캐시에 miss가 발생하면 stall해야 하기 때문에 메모리 stall 사이클은 miss횟수에 영향을 크게 받는다.

DRAM은 50ns로 매우느리기 때문에 MIPS penalty가 매우 중요하다.

또한 CPU가 아무리 고속이여도 메모리는 50ns이므로 CPU가 빨리질수록 암다르 법칙에 의해 stall이 CPI에 의해 미치는 영향이 증가하게 된다. → 캐시의 성능이 시스템 성능의 가장 중요한 요소이므로 cache ratio를 높여야 한다.

 

 

 

 

 

 

Increasing Memory Bandwidth

 

a. 캐시 폭 : 4바이트 & 메인 메모리 폭 : 4바이트 → 한꺼번에 32비트씩 읽어올 수 있음

b. 캐시 폭 : 8바이트 & 메인 메모리 폭 : 8바이트 → 한꺼번에 64비트씩 읽어올 수 있으므로 bandwidth증가하고 miss감소

c. 캐시 폭 : 4바이트 & 메모리는 interleaved해 4덩어리로 만듦 → 0번지 액세스 하여 miss가 발생한다면 그동안 나머지 1,2,3번지 액세스 →  메모리는 느리기 때문에 4개를 갖다놓고 번갈아가며 액세스 → bandwidth증가

 

 

 

 

 

 

 

 

 

출처

http://vlabs.iitkgp.ernet.in/coa/exp11/index.html

https://www.geeksforgeeks.org/cache-memory-in-computer-organization/

https://www.slideserve.com/tyrell/the-memory-hierarchy-cache-main-memory-and-virtual-memory-part-2