컴퓨터구조-캐시 기억장치

개념

주기억장치에 저장되어 있는 명령어와 데이터 중의 일부를 임시적으로 복사해서 저 장하는 장치

 

특징

-명령어와 데이터를 저장하고 인출하는 속도가 주기억장치보다 빠름

-자주사용되는명령들을저장하고있다가중앙처리장치에빠른속도로 제공

-느리게 동작하는 주기억장치와 빠르게 동작하는 중앙처리장치(CPU) 사이에서 속도 차이를 줄여주는 고속완충기억장치 -캐시기억장치의 용량에 의해 CPU의 가격이 결정됨

 

 

 

캐시 기억장치가 없는 시스템

1단계: CPU가 명령어와 데이터를 인출하기 위해서 주기억장치에 접근

2단계: 주기억장치에서 명령어나 필요한 정보를 획득하여 CPU내의 명령어 레지스터 등에 저장

 

주기억장치는 보조기억장치보단 빠르지만 중앙처리장치에 비해 매우 느리기 때문에, 둘 사이의 속도 차이를 맞추기 위해서 캐시기억장치를 사용하게 되었다

 

 

캐시 기억장치가 있는 시스템

1단계: CPU가 명령어나 데이터를 인출하기 위해 주기억장치에 가기 전에 캐시기억장치를 먼저 조사한다

2단계: 캐시기억장치에서 찾고자 하는 명령어나 데이터를 찾았으면(적중=hit) 주기억장치로 가지 않고 바로 값을 반환한다. 찾지 못했으면(실패=miss) 주기억장치에 접근하여 값을 찾아 반환한다

 

-CPU입장에서는 힛이 많을 수록 좋다

 

-주기억장치에서 가져온 데이터는 캐시기억장치에 저장된 후 중앙처리장치에 반환된다. 왜냐하면 지금 가져온 데이터는 나중에도 쓸 가능성이 있기 때문이다

 

-캐시기억장치에서 데이터를 못찾아서 miss인 경우 캐시기억장치는 주기억장치로부터 블록 단위로 데이터를 가져온다

그리고 캐시기억장치는 중앙처리장치에 워드 단위로 데이터를 전송한다

(CPU가 한 번에 처리할 수 있는 크기의 단위가 워드, 워드가 2개 이상 모이면 블록)

 

 

miss인 경우 자세한 동작 과정

CPU가 1000번지 워드가 필요하다고 가정한다

1. 먼저 캐시기억장치에서 1000번지 워드가 있는지 찾고 없으면 miss가 된다

2. 캐시기억장치는 주기억장치에서 필요한 정보를 획득하여 캐시기억장치에 저장한다. 이 때 CPU가 필요할 것이라고 생각하는 워드들도 함께 가져온다

(이렇게 더 사용할 것 같은 워드들도 예상해서 가져와야 하니까 데이터 뭉텅이=블록단위로 가져오는 것)

3. 캐시기억장치는 필요한 정보를 중앙처리장치CPU에게 반환한다

 

 

캐시 기억장치의 동작 원리

 

 

 

캐시 기억장치에서 적중률

적중률: 캐시 기억장치의 성능을 나타낸다. 적중률이 높을수록 데이터 액세스 속도가 빠르다

 

Taverage: 주기억장치와 캐시기억장치에서 데이터를 인출하는데 소용되는 평균 기억장치 접근 시간

Tcache: 평균 캐시기억장치 접근 시간

Tmain: 평균 주기억장치 접근 시간

Hhit_ratio: 적중률 (1이 가장 높다)

1-Hhit_ratio: 실패율 (0이 가장 낮다. 전체퍼센트1에서 hit적중률 빼면 miss확률)

 

평균 기억장치 접근 시간(Taverage) = 평균 캐시기억장치 접근 시간(Tcache) + 평균 주기억장치 접근 시간(Tmain)

 

평균 캐시기억장치 접근시간(Tcache) = Tcache * Hhit_ratio

->캐시기억장치 접근하는 시간*몇 번 접근

 

평균 주기억장치 접근 시간(Tmain) = Tmain * 1-Hhit_ratio

->주기억장치 접근하는 시간*몇 번 접근

 

정리하면,

평균 기억장치 접근시간 = 캐시 접근시간*적중률+주기억 접근시간*실패율

 

예시)

Tcache = 50ns, Tmain = 400ns일 때 정중률을 증가시키면서 기억 장치 접근시간을 계산하면

적중률 70%: Taverage = 0.7 x 50ns + 0.3 x 400ns = 155ns

