ch5.exercise

5.3번 문제들: 캐시 전체 비트 수 계산 및 성능 비교

 

문제 설명: 32KiB, 64KiB 캐시에 대해 태그, 유효 비트, 데이터 비트 총합을 계산하고, 블록 크기 변화에 따른 효과를 살펴본다.

• 1 KiB = 1024바이트

• 32 KiB = 32 * 1024 = 32768 바이트

• 64 KiB = 64 * 1024 = 65536 바이트

• 워드(Word) = 4바이트

 

5.3.1 (32KiB 캐시, 2-word 블록)

 

조건:

• 총 데이터 용량: 32KiB = 32768바이트

• 블록 크기: 2워드/블록, 1워드=4바이트 ⇒ 블록 크기 = 2 *4바이트 =8바이트

• 블록 수 = 총 용량 / 블록 크기 = 32768바이트 /8바이트 =4096블록

 

어드레스 비트 분해(32비트 주소):

• 오프셋(Offset) 비트 수: 블록 크기 8바이트 ⇒ log2(8)=3비트

• 인덱스(Index) 비트 수: 블록 수=4096 ⇒ log2(4096)=12비트

• 태그(Tag) 비트 수: 32 - (12+3)=17비트

 

각 블록마다:

• 태그: 17비트

• 유효 비트(Valid bit): 1비트

• 데이터: 8바이트(=64비트)

 

총 태그+유효 비트: (17+1)4096=184096=73728비트

총 데이터 비트: 32KiB =32768바이트=32768*8=262144비트

 

전체 비트 수 = 태그+유효+데이터 =73728+262144=335872비트

 

5.3.2 (64KiB 캐시, 16-word 블록)

 

조건:

• 총 용량: 64KiB =65536바이트

• 블록 크기: 16워드, 워드=4바이트 ⇒ 블록=16*4=64바이트

• 블록 수=65536바이트/64바이트=1024블록

 

주소 비트 분해:

• 오프셋: 64바이트/블록 ⇒ log2(64)=6비트

• 인덱스: 블록 수=1024 ⇒ log2(1024)=10비트

• 태그: 32-(10+6)=16비트

 

각 블록마다:

• 태그=16비트+유효=1비트=17비트/블록

• 총 태그+유효 비트:17*1024=17408비트

• 데이터 비트: 64KiB =65536바이트=65536*8=524288비트

 

전체 비트:524288+17408=541696비트

 

이 캐시는 이전 (5.3.1)의 32KiB 캐시보다 데이터 용량은 2배, 전체 비트 수도 증가했지만 블록 크기가 커서 태그 개수 감소효과가 있음. 그럼에도 더 큰 캐시임에도 오히려 태그 오버헤드는 덜 늘어남.

 

5.3.3

 

왜 64KiB 캐시가 더 큰데도 더 느릴 수 있는가?

• 블록 크기가 커지면 미스 발생 시 더 많은 데이터를 한 번에 가져와야 하므로 미스 패널티 증가

• 프로그램이 큰 블록 내부 데이터 모두 사용하지 않으면 낭비 발생(불필요한 데이터 전송)

• 또한 큰 블록은 더 적은 수의 블록을 의미하므로 어떤 워킹셋 패턴에는 오히려 충돌 미스가 증가할 수 있음.

즉, 더 큰 캐시라도 블록 크기 증가로 인해 오히려 성능이 떨어질 수 있다.

 

5.3.4

 

32KiB 2-way set associative 캐시와 32KiB direct mapped 캐시를 비교할 때, 2-way가 더 좋은 성능을 내는 요청 패턴 예:

• Direct mapped 캐시에선 같은 인덱스에 해당하는 다른 주소를 번갈아 접근하면 충돌이 발생해 매번 미스.

• 같은 상황에서 2-way 세트 연관은 같은 인덱스 라인 두 개 중 하나에 두 블록을 모두 저장 가능하므로 미스가 줄어듦.

예: 0x0000, 0x1000, 0x0000, 0x1000을 반복 접근 시 direct mapped는 계속 교체 발생, 2-way는 히트율 상승.

 

5.4번 문제: XOR 인덱싱 함수 사용 가능 여부

 

문제: 전통적 인덱싱은 단순히 주소 비트를 잘라서 인덱스로 사용. 여기서는 Block address[63:54] XOR Block address[53:44]와 같은 복잡한 인덱싱을 제안. 가능한가?

• 원칙적으로 하드웨어로 XOR 연산을 추가해 인덱스를 생성하는 것은 가능하다.

• 그러나 direct-mapped 캐시는 단순히 주소의 특정 비트 부분을 인덱스로 사용하여 빠르게 액세스하는 장점이 있다. XOR 같은 연산을 도입하면 하드웨어 복잡성 증가.

• 성능상 이득이 없다면 이렇게 하지 않는다.

 

즉, 가능은 하지만 일반적이지 않고 구현 복잡도가 증가한다. 실용적으로 거의 쓰지 않는다.

 

5.5번 문제들: 32비트 주소에서 주어진 필드(Tag, Index, Offset)로부터 블록 크기, 블록 수, 비트 비율 계산 및 접근 패턴 분석

 

문제 조건:

Tag: bits [63:10], Index: [9:5], Offset: [4:0] 라고 제시되었으나 이것은 교재 예시 형식으로, 실제 32비트 주소에서 태그가 63:10까지 나갈 수는 없다. 여기서는 문제에서 “the following bits of the address are used”라고 했으니, 상위 비트는 모두 태그로 간주하고, 인덱스와 오프셋 비트 수만 맞추면 됨.

 

가정: 32비트 주소 중

