Chapter5-4. 가상메모리 -2

메모리 계층을 위한 공통 프레임워크 (Chpater5-1 복습)

■ 공통 원칙은 메모리 계층의 모든 수준에 적용됩니다.
- 캐싱 개념 기반
■  계층의 각 수준에서
- Block placement

- Finding a block

- Replacement on a miss

- Write policy

 

① Block placement : 블록을 어디에 넣을 수 있을까?

■ 연관성에 의해 결정됨
- 직접 매핑(1-way 연관성)
  - 배치를 위한 하나의 선택
-  n-way 집합 연관
  - 집합 내에서 n개의 선택
- 완전 연관
  - 임의 위치
■ 연관성이 높을수록 miss rate(실패율)이 감소
- 복잡성, 비용 및 액세스 시간 증가

 

② Finding a Block : 블록을 어떻게 찾을까?

연관정도	블록을 찾는 방법	비교 횟수
직접매핑	index(인덱스)	1
n-way 집합 연관	집합을 인덱스한 후 집합 내에서 모든 원소 비교	n
완전 연관	모든 엔트리 검색	캐시 크기(entries)
	별도의 검색 테이블	0

■ 하드웨어 캐시
- 비교를 줄여 비용 절감
■ 가상 메모리
- 전체 테이블 조회를 통해 완전 연관 실현 가능
- 실패율 감소하는 장점이 있다.

 

③ Replacement on a miss : 캐시 실패가 발생하면 어느 블록을 교체할까?

■ 누락 시 대체할 항목 선택 방법
(1) 가장 최근에 적게 사용한 항목(LRU)
  - 높은 연관성을 위한 복잡하고 비용이 많이 드는 하드웨어
(2) 무작위 교체(랜덤)
  - LRU에 가깝고 구현이 용이함

(3) FIFO(First In First Out)

- 첫번째로 들어온 것부터 순서대로 대체한다.

 

■ 가상 메모리
- 실패 비용이 매우 커서 실패율의 작은 감소 조차도 중요하기 때문에

하드웨어 지원을 통한 LRU 근사 방식을 사용한다.

 

④ Write Policy : 쓰기는 어떻게 하는가?

(1) 직접쓰기(Write-through)
- 상위 및 하위 레벨 모두 업데이트
- 교체를 단순화하지만 쓰기 버퍼가 필요할 수 있음

(2) 나중 쓰기(Write-back)
- 상위 레벨만 업데이트
- 블록 교체 시 하위 레벨 업데이트
- 더 많은 상태를 유지할 필요가 있다.

 

즉시 쓰기	나중 쓰기
- 실패를 해도 하위 계층에 블록을 쓸 필요가 없으므로, 실패 처리가 간단하고 비용이 적게든다. - 나중 쓰기보다 구현이 간단하다. - 실용적을 가지려면 쓰기 버퍼가 필요하다.	- 프로세서는 각 워드를 메인 메모리가 아닌 캐시가 받아들일 수 있는 속도로 쓴다. - 블록에 쓰기가 여러번 발생해도 하위 계층에는 한 번만 쓰면된다. - 블록을 하위 계층에 쓸 때, 전체 블록을 한꺼번에 쓰기 때문에 높은 대역폭 전송을 효과적으로 이용할 수 있다.

 

■ 가상 메모리
- 디스크 쓰기 지연 시간이 주어진 경우에만 쓰기 가능

- 하위 계층을 쓸 때 지연시간이 크기 때문에 나중쓰기 방식이 유일한 실용적 대안이다.

물리적, 논리적으로 폭이 큰 메인 메모리를 사용하고 DRAM의 버스트 모드를 사용하더라도, 프로세서가 쓰기를 발생시키는 속도는 일반적으로 메모리 시스템이 쓰기를 처리하는 속도보다 빠르다. 그러므로 최하위 계층 캐시들은 대게 나중 쓰기 방식을 사용한다.

 

Sources of Misses(3C 모델, 실패의 원인)

① Compulsory misses(필수 실패, 최초 시작 실패)
- 블록에 대한 첫 번째 접근

- 캐시에 한번도 들어온 적 없는 블록을 처음 접근할 때 생기는 캐시 실패

② Capacity misses(용량 실패)

- 캐시가 프로그램 수행 중 필요한 모든 블록을 포함할 수 없을 때 발생한다. 

- 제한된 캐시 크기로 인해 블록이 교체되고 나중에 다시 그 블록을 가져올 때 발생한다.

 