적중률 80%: Taverage = 0.8 x 50ns + 0.2 x 400ns = 120ns

적중률 90%: Taverage = 0.9 x 50ns + 0.1 x 400ns = 85ns

적중률 95%: Taverage = 0.95 x 50ns + 0.05 x 400ns = 67.5ns

적중률 99%: Taverage = 0.99 x 50ns + 0.01 x 400ns = 53.5ns

 

 

캐시 기억장치의 설계

 

캐시 기억장치를 설계할 때 고려할 요소

크기, 인출방식, 사상함수 , 교체 알고리즘, 쓰기 정책, 블록 크기, 캐시기억장치의 수 등이 있다

 

 

1) 캐시기억장치의 크기(Size)

캐시를 검색하는 시간이 캐시 크기가 커질 수록 길어지니까 너무 많아도 비효율적이다

반대로 너무 적어도 주기억장치에 많이 접근해야 되니까 비효율적이다

캐시기억장치의 크기는 1k~128k 워드가 가장 효율적이라고 알려져있다

 

2) 인출방식(fetch algorithm)

주기억장치에서 캐시기억장치로 명령어나 데이터 블록을 인출해 오는 방식

 

요구인출 방식

cpu가 현재 필요한 정보만을 주기억장치에서 블록 단위로 인출해 온다

 

선인출 방식

cpu가 현재 필요한 정보 외에도 앞으로 필요할 거라 생각되는 요소까지 예측해서 가져와서 캐시 기억장치에 저장한다(주로 이웃한 위치에 있는 정보들)

알고리즘이 어렵고 복잡해서 여러 가지가 있다

 

3) 사상함수(Mapping function)

 

주기억장치의 구조

단어 : 하나의 주소 번지에 저장되는 데이터의 단위

블록 : K개의의 단어로 구성됨

 

캐시 기억장치의 구조

슬롯 : 데이터 블록이 저장되는 장소

태그 : 슬롯에 적재된 데이터 블록을 구분해주는 정보

 

주기억장치가 캐시 기억장치에서 필요한 데이터를 찾을 때 슬롯과 태그를 이용한다

 

사상=맵핑

주기억장치와 캐시기억장치 사이에서 정보를 옮기는 것. 주소를 맵핑한다는 의미로 사상이라고 한다(아래 그림)

 

주기억장치의 1000번지는 캐시의 500번지에 있다 이런 식으로 주소끼리 맵핑하는 걸 사상이라고 한다

주소를 연결시키는 작업에서는 다 쓰임(여기서도 쓰이고 db에서도 쓰이고)

 

사상 방법에는 3가지가 있다

(1) 직접 사상

주소변환을 통해 주기억장치의 데이터 블록을 캐시기억장치에 저장하는 것

캐시 기억장치로부터 데이터 블록 인출을 위해 데이터 블록의 슬롯번호에 해당하는 슬롯만 검색하면 된다

 

주기억장치 데이터 블록 주소 = 캐시기억장치 데이터 블록 슬롯번호(주소) + 데이터 블록 태그

 

전체 캐시 슬롯의 수는 캐시의 크기 32바이트를 캐시 슬롯의 크기 4바이트로 나눠서 8개로 결정함

그리고 블록 내의 단어 수는 1개라서, 단어 필드는 항상 00이 된다

 

장점 : 사상 과정이 간단

단점 : 동일한 슬롯 번호를 갖지만 태그가 다른 데이터 블록들에 대한 반복적인 접근을 적중률을 떨어뜨림(동일 슬롯 번호를 갖지만 태그가 다른 데이터 블록이면 miss가 뜬다)

 

예시)

1. cpu가 00001주소 번지 블록을 필요로 하는 경우

 

1) cpu는 앞의 두 자리 00을 태그로 붙이고, 나머지 숫자 세 자리 001을 슬롯 번호로한 00001을 캐시 기억장치로 보낸다. a가 실행 전이라 캐시에 001번지 주소가 없어서 miss가 뜬다 (캐시에서 태그는 보지 않는다)

2) 주기억장치에서 00001데이터를 가져와서 데이터 1234와 태그 00을 저장한다 (캐시와 00001을 맵핑)

3) cpu에 데이터 1234를 반환한다

 

 

2 cpu가 00010주소 번지 블록을 필요로 하는 경우

1) cpu는 캐시 기억장치에서 슬롯 번호가 010이고 태그가 00인 데이터를 찾는다. 010번지가 없으므로 miss가 된다