• Offset: 5비트([4:0])

• Index: 5비트([9:5])

• Tag: 나머지(22비트: [31:10])

 

5.5.1

 

오프셋이 5비트면 블록 크기 = 2^5=32바이트/블록. 1워드=4바이트 ⇒ 블록당 워드 수=32바이트/4바이트=8워드.

답: 8워드/블록

 

5.5.2

 

인덱스=5비트 ⇒ 블록 수(=라인 수)=2^5=32블록.

답: 32블록

 

5.5.3

 

데이터 전체 크기와 태그/유효 비트 비율 계산:

• 블록당 32바이트 데이터, 총 32블록 ⇒ 총 데이터=32*32=1024바이트=8192비트

• 태그=22비트, 유효비트=1비트/블록 ⇒ 23비트/블록 *32블록=736비트 오버헤드

• 전체=8192+736=8928비트

데이터 대비 전체 비율=8928/8192≈1.09 ⇒ 약 9% 추가 오버헤드.

답: 약 1.09:1 비율

 

5.5.4

 

여러 주소 접근(00,04,10,84,E8,A0,400,1E,8C,C1C,B4,884)에 대해:

1. 각 주소를 2진으로 변환

2. 오프셋(5비트), 인덱스(5비트), 태그(22비트) 분리

3. 캐시 초기엔 비어있으므로 첫 블록 접근은 미스 → 해당 블록 라인을 채운다.

4. 같은 블록 내 주소 접근 시 히트 발생

5. 다른 인덱스 또는 다른 태그로 접근 시 미스 발생

 

이 문제는 구체적인 수치가 매우 길어지므로 원리만 요약:

• 첫 번 주소(0x00): 미스 후 캐시에 로드

• 이어서 같은 블록 범위 내 주소들(예: 0x04, 0x10)이 오면 히트

• 새로운 블록에 속하는 주소(0x84, 0xE8 등) 접근 시 미스

• 같은 블록 재접근 시 히트

이 과정을 모든 주소에 대해 반복하면 각 접근의 히트/미스 판정과 대체된 바이트(교체된 바이트)를 나열할 수 있다.

 

5.5.5

 

히트율(hit ratio)는 5.5.4에서 계산한 총 히트 횟수/총 접근 횟수.

실제 계산은 각 접근 마다 히트/미스를 판정한 뒤, 히트 수를 세면 됨.

 

5.5.6

 

최종적으로 캐시에 남아 있는 각 블록의 <인덱스, 태그, 데이터> 상태를 나열. 데이터는 해당 블록에 적재된 메모리 범위를 표시. 접근 종료 후의 캐시 상태를 기록한다.

 

5.6번 문제들: L1/L2 캐시의 쓰기 정책(Write policy) 및 버퍼, 멀티 레벨 익스클루시브 캐시 전략

 

5.6.1

 

L1과 L2 사이, 또 L2와 메인 메모리 사이에 쓰기 버퍼(write buffer), 미스 핸들링용 버퍼, 프리페치 버퍼 등을 둘 수 있다. 문제의 요지는 L1 write-through, L2 write-back 등의 조합에서 레이턴시를 줄이기 위해 버퍼가 필요하다는 것. 가능한 버퍼:

• L1->L2 사이의 write buffer(작성 버퍼)

• L2->Memory 사이의 miss buffer나 prefetch buffer

 

5.6.2

 

L1 write-miss 처리 절차(더티 블록 교체 가정):

• L1에 블록이 없음: write-allocate이면 먼저 L2에서 블록을 가져와 L1에 적재.

• 이 때 L1에서 블록 교체가 필요하고, 교체되는 블록이 더티라면 L2로 해당 블록을 다시 써야(write-back) 함.

• L2에서도 만약 교체 발생 시 더티 블록을 메모리에 다시 써야 할 수도 있음.

• 즉 L1 miss → L2 접근, 필요 시 L1 더티 블록 write-back, L2 miss 시 메모리 접근… 이런 식으로 단계적으로 처리.

 

5.6.3 (Multilevel exclusive 캐시)

 

익스클루시브 캐시는 같은 블록이 L1과 L2에 동시에 존재하지 않는다.

• L1 read-miss: L2에 해당 블록이 있다면 L2에서 L1으로 블록을 이동(L1에 로드하면서 L2에서 제거). 메모리까지 갈 수도 있음.

• L1 write-miss:

• Write-allocate 시: L2에서 블록 가져와 L1에 적재 후 수정

• Non-write-allocate 시: L1에 적재하지 않고 L2(또는 메모리)에 직접 쓰기(write-through)

이때 항상 한 레벨에만 블록이 존재하므로 L1에서 블록을 가져오면 L2에선 제거, L2에 있던 것을 다시 L1으로 올리는 식으로 운영한다.

 

 

5.7번 문제: CPU 성능, 캐시 미스율, 대역폭 계산

 

주어진 상황:

• 프로그램 실행 시, 1000명령어당 data reads =250번, data writes=100번 발생.

• Instruction miss rate=0.30%, Data miss rate=2%, block size=64바이트

• CPU의 CPI(기본 CPI)=2라고 가정(즉, 캐시 미스 없으면 한 명령어당 2 사이클 정도 걸림).

 

5.7.1 (Write-through, Write-allocate 캐시에서 대역폭 계산)

• Read bandwidth(읽기 대역폭)과 Write bandwidth(쓰기 대역폭)을 구해야 한다.

• miss가 날 때마다 64바이트 블록을 메모리에서 가져온다.