③ Conflict misses(= Collision miss, 충돌 실패)

- 집합 연관이나 직접 사상 캐시에서 여러 블록들이 같은 집합에 대해 경쟁을 벌일 때 발생하는 캐시 실패.

- 같은 크기의 완전 연관 캐시에서는 발생하지 않는다.

 

Cache Design Trade-offs(메모리 계층구조 설계의 어려움)

디자인 변경	실패율의 영향	부정적인 성능 효과
캐시 크기 증가	용량 실패 감소	접근 시간 증가
연관성 증가	충돌 실패 감소	접근 시간 증가
블록 크기 증가	필수 실패 감소	실패 손실 증가 블록 크기가 매우 커짐에 따라 오염으로 인한 실패율이 증가

 

Cache Coherence Protocols(캐시 일관성 프로토콜)

■ 일관성을 보장하기 위해 멀티프로세서의 캐시에 의해 수행되는 작업
- 로컬 캐시로 데이터 이동
  → 공유 메모리의 대역폭 감소

  → 데이터는 지역 캐시로 이동하여 그곳에서 투명하게 사용될 수 있다. 이동은 먼 곳에서 위치한 공유 데이터를 접근할 때 발생하는 지연과 공유 메모리에 대한 대역폭 요구를 줄여준다.
- 읽기 공유 데이터 복제
  → 액세스 경합 감소

  → 공유데이터가 동시에 읽힐 때, 캐시는 지역 캐시 안에 복사본을 만들어 공유 데이터 읽기에 대한 접근 지연과 경쟁을 감소시킨다.

 

■ 스누핑 프로토콜
- 각 캐시는 버스 읽기/쓰기를 모니터링합니다.

- 프로토콜 쓰기 작업 시에 다른 캐시에 있는 복사본들을 무효화하기 때문에 쓰기 무효화 프로토콜이라고도 한다.

■ 디렉토리 기반 프로토콜
- 디렉터리에 있는 블록의 캐시 및 메모리 레코드 공유 상태

- 디렉터리에 실제 메모리 블록의 공유 상태를 저장하고 스누핑 구현 오버헤드가 약간 더 크다.

- 캐시들 간의 트래픽을 줄여서 프로세서 수가 많을 때 적합하다.

 

Invalidating Snooping Protocols : 스누핑 프로토콜 무효화

■ 캐시는 블록을 작성할 때 블록에 대한 독점적인 액세스 권한을 갖습니다.
- 버스에서 유효하지 않은 메시지를 브로드캐스트합니다.
- 다른 캐시에서 후속 읽기 누락
 → 캐시 소유는 업데이트된 값을 제공합니다.

그림 5.41 나중 쓰기 캐시의 한 캐시 블록(X)을 위해 스누핑 버스에서 동작한 무효화 프로토콜의 예.

초기에 두 캐시 다 X를 갖고 있지 않고 메모리의 X 값이 0이라고 가정한다.

CPU와 메모리의 내용은 프로세서와 버스의 활동이 모두 끝난 후의 값을 보여준다. 빈칸은 아무 활동이 없거나 캐시에 아무 복사본도 들어가지 않는다는 것을 나타낸다. CPU B에 의해 두 번째 실패가 발생할 때 CPU A는 메모리로부터의 응답을 취소하고 자신의 값으로 응답한다. 이때 X의 B캐시 복사본과 메모리의 내용이 모두 갱신된다.

이렇게 블록이 공유될 때 메모리 갱신하면 프로토콜이 단순해진다. 하지만 데이터의 소유권을 추적하고 있다가 블록이 교체될 때만 나중쓰기를 수행하는 방법도 있다. 이렇게 하면 "소유(owner)"라는 새로운 상태가 필요하다. 소유 상태에는 다른 프로세서와 블록을 공유하고 있을 수도 있다. 그러나 소유 프로세서는 블록을 바꾸거나 교체할 때 모든 다른 프로세서와 메모리를 갱신할 책임이 있다.

 

결론적으로...

■ 빠른 기억은 작고, 큰 기억은 느리다.
- 우리는 정말 빠르고 큰 기억을 원한다.
- 캐싱은 이런 착각을 준다.
■ 지역성의 원리
- 프로그램은 메모리 공간의 작은 부분을 자주 사용합니다.
■ 메모리 계층
- L1 캐시 ↔ L2 캐시 ↔ … ↔ DRAM 메모리 ↔ 디스크

■ 메모리 시스템 설계는 멀티프로세서에 매우 중요합니다.