2) 주기억장치에서 00010번지를 가져와서 주소 앞의 두 자리 00을 태그로 붙이고 데이터 5678을 저장한다 (캐시와 00010을 맵핑)

3) cpu에 데이터 5678을 반환한다

 

 

3. cpu가 10001주소 번지 블록을 필요로 하는 경우

1) cpu가 주소 앞의 두 자리 10을 태그로 붙이고, 나머지 숫자 세 자리 001을 슬롯 번호로 캐시 기억장치 001에 접근. 슬롯 번호가 001으로 같은데 태그는 다르므로 miss가 된다

2) 주기억장치에서 10001번지를 가져와서 태그 10과 데이터 7890을 저장하는데, 이처럼 슬롯 번호가 같은 경우에는 데이터를 덮어씌운다. 데이터 1234가 없어지고 7890이 되었고, 태그도 10이 되었다

3) cpu에 데이터 7890을 반환한다

 

 

4. CPU가 00010주소 번지 블록을 필요로 하는 경우

1) cpu는 슬롯 번호가 010이고 태그가 00로 표시함. 캐시 기억장치에서 010번지를 찾는다. 슬롯 번호도 같고 태그도 같으므로 hit으로 판단한다

2) cpu에 데이터 5678을 반환한다

 

 

(2) 연관 사상

주소변환 식을 통해 주기억장치의 데이터 블록을 캐시기억장치에 저장함

캐시기억장치로부터 데이터 블록 인출을 위해서 모든 슬롯에 대한 검색이 필요함

 

주기억장치 데이터 블록 주소 = 캐시기억장치 데이터 블록 슬롯번호(주소) + 데이터 블록 태그

 

한 마디로 연관 사상은 주소 무작위로 그냥 저장함

램(주기억)에 있는 주소를 그냥 캐시에 저장하는데 매번 찾아야 하니까 좀 비효율적이다

 

그래서 나온 게 집합 연관 사상

 

 

(3) 집합 연관 사상

직접 사상과 연관 사상 방식을 조합한 방식

캐시는 v개의 집합들로 나뉘며, 각 집합들은 k개의 슬롯들로 구성된다

직접 사상 방식에 의해, v개의 집합들 중 하나의 집합을 선택한다

연관 사상 방식에 의해, 선택한 집합내에 있는 k개의 슬롯 중 하나의 슬롯을 선택한다

 

태그 000과 데이터 abcd와 태그 010 fell이 한 집합

 

 

4) 교체 알고리즘(Replacement algorithm)

캐시 기억장치의 모든 슬롯이 채워져 있는 상태에서 miss가 뜨면 주기억장치로부터 새로운 데이터 블록을 캐시기억장치로 옮기기 위해 캐시 기억장치를 비워야 되는데, 이 때 어느 슬롯 데이터를 제거할지 결정하는 방식

 

캐시에서 가장 쓸모없을 것 같은 데이터를 판단해서 그걸 삭제한다

그걸 판단하는 게 교체 알고리즘

 

직접 사상: 교체 알고리즘이 필요 없다

연관 & 집합 연관 사상: 교체 알고리즘이 필요하다

 

교체 알고리즘 종류

LRU (Least Recently Used): 최소 최근 사용 알고리즘

LFU (Least Frequently Used): 최소 사용 빈도 알고리즘

FIFO (First In First Out): 선입력 선출력 알고리즘

RANDOM: 랜덤

 

 

5) 쓰기 정책(Write policy)

즉시 쓰기

cpu에서 생성되는 데이터 블록을 캐시 기억장치와 주기억장치에 동시에 기록한다

 

장점: 데이터의 일관성을 쉽게 보장할 수 있다

단점: 매번 쓰기 동작이 발생할 때마다 캐시 기억장치와 주기억장치 간의 접근이 빈번하게 일어나 쓰기 시간이 길어진다

 

나중 쓰기

캐시 기억장치에 기록한 후, 기록된 블록에 대한 교체가 일어날 때 주기억장치에 기록함

명령어를 모아 한번에 기록한다

 

장점: 즉시 쓰기 방식과는 달리 주기억장치에 기록하는 동작을 최소화할 수 있다

단점: 캐시 기억장치와 주기억장치의 데이터가 서로 일치하지 않을 수 있다(변조가 생길 수 있음)

 

 

6) 블록 크기(Block size)

블록의 크기가 클수록 한번에 많은 정보를 읽어올 수 있지만 인출 시간이 길어짐

블록이 커질수록 캐시기억장치에 적재할 수 있는 블록의 수가 감소해 블록들이 더 빈번하게 교체됨