• 1000명령어당 instruction fetch miss: 명령어 접근량: 1000명령어 당 보통 1000 instruction fetch라 가정. 미스율 0.30%면 1000번 중 3번 miss 발생. miss 1회 당 64바이트 읽음 → instruction miss로 인한 읽기 = 3 *64바이트=192바이트

• data read miss: data read는 1000명령어 당 250회, 그 중 miss율 2% →2500.02=5회 miss, 각 miss 때 64바이트 읽음 → 564=320바이트

• data write miss: data write=100, miss율 동일 2%라고 하면 write-allocate이므로 miss 시에도 block read 필요 (64바이트) →2회 miss 발생(1000.02=2), 264=128바이트 읽음

또한 write-through 이므로 모든 write는 메모리에도 쓰여야 한다. write hit일 때도 최소한 store를 메모리에 전달한다. 100회 쓰기 중 miss는 2회(이미 위에서 block 읽고 쓰는 과정), 나머지 98회는 write hit인데 write-through면 매번 적어도 4바이트(한 워드) 정도를 메모리에 써야 한다고 가정(문제 상세조건이 필요하지만 일반적으로 write-through는 매 쓰기마다 메모리에 1워드 정도 씀). 98회*4바이트=392바이트 write.

 

정리:

• Read 총량: instruction miss로 192바이트 + data read miss로 320바이트 + data write miss로 128바이트 → 총 640바이트 정도 읽기

• Write 총량: write-through는 모든 write를 메모리에 → 총 100회 writes *4바이트=400바이트 (추가적으로 block write-back은 없으나 write-allocate 시 miss 때 읽기는 했지만 바로 쓰기 반영은 write-through로 매번…)

(정확한 수치는 문제의 조건해석에 따라 다를 수 있으나 개념적으로 read miss 때 block 전송으로 읽기 대역폭, write-through로 매번 write로 쓰기 대역폭 발생.)

 

핵심: read bandwidth는 모든 miss 시 블록 크기만큼 읽어오는 바이트 수/1000명령어, write bandwidth는 write-through 때문에 대부분의 write가 메모리에 반영되는 것으로 계산.

 

5.7.2 (Write-back, Write-allocate, 30% dirty blocks)

• 여기서는 replaced data block의 30%가 더티(수정됨)라서 miss 시 새로운 블록을 가져오기 전에 더티 블록을 메모리에 64바이트 써야 함.

• read bandwidth: instruction/data miss 발생 시 64바이트 블록 읽기 동일.

• write bandwidth: 30% 확률로 블록을 쓸 때(교체 시) 64바이트를 메모리에 write-back.

• 따라서 miss 발생 비율에 따라 0.3*(미스 횟수)*64바이트만큼 write 발생.

정확한 수치는 문제 조건에서 명확히 주어진 계산식을 따른다. 핵심은 write-back은 miss 시에만 블록을 메모리에 다시 쓰며, 그 중 30% 정도 발생한다는 점이다.

 

5.8번 문제: 스트리밍 워크로드의 miss rate

 

상황:

• 워크로드가 순차적으로 0,1,2,3,… 이렇게 커다란 주소 공간(512KiB)을 스트리밍(한 번만 읽고 다시 안 쓰는)

• 64KiB direct-mapped 캐시, 블록 크기=32바이트 일 때 miss rate?

순차 접근이라 매번 새로운 블록 접근 시 한 번 miss 후 그 블록 내 나머지 주소는 히트.

하지만 스트리밍은 크기가 워킹셋보다 훨씬 커서 한 번 사용한 블록은 다시 안 씀. 결국 거의 매 블록당 첫 단어 접근 시 miss. 즉 miss rate는 (블록 내 워드 수 중 첫 워드 접근 시 miss 1번/블록 내 모든 워드 접근) 형태가 된다.

 

5.8.1

512KiB 데이터를 순차 접근, 블록당 32바이트면 총 512KiB/32바이트 = 16384블록. 모든 블록을 처음 접근할 때 miss 발생 → miss 16384번

접근 횟수(단어 주소 스트림 길이)는 매우 클 것이고 대부분 첫 접근당 miss. miss rate는 거의 100%에 가깝다(블록당 첫 접근이 miss이므로 1-block당 1번 miss, 이후 다시 같은 블록에 접근 없으면 miss율 ~100%).

이런 워크로드는 공간 지역성은 있으나(연속적), 재사용이 거의 없어 시간 지역성이 없다. 결국 캐시 크기를 늘려도 재사용이 없으면 miss rate 줄이기 힘들다.

 

5.8.2

블록 크기 16바이트, 64바이트, 128바이트로 바꾸면?

• 큰 블록일수록 한 번 miss 시 더 많은 데이터 가져오나, 어차피 한 번만 사용하고 지나가므로 추가로 가져온 데이터는 헛수고(사용 안 함).

• 블록 크기 커져도 miss 횟수는 총 접근한 블록 수와 비슷. 결국 miss rate 크게 안 줄어듦.

 

5.8.3 (Prefetching)

스트림 버퍼로 미리 다음 블록을 가져온다면, 현재 블록 사용 중에 다음 블록 미리 갖고 있으면 miss 없이 히트로 처리 가능. 이 경우 스트리밍에 딱 맞아, miss rate를 매우 낮출 수 있다. 이상적으로는 첫 블록 miss 이후 나머지는 프리페치로 히트 → miss rate 거의 1/블록 전체 개수 정도로 매우 낮아진다.

 

5.9번 문제: miss rate와 miss latency의 트레이드오프

 

block size 변화에 따라 miss rate가 바뀌고, miss latency(미스 처리 시간)도 바뀐다.

표:

• 8바이트: 4% miss

• 16바이트:3%

• 32바이트:2%

