cache memories acting as staging areas between CPU and main memory, having the most impact on application program performance
for C programmers…
the book show how to your C programs for localityand introduce techniques for imporving the locality in your programs.
Storage Technologies
RAM
SRAM is persistent as long as power is applied. Unlike DRAM, no refresh is necessary. SRAM can be accessed faster than DRAM. SRAM is not sensitive to disturbances such as light and electrical noise. The trade-off is that SRAM cells use more transistors than DRAM cells and thus have lower densities, are more expensive, and consume more power
DRAM / Dynamic RAM
메인 메모리와 그래픽 시스템의 frame buffer에 쓰임.
각 비트를 축전기에 전하로 저장합니다.
SRAM
CPU 칩의 on/off 모두에서 cache 메모리로 사용됨.
각 비트를 distable memory cell에 저장하는데, 각각의 셀은 6-transistor 회로로 구현된다.
비휘발성 메모리 Nonvolatile Memories
DRAM 과 SRAM은 휘발성 메모리이므로 전원이 꺼졌을 때 정보를 잃는다.
비휘발성 메모리는 전원이 꺼져도 정보를 유지한다.
이름
축약어
기능
Read-only memory
ROM
programmed during produc;on
Programmable ROM
PROM
can be programmed once
Eraseable PROM
EPROM
can be bulk erased (UV, X-Ray)
Electrically eraseable PROM
EEPROM
electronic erase capability
Flash memory
EEPROMs. with partial(block-level) erase capability
solid state disk (replace rotating disks in thumb drives..)
Disk Caches
Traditional Bus Structure Connecting CPU and Memory
BUS
a collection of parallel wires that carry address, data, and control signals.
버스는 보통 다중 디바이스들이 공유한다.
Memory Raed Transcation
CPU가 주소 A를 메모리 버스에 올린다.
The I/O bridge passes the signal along to the memory bus
메인 메모리가 A를 버스에서 읽어서 주소 A에 있던 word X를 검색하여 버스에 올린다.
CPU가 word X를 버스에서 꺼내 레지스터 %rax에 복사해간다.
Memory Write Transcaction
movq %rax,A 와 은 명령어를 수행하면 레지스터 %rax의 내용물이 주소 A에 쓰인다.
CPU가 버스에 올린 주소 A를 메인 메모리가 읽어서 대응하는 데이터 word가 도착하기를 기다린다.
CPU가 데이터 word y를 버스에 올린다.
메인 메모리가 버스로부터 word y를 읽고 주소 a에 그것을 저장한다.
What’s Inside a Disk Drive?
DIsk는 매우 많은 양의 데이터를 보관할 수 있는 견고한 저장 장치이다. the hundreds or thousands of megabytes RAM기반 메모리와 반대로 the order of hundreds to thousands of gigabytes를 가지고 있다. 그러나 많이 저장한 만큼 DRAM보다 느리고 SRAM보다는 훨씬 더 느리다.
Disk Geometry 디스크 형상: 디스크는 원판으로 구성되어있다.
Disck Capacity 디스크 용량
Recording Zones
Computing Disk Capacity
Disk Operation
Disk Strucutre
Disk Access
Disk Access Time
Logical Disk Blocks
0, 1, ..B-1 로 번호를 붙인 B 섹터 크기의 논리블록의 배열로 구조를 단순화한다.
Mapping between logical blocks and actual physical sector: 디스크 패키지 안에 있는 디스크 컨트롤러라는 이름의 하드웨어/펌웨어 디바이스는 논리블록 수와 실제 디스크 섹터와의 메핑을 유지한다.
I/O Bus
그래픽카드, 모니터, 마우스 키보드, 디스크 같은 입출력장치들은 입출력 버스로 CPU와 메인메모리에 연결된다.
메모리 버스와 시스템 버스는 CPU에 특화되어있으나, PCI 같은 입출력 버스는 하부 CPU에 독집적으로 구성되어 시스템/메모리 버스보다는 더 느리다. 그러나 타사의 광범위한 I/O 디바이스를 연결할 수 있다.
Reading a Disk Sector
CPU는 명령어/논리블록 번호/ 목적지 메모리 주소를 디스크와 연결된 메모리 매핑 port(주소)에 기록함으로서 디스크 읽기를 시작한다.
디스크 컨트롤러는 이 섹터를 읽고 메인 메모리로 직접 메모리 전송을 수행한다.
DMA(직접 메모리 접근)이 완료될 때, 디스크 컨트롤러는 CPU에 인터럽트로 알려준다.
SSD : Solid State Disks
SSD performance Characteristics
읽어오기 작업이 쓰기 작업보다 더 빠른데 이는 SSD의 B블록들이 플래시 메모리로 구성되어있기 때문이다.
한 개의 블록을 지우는 건 1ms단위로 상대적으로 긴 시간이 걸리고 페이지에 접근하기 위해 걸리는 시간보다 한 단위 정도 더 걸린다. ‘
어떤 쓰기 연산이 이미 존재하는 데이터를 포함하는 페이지를 수정하려면 수행되어야 하는 작업이 있다.
SSD Tradeoffs VS Rotating Disks
장점: 반도체 메모리로 만들어져서 회전하는 디스크보다 Random access 시간이 더 빠르고 더 적은 전력을 소모하고 더 견고하다.
단점: 플래시 블록이 반복적인 쓰기 작업 후에 노후화되어 SSD도 노후화할 가능성이 있다. SSD는 회전하는 디스크보다는 좀 더 비싸다.
CPU-Memory gap
the key to bridging this CPU-Memory Gap is fundamental property of computer programs known as locality
Locality
Well- written programs exhibit a property called locality: 잘 작성된 프로그램은 다른 최근에 참조했던 data item 근처의 data item이나, 최근에 자신을 참조했던 data item을 참조하려는 경향이 있다.
← 들이 좋은 프로그램들의 특성이란..
시간 지역성Temporal locality
한번 참조된 메모리 위치가 가까운 미래에 다시 여러번 참조될 가능성이 높다.
공간 지역성Spatial locality
어떤 메모리 위치가 참조될 때, 근미래에 근처의 메모리 위치를 참조할 가능성이 높다.
하드웨어 수준에서 컴퓨터 디자이너들은 지역성의 원칙을 사용해 가장 최근에 참조한 명령어와 data item의 블록을 저장하고 있는 캐시 메모리라는 작고 빠른 메모리를 도입해서 메인메모리를 빠르게 돌릴 수 있게 하였다.
ex) 웹 브라우저는 디스크 상의 최근 참조한 문서들을 캐싱해서 시간적 지역성을 활용하거나 대용량 웹서버들은 최근 요청 문서들을 최전방 캐시에 저장해둔다.
운영체제와 지역성
시스템이 메인 메모리를 가장 최근에 참조한 가상 주소공간 블록에 대한 캐시로 사용할 수 있게 해준다.
메인메모리를 가장 최근에 사용된 디스크 파일 시스템 상의 디스크 블록을 캐시하기 위해 사용한다.
Locality Example
Qualitative Estimates of Locality
좋은 시간 지역성
동일 변수들을 반복적으로 참조하는 프로그램은 좋은 시간 지역성을 가지다.
stride-k 참조 패턴을 갖는 프로그램은 stride가 적으면 적을수록 공간 지역성도 좋아진다. 즉, stride-1 참조 패턴을 갖는 프로그램들은 좋은 공간 지역성을 가진다. k값이 큰 프로그램들은 공간 지역성이 좋지 못하다.
루프는 명령어 선입에 대해 좋은 시간/공간 지역성을 보인다. 루프 본체가 작을수록 루프 반복 실행의 수는 더 커지고 지역성도 더 좋다.
The memory Hierachy
M.H based on caching close the gap by exploting locality
각 레벨에 있는 저장장치가 다음 낮은 레벨을 위한 캐시이다.
HW와 SW에 대한 기본 속성
빠른 저장 기술은 바이트 당 더 비싸고, 더 적은 용량을 가지며, 더 많은 전력을 요구한다.
CPU와 메인 메모리 속도 격차는 더 커지고 있다.
잘 짜여진 프로그램은 좋은 지역성을 보이는 경향이 있다.
→ 메모리와 저장 시스템에 대한 접근 방법을 제안한다: 바로 메모리 계층 구조가 그것이다.
Cache
더 크고 느린 장치에 저장된 데이터의 subset을 위한 staging area(준비 영역)으로 사용되는 더 작고, 더 빠른 저장 장치
모든 각각의 K에 대해, K 레벨에 있는 더 작고 더 빠른 장치는 K+1레벨에 있는 더 크고 더 느린 장치에 대한 캐시로서 사용될 수 있다.
가령 로컬 디스크는 네트워크 너머 원격 디스크로부터 가져온 파일들(웹페이지 같은 ㅓㅅ들)에 대한 캐시로 서비스하고, 메인 메모리는 로컬 디스크 상의 데이터에 대한 캐시로 서비스하는 식으로 가장 작은 캐시인 CPU 레지스터 집합에 이를 때까지 이를 계속한다.
왜 메모리 계층구조가 작동할까?
지역성 때문에 프로그램은 K+1레벨에 있는 데이터에 접근하기보단 K레벨에 있는 데이터에 접근하려고 한다. 따라서 K+1레벨에 있는 저장장치는 느려질 수 있고, 따라서 bit당 더 크고 더 싸다.
The memory hierarchy creates a large pool of storage that costs as much as the cheap storage near the bottom, but that serves data to programs at the rate of the fast storage near the top.
General Cache Concepts
K레벨에 있는 저장장치는 K+1 레벨의 저장장치에 있는 블록들과 같은 크기인 블록으로 4, 9, 14, 3의 사본을 갖고 있다.
데이터는 항상 K와 K+1 레벨 사이에서 블록 크기의 전송 유닛 단위로 복사되며, 계층구조의 인접한 모든 쌍들 사이에서 블록 크기가 고정되어 있으나 다른 레벨의 쌍들은 블록 크기가 다를 수 있다. 가령 L0과 L1 사이는 일반적으로 word 크기의 블록을 사용하지만 그 외 계층은 수백/수천/수십 바이트의 블록을 사용한다.
Hit
어떤 프로그램이 K+1 레벨로부터 특정 데이터 객체 d를 필요로 할때, 현재 래밸 k에 저장된 블록들 중에서 d를 먼저 찾는다. 이때 만약 d가 k에 우연히 캐시되어 있을 때 이 경우 ‘캐시 적중Cache Hit’이라고 부른다.
Miss
반대로 객체 d가 레벨 k에 캐시되어있지 않는다면 캐시 미스가 발생한다. 캐시 미스가 존재한다면 레벨 k에서의 cache는 k+1의 캐시로부터 d를 포함한 블록을 가져오고, k레벨의 cache가 꽉 찬 상태라면 기존 블록에 덮어 쓴다.
기존 블록에 덮어쓸 때 블록을 교체/촉출하는데, 후자의 블록을 victim block 희생 블록이라고 부르는데 어떤 블록을 교체할 것인지는 cache’s replacement policy에 달렸다.
위 그림에서, k레벨에서 블록 12에서 데이터 객체를 읽으면 블록 12가 현재 레벨 k에 저장되어있지 않으므로 캐시 미스가 발생하고, K+1에서 레벨 k로 복사된 후에 블록 12는 다음번 접근을 예상하여 거기에 남아 있게 된다.
Type of Cache Miss
cold miss: cache가 비어 있어서 발생한다.
Cold misses are important because they are often transient events that might not occur in steady state, after the cache has been warmed up by repeated memory accesses
conflict miss(충돌 미스):
capcity miss(용량 미스): 동적 캐시 블록의 집합(working set)이 cache보다 더 클 때 발생한다.
프로그램이 일련의 단계(예: 루프)에 따라 실행될 때, 각 단계마다 캐시 블록의 집합에 접근한다. 중첩 루프는 동일한 배열 원소들에 계속해서 반복해서 접근하는데 이때 이 block의 집합을 working set이라고 부른다.
Cache memories (organization & operation)
Cache memories can have significant performance impact.
Cache Memories
하드웨어에서 자동으로 관리되는 작고 빠른 SRAM 기반의 메모리이며, 메인 메모리의 접근된 블록을 자주 붙잡는다. CPU는 cache에 있는 데이터부터 먼저 본다.
General Cache Organization
Cache Read
Direct-Mapped Cache Simulation
E-way set Associative Cache
캐시 읽기 동작 요약
원하는 워드 w의 사본을 캐시에서 찾는다.
적중이 발생하면(캐시에 w의 사본이 있다면) w를 리턴하고, 미스가 발생하면 메모리 계층구조의 다음 하위 레벨에서 w를 포함하고 있는 블록을 같은 캐시 라인에 선입 및 저장하여 w를 리턴한다.
이 과정에서(선입과정에서) 유효한 라인 하나를 희생해야 할 수도 있다.
Writing Cache-Friendly Code
what about write?
이미 캐시에 저장된 워드 w를 쓴다면?
write-hit
워드 w가 이미 캐시에 들어 있는(쓰기 적중한) 상황에서 워드 w를 쓰려할 땐?
write-through
메모리에 즉시 쓴다.
no-write-allocate 방식
write-back
갱신을 지연하여 이 블록이 교체 알고리즘에 의해 캐시에서 축출될 때에만 갱신할 블록을 하위 레벨에 써준다.
버스 트래픽을 줄일 수 있으나 복잡하다. dirty bit(캐시 블록이 수정 되었는지 아닌지를 표시하는 비트)가 필요하다. write-allocate방식
write-miss
워드 w가 캐시에 들어있지 않은 상황이라면?
write-allocate
캐시에 로드하고 캐시 블록을 갱신.
no-write-allocate
캐시에 로드하지 않고 직접 메모리에 쓴다.
Intel Core i7 Cache Hierachy
Cache performance Metrics
Let’s think about thoes numbers…
Writeing cache friendly code
Make the common case go fast.
Minimize the number of cache misses in each inner loop.
Cache line / sets, blocks
block
캐시와 메인메모리 사이에서 앞뒤로 이동하는 고정된 길이의 패킷 정보
line
블록, 유효 비트(valid bit_과 태그 비트같은 추가정보를 저장하는 캐시 내의 저장소
sets
하나 이상의 라인이 모인 것.
Our qualitative notion of locality is quantified through our understanding of cache memories