일반적인 적당한 블록의 크기는 4~8 워드

 

 

7) 캐시기억장치의 수(Number of caches)

시스템 성능 향상을 위해 다수의 캐시가 기억장치들을 사용하는 것이 보편화 되었다

캐시 기억장치들을 계층적 구조나 기능적 구조로 설치한다

 

 

 

 

[연습 문제]-캐시 기억장치

1. 캐시 기억장치 설계 시 고려할 요소가 아닌 것은?

1) 주기억장치의 크기

2) 사상함수

3) 교체 알고리즘

4) 쓰기 정책

5) 캐시기억장치의 수

답: 1

캐시기억장치를 설계할 때 주기억장치의 크기가 아닌 캐시기억장치의 크기를 고려

 

2. 캐시기억장치 접근시간이 50ns이고 주기억장치 접근시간이 400ns일 때, 캐시 기억장치의 적중률이 80%인 경우 기억장치 접근 시간은?

답: 120ns

평균 기억장치 접근시간 = 캐시 접근시간*적중률+주기억 접근시간*실패율

Taverage = 0.8 x 50ns + 0.2 x 400ns = 120ns

 

3. 다음 중 설명에 해당되는 사상 방법은?

주소변환 식을 통해 주기억장치의 데이터 블록을 캐시기억장치에 저장함

캐시기억장치로부터 데이터 블록 인출을 위해서 모든 슬롯에 대한 검색이 필요함

 

1) 직접 사상

2) 연관 사상

3) 집합 연관 사상

답: 2

모든 슬롯을 검색하는 연관 사상에 대한 설명이다

 

4. 쓰기 정책 중 나중 쓰기 방식에서는 캐시 기억장치와 주기억장치에 데이터가 서로 일치하지 않게 변조가 생길 수도 있다(O,X)

답: O

명령어를 모아 한 번에 기록하는 만큼 변조 가능성 있음

 

5. 교체 알고리즘이 필요 없는 것은?

1) 직접 사상

2) 연관 사상

3) 집합 연관 사상

답: 1

직접 사상은 교체 알고리즘이 필요 없다

 

6. 다음에 들어갈 단어는?

캐시기억장치에서 데이터를 못찾아서 miss인 경우 캐시기억장치는 주기억장치로부터 ____단위로 데이터를 가져온다

그리고 캐시기억장치는 중앙처리장치에 ____단위로 데이터를 전송한다

답: 블록, 워드

 

7. 인출 방식 중 선인출방식은 cpu가 현재 필요한 정보만을 주기억장치에서 블록 단위로 인출해 온다(O,X)

답: X

요구인출방식이 그렇다

선인출방식은 cpu가 현재 필요한 정보 외에도 앞으로 필요할 거라 생각되는 요소까지 예측해서 가져와서 캐시 기억장치에 저장한다

 

 

 

[연습 문제]-보조 기억장치, 입력과 출력, 시스템 버스

1. 보조 기억장치의 종류로 옳지 않은 것은?

1) RAM

2) 하드 디스크

3) flash

4) CD

답: 1

ROM과 RAM은 주기억장치다

 

2. 자기 디스크의 고정 헤드는 헤드를 이동시키는 장치이다(O,X)

답: X

자기 디스크의 고정 헤드는 하나의 헤드가 원형평판위를 이동하며 여러 트랙에 읽기와 쓰기를 수행한다

 

3. 보조기억장치에 접근 할 때 데이터가 저장되는 순서에 따라 접근 순서가 결정되며, 접근 시간은 데이터의 저장 위치에 따라 다른 접근 방법으로, 자기 테이프와 케시트 테이프가 대표적으로 쓰고 있는 방법은?

답: 순차적 접근 방법

 

4. 중앙처리장치, 입출력장치과 관련된 제어 신호 중, 버스에 적재된 데이터를 지정된 입출력장치로 출력시키는 제어 신호는?

1) 입출력 읽기 신호

2) 입출력 쓰기 신호

3) 전송 확인 신호

답: 2

 

5. 시스템 버스 중 양방향 전송이 가능한 버스는?

답: 데이터 버스, 제어버스

데이터 버스는 컴퓨터 시스템을 구성하는 장치들 사이에서 데이터를 전송하는 용도로 사용되는 선들의 집합으로,

연결된 장치들간에 양방향 전송이 가능하다

 

제어 버스는 중앙처리장치가 메모리가 I/O장치에게 제어 신호를 전송하거나, 혹은 반대로 중앙처리장치에게 어떤 동작을 지시하는 단방향일 수도 있고 양방향 일 수도 있다