• 64바이트:1.5%

-128바이트:1%

 

miss latency가 B 사이클(블록 크기에 비례)라고 하면, block이 커질수록 miss latency 증가하지만 miss rate 감소.

 

5.9.1 (miss latency=20×B)

블록 크기 커질수록 miss latency 커진다. 여기서 최소화해야 할 것은 total miss penalty = miss rate * miss latency.

예:

• 8바이트: miss rate=4%, miss latency=20×8=160사이클 →평균 미스코스트=0.04160=6.4사이클

-16바이트: miss rate=3%, latency=20×16=320사이클 →0.03320=9.6사이클

-32바이트:2%, latency=20×32=640 사이클 →0.02640=12.8사이클

-64바이트:1.5%, latency=20×64=1280 사이클 →0.0151280=19.2사이클

-128바이트:1%, latency=20×128=2560 사이클 →0.01*2560=25.6사이클

 

가장 낮은 것은 8바이트일 때 6.4사이클.

답: 8바이트 블록이 최적.

 

5.9.2 (miss latency=24+B)

이제 latency는 24+(블록 크기)라고 가정.

-8바이트: latency=24+8=32사이클, miss rate=4% →평균=0.0432=1.28사이클

-16바이트: latency=24+16=40사이클, miss rate=3% →0.0340=1.2사이클

-32바이트:24+32=56사이클, miss rate=2% →0.0256=1.12사이클

-64바이트:24+64=88사이클, miss=1.5% →0.01588=1.32사이클

-128바이트:24+128=152사이클, miss=1% →0.01*152=1.52사이클

 

여기서 최소는 1.12사이클(32바이트)

답: 32바이트 블록 최적.

 

5.9.3 (constant miss latency)

miss latency가 block size에 상관없이 일정하다면, miss rate가 낮을수록 좋으므로 가장 큰 블록(128바이트)이 miss rate 1%로 최소. 이 경우 블록 크기를 크게 해서 miss rate를 낮추는 것이 최적.

 

5.10번 문제: L1 캐시 크기 변화로 인한 성능 변동

 

P1: L1=2KiB, 8% miss rate, L1 hit time=0.66ns

P2: L1=4KiB, 6% miss rate, L1 hit time=0.90ns

 

메모리 access=70ns, instruction 36%가 data, 나머지 instruction fetch.

 

5.10.1

L1 hit time이 사이클 타임 결정 → P1=0.66ns/사이클, P2=0.90ns/사이클

즉, P1 클럭은 더 빠름(주기가 짧음), P2는 더 큼=더 느린 클럭.

 

5.10.2

Average Memory Access Time(AMAT)= hit time + miss rate×miss penalty

P1: hit=0.66ns, miss=0.08×70ns=5.6ns추가 →AMAT~0.66+5.6=6.26ns

P2: hit=0.90ns, miss=0.06×70=4.2ns →AMAT=5.1ns

 

5.10.3

CPI=1.0(기본)+Memory stall

Memory stall 비율은 AMAT와 접근 횟수 고려

대략적으로 P2가 더 낮은 AMAT이므로 전체 CPI 낮아 P2가 더 빠름.

 

이후 L2 캐시 추가 시(5.10.4~5.10.7)는 L2 hit time, miss rate 고려해서 AMAT 다시 계산. L2 miss 시 메모리 접근. 목표: L2로 miss penalty 줄이고 CPI 감소. L2 miss rate를 조절해 P1을 P2보다 빠르게 만들 수 있다.

• 5.10.4: L2 추가하면 L1 miss→L2 접근해서 더 짧은 시간에 해결 가능. AMAT 계산 시 L1 miss penalty 대신 L2 hit time+L2 miss penalty로 바뀌며, L2가 크고 miss rate 낮으면 전체 AMAT 개선.

• 5.10.5~5.10.7: L2 miss rate를 어느 정도까지 줄이면 P1이 P2보다 빨라지나? 즉 L2가 충분히 좋으면 작은 L1+L2 조합이 큰 L1 단독보다 나아진다.

 

5.11번 문제: 다양한 캐시 디자인(직접사상 vs 세트 연관 vs 완전 연관), 블록 크기 변화, 대체 정책(LRU, MRU, Optimal) 시뮬레이션

 

여기서는 주소열(0x03,0xb4,0x2b,…)에 대해:

• 5.11.1: 3-way set associative cache 그림 그리기(48워드용), 각 라인에 몇 비트 태그, 데이터가 들어가는지. 블록당 2워드이므로 offset 비트=1, 전체 블록 수 계산해서 인덱스 비트 정하고 나머지는 태그.

• 5.11.2: 주어진 참조 주소마다 태그, 인덱스, 오프셋 나누고 해당 세트 내 LRU를 고려해 hit/miss 판단.

• 5.11.3: 완전 연관 8워드 캐시: 인덱스 없음(모두 한 세트), 태그만으로 식별, 매번 LRU로 교체.

• 5.11.4: 동일 접근 패턴을 완전 연관 캐시에 적용, 히트/미스 및 교체 추적.

• 5.11.5, 5.11.6: 2-word 블록 완전 연관 8워드 캐시, 각 참조 시 offset, tag만 확인, LRU로 교체, 히트/미스 기록.

• 5.11.7 (MRU): LRU 대신 MRU(가장 최근 사용) 교체 정책으로 다시 추적.

• 5.11.8 (Optimal): 최적 대체 정책(앞으로 가장 늦게 필요할 블록 교체)으로 다시 계산하면 miss 더 줄어듦.

 

