Normally, there exists a trade-off between speed and memory size, price
지역성의 원칙 (principle of loality)
프로그램은 한 번에 주소 공간의 일부분만 접근한다. 즉, 일반적으로 프로그램은 주소 공간의 일부만 사용한다.
시간적 지역성(temporal locality) :
최근에 접근한 항목은 가까운 시점에 다시 접근될 가능성이 높다.
예: 반복문 내의 명령어, 순환 변수(for문에서 i)
공간적 지역성(spatial locality) :
최근에 접근한 항목 근처의 데이터가 곧 접근될 가능성이 높다.
예 : 순차적인 명령어 접근, 배열 데이터
Memory Hierarchy
▪ Store everything on disk (lowest level)
▪ Copy recently accessed (and nearby) items from disk to smaller DRAM memory (e.g., Main memory)
▪ Copy more recently accessed (and nearby) items from DRAM to smaller SRAM memory (e.g., Cache memory)
Lowest level must have all the data
Data is copied between only two adjacent levels at a time
블록: 두 계층간 정보 전송의 최소 단위
- 복사의 단위
- 여러 단어로 구성될 수 있음
Hierarchical Access
- 데이터가 상위 계층에 있으면 Hit
- 데이터가 없으면 Miss
- 블록은 하위 계층에서 복사됨
- 데이터는 상위 계층에서 제공됨
SRAM Technology
Data stored using 6 ~ 8 transactors in an IC
▪ Fast, but expensive
▪ Fixed access time to any datum
▪ No refresh required
▪ Usually for caches, integrated on processor chips
DRAM Technology
데이터는 Capacitor의 전하(Charge)로 저장됨.
전하 접근을 위해 단일 트랜지스터 사용.
Capacitor의 전하는 시간이 지나면서 누출됨(물리적 특성).
주기적으로 새로 고침(read & write-back)이 필요함.
- Synchronuous DRAM(SDRAM)
클럭 신호를 사용하는 DRAM으로 대역폭이 향상됨.
- DDR(Double Data Rate) DRAM
상승 및 하강 에지에서 모두 데이터 전송
Flash Storage
비휘발성(Non-volatile) 반도체(Semiconductor) 저장 장치(EEPROM의 한 종류)
- 디스크보다 100~1000배 빠름.
- 더 작고, 전력 소모가 적으며, 더 견고함.
- 그러나 $/GB 더 높음(디스크와 DRAM 사이).
* EEPROM : 전기적으로 지우고 프로그래밍 가능한 ROM, 전원이 꺼져도 데이터 유지
- NOR 플래시: NOR 게이트와 유사한 비트 셀 구조
랜덤 읽기/쓰기 가능
임베디드 시스템의 명령어 메모리에 사용
- NAND 플래시: NAND 게이트와 유사한 비트 셀 구조
면적당 비트 밀도가 높음, 블록 단위 접근
GB당 비용이 저렴
USB 키, 미디어 저장 장치 등에 사용
- 플래시 비트는 수천 번 접근 후 마모됨.
- 직접 RAM으로 사용하기 부적합.
- 웨어 레벨링(Wear leveling): 덜 사용된 블록으로 데이터 재배치.
Disk Storage
Nonvolatile, Rotating Magnetic Storage
섹터에 기록된 내용
- 섹터 ID
- 데이터: 512바이트 (제안된 크기 4096바이트)
- 오류 수정 코드(ECC)
- 동기화 필드와 간격
섹터 접근 과정
- 탐색(Seek): 헤드 이동
- 회전 지연(Rotational Latency, average = 0.5): 평균 0.5회전
- 데이터 전송(Data transfer)
- 컨트롤러 오버헤드 (Controller overhead)
Example : Given 512B sector, 15,000 rpm, 4ms average seek time, 100MB/s transfer rate, 0.2ms controller overhead, idle disk. What is the average read time?
seek time(given) +
rotational latency(rpm → rps → 1/2를 나누기) +
transfer time(transfer rate로 구하기) +
controller overhead(given)
Disk Performance Issues
제조업체는 평균 탐색 시간을 다음과 같이 인용:
- 가능한 모든 탐색을 기반으로 함
- 지역성 및 OS 스케줄링이 실제 평균 탐색 시간을 더 작게 만듦
스마트 디스크 컨트롤러는 디스크의 물리적 섹터를 할당한다:
- 호스트에 논리적 섹터 인터페이스 제공
- SCSI, ATA, SATA
디스크 드라이브에는 캐시가 포함됩니다:
- 접근을 예측하여 섹터를 미리 가져옴
- 탐색 및 회전 지연을 피함
Direct Mapped Cache
직접 사상(direct mapped) : 각 메모리의 위치가 캐시 내의 정확히 한 곳에만 사상되는 캐시 구조
거의 모든 직접 사상 캐시는 다음의 사상 방식으로 캐시 블록을 찾는다
(블록 주소) modulo (캐시 내에 존재하는 전체 캐시 블록 수)
캐시 내의 블록 수가 의 거듭제곱이면, 주소의 하위 log2(캐시 내의 전체 블록 수) 비트를 취하여 modulo 연산을 한다
태그 : 찾은 블록이 요청한 워드에 해당하는지 아닌지를 식별하는데 필요한 주소 정보를 담고 있는 필드로 캐시 인덱스로 사용하지 않은 주소의 상위 부분 비트들로 구성된다.
컴퓨터를 처음 켜서 프로세서가 작업을 시작할 때 캐시는 비어있을 것이며, 태그 필드는 아무 의미가 없을 것이다. 따라서 이들 엔트리의 태그들은 무시되어야 한다. 따라서 유효 비트를 추가해서 이 비트가 0이면 이 엔트리는 유효한 블록이 없는 것으로 간주한다
Subdivision은 메모리 계층에서 데이터를 효율적으로 찾고 접근하기 위해 컴퓨터 아키텍처에서 필수적.
- 태그(Tag): 메모리 주소의 가장 상위 부분으로, 캐시 블록에 올바른 데이터 블록이 있는지 식별하는 데 사용됨.
- 인덱스(Index): 주소의 중간 부분으로, 해당 주소가 어떤 캐시 블록에 매핑되는지를 결정합니다. 예제에서는 캐시 크기가 2^10이므로 인덱스는 10비트 길이입니다.
- 블록 오프셋(BlockOffset): 주소의 가장 하위 부분으로, 캐시 블록이나 메모리 블록 내에서 정확한 위치를 지정함.
Block Size Consideration
- Larger blocks reduce miss rate : Spatial Locality
- But, in fixed-size cache → Large block means fewer blocks in cache.
- Increased conflict misses:
same cache block is frequently overwritten by competing addresses
Cache Pollution
- Larger block means larger miss penalty
Cache (Read) Misses
캐시 히트 시, CPU는 정상적으로 작동.
캐시 미스 시,
- 다음 계층(메인 메모리)에서 블록을 가져온다.
- 메인 메모리에 읽기 작업을 요청하고, 메모리가 접근을 완료할 때까지 기다린다.
- 데이터를 캐시 항목에 기록 (데이터, 태그, 유효 비트 포함).
- 캐시 접근을 재시작.
- 명령어 캐시 미스의 경우: 원래의 PC 값(즉, PC - 4)을 보내고, 명령어 페치 작업을 재시작합니다.
- 데이터 캐시 미스의 경우: 데이터 접근을 완료합니다.
(1) Write-Through
항상 캐시와 메모리를 모두 업데이트.
- 먼저 캐시에 쓰고, 그 다음 메모리에 쓴다.
- 간단하지만 '스토어(store)' 명령어가 더 오래 걸린다.
- 만약 기본 CPI가 1이고, 명령어의 10%가 '스토어'이며, 메모리에 쓰는 데 100 사이클이 걸린다면, 유효 CPI는 1 + 0.1 x 100 = 11이 된다.
해결책: 'Write Buffer'
- 메모리에 쓰는 데이터를 저장.
- CPU는 즉시 계속 진행되며, 쓰기 버퍼가 꽉 차지 않으면 쓰기 지연이 발생하지 않는다.
(2) Write-Back
캐시에서만 업데이트하고, 수정된 블록은 교체될 때 메모리에 쓴다.
- 데이터 쓰기 히트 시, 캐시 내 블록만 업데이트.
- 더티 블록이 교체될 때,
- 메모리에 다시 쓴다.
- 블록을 먼저 읽을 수 있도록 쓰기 버퍼를 사용한다.
보통 더 빠르지만, 훨씬 더 복잡하다.
- 미스를 감지하기 전에 캐시를 덮어쓸 수 없다.
- 먼저 미스를 감지하고, 그 다음에 캐시에 써야 한다: 즉, 감지에 추가적인 사이클이 필요합니다.
Cache (Write) Misses
Write Allocation : 쓰기 미스가 발생했을 때, 메모리를 캐시로 가져와야 하는가?
- Write-through의 경우:
- Allocate on miss : 블록을 가져온다
- Write around : 블록을 가져오지 않는다
- Write-back의 경우:
- 보통 블록을 가져온다.
Measuring Cache Performance
CPU Time = (CPU Execution Time) + (Memory-stall time)
CPU Execution Time = Program Execution Cycles (including cache hit time)
Memory Stall Cycles = Mainly from Cache Misses
Average Memory Access Time
AMAT = Hit time + Miss rate * Miss Penalty