핵심: 이 문제들은 실제로 주소를 2진수로 변환해 태그/인덱스/오프셋을 나누고, 각 접근마다 캐시 상태(어떤 태그가 어느 라인에 있나, 어떤 것이 LRU인지)를 갱신해야 한다. 여기서는 원리만 설명:

• Set associative나 fully associative일 때 인덱스가 줄어들거나 사라지고, 한 세트에 여러 블록이 들어가므로 miss가 줄어들 수 있다(충돌 줄음).

• LRU, MRU, Optimal 등의 대체 정책에 따라 miss 횟수가 달라진다. Optimal이 이론적으로 가장 miss가 적다.

 

 

5.12번: 멀티 레벨 캐시(Multilevel Caching)

• 기본 개념: L1 캐시 미스 발생 시 L2 캐시 접근, L2에서도 미스 나면 메인 메모리 접근. L2 캐시는 L1보다 크고 느리지만, L1 미스를 줄여 전체 성능 향상에 도움.

• 5.12.1: L1만 있을 때 CPI, L2를 직병렬(Direct-mapped)으로 추가했을 때의 CPI, 8-way 세트 연관 L2를 추가했을 때의 CPI를 계산.

방법:

1. 기본 CPI를 주고 (예: 1.5), L1 미스율, L2 미스율, 메모리 액세스 시간 등을 이용해 AMAT를 구한다.

2. AMAT(평균 메모리 접근 시간)으로부터 추가 사이클을 CPI에 반영.

3. 미스율이 절반으로 준다거나 메모리 접근 시간이 2배가 된다면 CPI가 어떻게 변하는지 비교.

핵심: L2 추가로 L1 미스를 빨리 해결해 CPI를 낮출 수 있고, 메인 메모리 접근 부담을 덜 수 있다.

• 5.12.2: L3 캐시 추가가 더 나은가?

L3는 L2보다 더 큰 캐시로, 더 낮은 레벨 미스를 줄인다. 하지만 액세스 시간이 더 길어질 수 있다. 장점: 미스율 추가 감소. 단점: 더욱 긴 접근 시간. 결과적으로 시스템 성능 향상 여부는 워크로드(프로그램 특성)에 따라 달라짐.

• 5.12.3: 과거 프로세서 사례(Pentium이나 Alpha) 언급. L2 캐시가 칩 외부에 있을 때 대역폭과 레이턴시 문제. 추가 캐시 용량으로 미스율 낮추는 대신 레이턴시 증가. 최적의 캐시 크기와 레벨 수는 균형 문제.

 

5.13번: MTBF(Mean Time Between Failures), Availability

• MTBF: 평균 고장간격(한 장치가 평균적으로 고장 없이 동작하는 시간)

• MTTR: 평균 수리시간

• Availability(가용성) = MTBF/(MTBF+MTTR)

문제에서 3년 MTBF, 1일 MTTR 등이 주어질 경우 시간을 같은 단위로 맞춘 뒤 계산. 예를 들어:

3년 ≈ 3*365일=1095일, MTTR=1일

Availability = 1095/(1095+1)=약 1095/1096≈99.9%

MTTR→0이면 가용성은 거의 100%에 수렴. MTTR 매우 커지면 장비 복구 힘들어 가용성 크게 떨어짐.

 

5.14번: SEC/DED (Single Error Correct / Double Error Detect) ECC 코드

• 5.14.1: 128비트 단어를 보호하기 위한 최소 패리티 비트 수 계산. SEC/DED 코드는 해밍 코드 변형으로, k비트 데이터 보호 위해 r비트 패리티 필요. 2^r ≥ k + r +1 조건 사용. 128비트일 때 r을 증가시키며 조건 만족하는 최소 r 찾음. 대략 128비트 보호 위해 약 8비트 정도의 패리티 필요(문제에서 자세히 계산 가능).

• 5.14.2: 64비트 당 8비트 패리티(예: 기존 코드 대비 새로운 코드) 성능/비용 비교. 패리티 비트 수(오버헤드) 대비 교정 성능(몇 개 에러까지 교정?) 비교. 적은 패리티로 동일 수준 교정 가능하면 효율적.

• 5.14.3~5.14.5: 8비트 데이터 보호에 4 parity bits 사용 시, 특정 값(0x375) 읽었을 때 오류 감지/수정 여부. 해밍 코드 테이블에 따라 에러 비트 위치 식별하고 수정 가능. 핵심: 해밍 코드로 단일 비트 에러는 교정, 이중 비트 에러는 검출 가능.

 

5.15번: 페이지 사이즈 최적화(Page size for B-tree index)

• 디스크 액세스 비용과 페이지 크기 선택. 페이지가 크면 한 번 읽을 때 더 많은 데이터 가져올 수 있으나 불필요한 데이터 전송 증가, 작은 페이지면 I/O 오버헤드 증가.

• 문제에서 표로 제공된 유틸리티(몇 개의 디스크 액세스 절약?), 인덱스 페이지 액세스 비용(ms), Utility/Cost 비율 제공.

• 5.15.15.15.3: 엔트리 크기나 페이지 반쯤 차있을 때, 디스크 대역폭 변할 때 최적 페이지 크기 재산정.

핵심: 주어진 조건에서 다양한 페이지 크기(2KB32KB 등)에 대해 Utility/Cost 비교 후 가장 높은 Utility/Cost 비율 갖는 페이지 크기 선택.

 

5.16번: 가상 메모리, TLB, 페이지 테이블 업데이트

• TLB(Translation Lookaside Buffer): 가상주소→물리주소 매핑 캐시. TLB miss 시 페이지 테이블 접근. 페이지도 메모리 없으면 디스크에서 로드(Page fault).

• 5.16.1: 주어진 가상 주소 스트림(예: 0x123d,0x08b3…)에 대해:

1. 페이지 번호와 오프셋 분리(4KiB 페이지면 하위 12비트 오프셋).

2. TLB에 해당 페이지 태그 있는지 확인 → 히트/미스 판정

3. 미스면 페이지 테이블 확인, 또 페이지가 메모리에 없는 경우 디스크에서 로드(page fault)

4. TLB 업데이트(LRU 방식)

이 과정을 각 주소에 대해 반복, 히트/미스, page fault 여부와 TLB 최종 상태 제시.

• 5.16.2~5.16.5: 페이지 크기 16KiB로 바꿔보거나, 2-way 세트 연관 TLB, direct-mapped TLB등 바꿨을 때 hit/miss 변화 파악. 페이지 크기 커지면 TLB 엔트리 수 감소하지만 miss penalty 증가 가능. Set associative TLB는 miss 줄일 수 있으나 접근 시간 증가.

• 5.16.5: 왜 TLB가 성능에 중요한가? TLB 없이 매번 페이지 테이블 접근하면 매우 느려짐. TLB는 가상→물리 변환을 빠르게 해 CPU 성능 유지.

 

5.17번: 페이지 테이블 크기 계산

• 파라미터: 32비트 주소, 8KiB 페이지, 4바이트 PTE(Page Table Entry)

• 5.17.1: 단일 레벨 페이지 테이블 크기 = (가상 주소 공간 / 페이지 크기) PTE크기

32비트 주소공간 =4GiB(≈42^30바이트)

페이지=8KiB=8192바이트

4GiB/8KiB=약 524288개 페이지 당 PTE 필요

PTE 하나 4바이트 → 총 524288*4바이트=약 2MiB 페이지 테이블 크기

5개의 프로세스라면 5배.

• 5.17.2: 2레벨 페이지 테이블 사용 시, 1레벨당 엔트리 수, 2레벨당 엔트리 수 계산해 실제 사용하는 PTE만 할당. 페이지 테이블 크기 감소. 최솟값: 필요한 엔트리만큼만 2레벨 페이지 테이블 할당, 최대값: 전체 가상 공간 커버하는 풀 트리 구성 시.

• 5.17.3: 페이지 크기 변화, 캐시 크기 변화에 따른 데이터 사이즈 결정. 가상 인덱스, 물리 태그 캐시 구현 시 데이터 부분 증가 필요성.

 

5.18번: 다단계 페이지 테이블 및 성능 최적화

• 5.18.1: 단일 레벨 페이지 테이블에서 PTE 수 = (가상공간/페이지크기).

• 5.18.2: 다단계 페이지 테이블로 메모리 절약. 활성화된 페이지만 PTE 할당. 레벨 수 = 주소 비트 분해해 상위 비트를 분배. 세그먼트 테이블+페이지 테이블 사용 시 세그먼트 테이블 크기, 페이지 테이블 크기 계산.

• 5.18.3, 5.18.4: 세그먼트 제한 시 테이블 깊이. 4바이트 PTE가 4KiB 페이지에 얼마나 많이 들어가는지, 필요한 레벨 수, 세그먼트 테이블 크기 등 계산.

 

5.18.5 (Inverted page table): 해시 기반 테이블에서 PTE 수 = 물리 메모리 페이지 수, 해시 충돌 시 추가 참조 필요. 보통 평균 1회 참조, 최악의 경우 여러 번 참조 필요. 장점: 크기 일정, 단점: 해시 충돌 시 탐색 비용 증가.

 

 

5.19번 문제 (TLB 상태표 분석)

 

표에 4-엔트리 TLB 상태가 주어지고, 각 엔트리에 Valid 비트, VA Page(가상 페이지), Modified 비트, Protection, PA Page(물리 페이지)가 있다.

• 5.19.1: 어떤 상황에서 엔트리 3의 Valid 비트를 0으로 만드는가?

TLB 엔트리의 Valid 비트는 그 엔트리에 해당하는 매핑이 더 이상 유효하지 않을 때 0으로 리셋된다. 예를 들어, 해당 페이지가 unmapped되거나, 프로세스 컨텍스트 스위치 시 flush, 해당 페이지 테이블 엔트리가 수정되었을 때 등의 상황.

즉, 페이지가 무효화되거나 해당 매핑이 사라지는 경우.

• 5.19.2: VA 페이지 30(가상 페이지 번호 30)에 접근 시 무슨 일이 일어나는가? 소프트웨어 관리 TLB vs 하드웨어 관리 TLB 비교.

하드웨어 관리 TLB의 경우 미스 시 하드웨어가 페이지 테이블 참조, 빠르게 TLB를 업데이트. 소프트웨어 관리 TLB는 miss 발생 시 OS 트랩, OS가 페이지 테이블 확인 후 TLB 업데이트. VA page 30이 TLB에 없으면 miss, 소프트웨어 관리라면 트랩 → OS처리 → TLB 업데이트 과정 필요.

소프트웨어 관리 TLB는 유연하지만 miss penalty가 클 수 있음. 특정 상황(특히 OS가 최적화할 때) 소프트웨어 관리가 빠를 수도 있지만 일반적으로 하드웨어 관리가 평균적으로 더 빠르다.

• 5.19.3: VA 페이지 200에 접근 시?

동일한 원리. TLB에 VA page 200 매핑 없으면 miss. miss 시 페이지 테이블 확인, 물리 페이지 찾기, TLB 업데이트. Protection 비트나 Modified 비트는 페이지 접근 권한과 쓰기 여부에 따라 설정.

 

5.20번 문제 (Replacement policy 영향)

2-way set associative 캐시, 각 세트 당 4워드 블록 중 2개 존재(2-way), 주소 시퀀스: 0,2,4,8,10,12,14,16,0,… 등

• 5.20.1 (LRU): LRU(Least Recently Used) 사용 시 어떤 접근이 히트인가?

주소를 순서대로 변환해 인덱스, 태그를 구한 뒤 캐시 라인에 들어가 있는지 확인. LRU는 가장 오래 사용하지 않은 블록을 치환. 반복적인 패턴(예: 0,2,4,8…)에서 일정 주기 후 다시 같은 블록이 온다면 히트 발생. 문제에서 0→2→4→8… 이런 식으로 일정한 패턴이라면, 실제 인덱스 계산 후 히트를 판단해야 한다. 여기서는 단순히 개념적으로: LRU 정책일 때 자주 재사용되는 어드레스는 히트 확률↑.

• 5.20.2 (MRU): MRU(Most Recently Used) 교체 정책은 마지막에 사용한 블록을 우선 추방. 이런 정책은 순차적 스트림에 불리할 수 있다. 예를 들어 0 사용 후 2,4,8… 계속 새로운 블록을 불러오면, 자주 재사용되는 블록을 계속 잘못 추방해 miss 증가 가능.

• 5.20.3 (Random): 무작위로 교체하면 평균적으로 LRU보다 성능이 떨어짐. 몇 번의 miss가 늘어나는지? 랜덤으로 동전 던지듯 선택 시 재사용 패턴을 전혀 활용하지 못해 miss가 증가.

• 5.20.4~5.20.5 (Optimal): 최적 정책은 앞으로 가장 늦게 사용될 블록을 교체. 실제 시스템에서 미래를 알 수 없으나, 최적 정책 가정 시 miss 최소화. 여기서는 실제 접근 시퀀스를 알고 있으므로, 가장 나중에 사용될 블록을 추방하면 miss 최소. Optimal 정책이 어떻게 miss를 줄이는지 설명 가능.

 

핵심: 교체 정책에 따라 동일한 접근 패턴에서 miss율 달라진다. LRU가 보통 좋은 성능, Random은 중간, MRU는 특정 패턴에 비효율적, Optimal은 이론적 최솟값.

 

5.21번 문제 (가상머신 성능, 트랩 오버헤드)

 

가상 머신(VMM) 환경에서 I/O 액세스, 트랩 오버헤드, CPI 계산 문제.

• 기본 CPI=1.5, priv. op. per 10,000 instr = 120, trap to guest OS=15 cycles, trap to VMM=175 cycles, I/O per 10,000 instr=30, I/O latency=1100 cycles 등 주어짐.

• 5.21.1: I/O가 없다고 가정하면 CPI 계산.

CPI = 기본CPI + (privileged op * trap penalty/명령어).

priv op 120/10,000명령어 → 0.012 priv op/명령어

각 priv op trap 15 cycles 추가 → 0.012*15=0.18 사이클 추가

총 CPI=1.5+0.18=1.68

VMM 오버헤드가 2배로 늘면 trap to VMM=350 cycles 가정 시, 만약 priv op 처리 시 guest OS→VMM 트랩 발생 시 추가적 계산 필요.

I/O 없으므로 I/O 부분 제외. 만약 VMM 오버헤드 절반이라면 trap penalty 절반 줄어 CPI 낮출 수 있다. 10% degradation 이하로 제한하려면 trap빈도와 penalty를 재계산해 최대 허용 cycle 도출.

• 5.21.2: I/O가 존재한다면 I/O miss penalty(1100 cycles) 고려. 비가상화 vs 가상화 환경 CPI 비교. 비가상화에서는 단순히 I/O latency만 반영, 가상화에서는 추가 trap to VMM 비용도 반영. I/O 빈도를 절반으로 줄이면 CPI 얼마나 개선되는지 계산 가능.

• 5.21.3: 가상화 장점/단점 정성적 비교. 언제 가상화 선호하는지 (서버 consolidation), 언제 기피하는지(극한 성능 요구).

 

5.23번 문제 (이기종 ISA 가상화)

 

QEMU같은 에뮬레이터 예를 들어, 다른 ISA를 에뮬레이션할 때 발생하는 어려움. 완전한 속도 달성 어려움, 원래 ISA보다 느려질 수 있음. 최적화 기법 필요. 이 문제는 정성적 설명.

 

5.24번 문제 (Write buffer 추가한 캐시 컨트롤러 FSM 설계)

• Write-back 캐시에서 더티 블록 교체 시 메모리 쓰기 때문에 시간 걸림. Write buffer 도입하면 프로세서는 블록 읽는 동안 더티 블록을 버퍼에 저장하고 비동기적으로 메모리에 쓰기.

• 5.24.1: 블록을 메모리에 쓰는 중 miss 발생 시 어떻게? write buffer 비우지 않고 miss 블록을 우선 가져올 수도 있음. 어떤 상황에서 stall하는지 설명.

• 5.24.3: Write buffer 지원하는 FSM 설계: 상태 다이어그램 그리기, miss 발생 시 dirty block write를 buffer에 enqueue, main memory write 끝나면 buffer 비움. 상태 전이와 신호, 제어 로직을 서술.

 

5.25번 (Cache coherence)

 

두 프로세서가 같은 캐시 블록 X의 다른 단어에 read/write. 캐시 일관성 프로토콜 없으면 한 프로세서 업데이트가 다른 쪽에 반영 안됨. 나쁜 값 관측 가능.

• 5.25.1~5.25.3: 일관성 보장 위해 MESI 또는 Snooping 프로토콜 사용. 가능한 시나리오 나열. Best case: 한 번의 invalidate, write-back 최소화. Worst case: 서로 번갈아 업데이트 → 매번 invalidation, miss 발생.

기본적으로 coherence는 read/write 순서에 따라 다양한 miss 패턴 생김.

 

5.26번 문제 (CMP - 멀티코어 Private vs Shared L2 캐시)

 

벤치마크 A,B에 대해 Private L2 vs Shared L2 miss율, hit latency 차이 비교.

• Private L2: 각 코어 전용 L2. Miss율 높을 수 있으나 hit latency 짧음(5 cycles).

• Shared L2: miss율 낮추나 latency 길어짐(20 cycles).

• 메모리 접근 180 cycles.

• 5.26.1: 어떤 벤치마크에 어떤 캐시가 좋은가? miss rate vs latency trade-off. 예: A는 10% vs 4%, B는 2% vs 1%. A의 경우 miss율 차이가 크므로 shared가 좋을 수 있음. B는 miss율 차이 적으나 latency 차이가 클 경우 private가 나을 수도 있다.

• 5.26.2: 코어 수 늘어나 off-chip 대역폭 병목 증가. Shared 캐시는 miss율 낮춰 off-chip 접근 줄일 수 있으나 latency 커짐. off-chip 대역폭이 두 배 필요하면 어떤 구조가 유리한지 분석.

• 5.26.3: single-threaded(코어 하나), multithreaded(동일 프로그램 여러 스레드), multiprogramming(서로 다른 프로그램) 상황에서 private vs shared L2 장단점. Shared는 전체 miss율 낮출 수 있지만 한 프로그램에 대한 보장 줄어듦, private는 독립성 but miss 많음.

• 5.26.4~5.26.6: Non-blocking L2, off-chip 대역폭 증가 필요성, concurrency 개선 등. 미래 코어 수 증가 시 off-chip BW가 얼마나 증가해야 동일 성능 유지? Miss를 효율적으로 처리하기 위해 비차단 캐시나 더 큰 대역폭 필요.

 

5.27번 문제 (로그 처리 최적화)

 

구조체 entry {srcIP, URL, refTime, status, browser[64]}

가장 많이 쓰는 필드는 캐시에 잘 들어맞는 곳에 배치. 64바이트 캐시 블록 가정 시, 자주 접근하는 필드를 한 블록 안에 몰아서 공간 지역성 향상. URL이나 browser같이 큰 필드는 덜 자주 쓰이면 뒤로 배치.

• 5.27.1: log entry에서 가장 자주 읽는 필드 식별, 그 필드를 블록 경계 맞춰서 배치하면 miss 감소.

• 5.27.2: 데이터 구조 재배치로 더 나은 spatial/temporal locality 달성.

• 5.27.3: 다른 로깅 함수와 결합 시에도 캐시 효율 개선 가능. hot field와 cold field 분리.

 

5.28번 문제 (SPEC CPU2000 캐시 성능 자료 활용)

• 5.28.1~5.28.3: MESA/GCC vs MCF/SWIM 같은 벤치마크 조합에서 64KiB, 1MiB L2 캐시, 세트 연관도 변화에 따른 miss type(Cold, Capacity, Conflict) 분석. 더 큰 캐시에선 capacity miss 줄고, 연관도 증가 시 conflict miss 줄어듦.

• 최적 세트 연관도 선택: L1은 direct-mapped, L2는 4-way 등 제안.

• 5.28.3: 세트 연관도 증가하면 라인 당 태그 저장 많아져서 태그 스토리지 늘어남. miss rate 낮출 수 있지만 비용↑.

 

5.29번 문제 (2단계 가상화: Shadow page table, Nested page table)

 

VA→PA→MA(Nested) 변환 시 TLB miss 처리에 더 많은 메모리 접근 필요.

• 5.29.1: Shadow page table vs Nested page table 시 같은 작업(프로세스 생성, TLB miss, page fault, context switch)에서 발생하는 동작 비교. Nested PT는 두 번의 페이지 테이블 워크 필요.

• 5.29.2: x86 4-level page table vs nested page table 접근 횟수 비교. TLB miss 시 native는 4번 테이블 접근(최대), Nested는 4번 * 2 =8번 등 더 많음.

• 5.29.3: TLB miss rate, miss latency, page fault rate, page fault handler latency 중 nested PT에서 중요한 것은 miss latency 및 reference count. Nested로 인한 2배 탐색 비용이 성능 영향.

• 5.29.4: NPT(Nested Page Table) 오버헤드로 CPI 변화 계산. 예: Base CPI=1, TLB miss per 1000 instr=0.2, NPT TLB miss latency=200 cycles, shadowing overhead=30,000 cycles/page fault 등.

각 이벤트 확률×penalty 더해 CPI 추산.

• 5.29.5~5.29.6: Page table shadowing 감소 기법, 예: Huge pages 사용, TLB reach 확대, 소프트웨어 최적화로 shadow overhead 감소. NPT 오버헤드 줄이기 위해 캐시된 변환 사용, 대형 페이지로 테이블 단계 줄이기.

 

정리:

 

• CPI 계산: CPI = Base CPI + (Event Frequency * Event Penalty)

• Page table 크기: (Virtual Memory Size / Page Size) * PTE Size

• ECC parity bits: 2^r ≥ data_bits + r + 1 조건으로 r 구하기.

• Replacement policy: 실제 접근 시퀀스 나열 후 hit/miss 판단.

• I/O 오버헤드: I/O 빈도 × I/O penalty를 CPI에 추가.