Aufgabe 8 기초 개념 · RO Probeklausur

교재처럼 순서대로 읽는 본문

이 글은 요약 카드가 아닙니다. 처음 보는 용어의 뜻부터 시작해, 왜 그런 규칙이 생겼는지와 문제에서 어떻게 사용하는지를 한 흐름으로 설명합니다.

이 장을 공부하는 이유

Cache 문제는 암산 속도보다 기록 습관이 중요합니다. 주소를 tag/set/offset으로 자르고, 접근할 때마다 각 set의 현재 내용과 ‘이 block을 전에 본 적 있는가’를 갱신하면 miss type이 자동으로 결정됩니다.

읽고 나면 할 수 있어야 하는 것

다단계 AMAT를 조건부 확률로 계산한다.
address에서 block offset·set·tag를 계산한다.
Compulsory·Conflict·Capacity miss를 cache state와 history로 구분한다.

먼저 비유로 머릿속 구조 만들기

Cache는 번호가 붙은 작은 사물함입니다. direct-mapped는 각 번호에 물건 하나만 들어가서 같은 사물함 번호를 가진 다른 물건이 서로 밀어냅니다. set-associative는 한 번호 안에 여러 칸(way)이 있어 충돌을 줄입니다.

그림은 왼쪽에서 오른쪽으로 읽습니다. 각 화살표는 앞 단계의 결과가 다음 단계의 입력이 된다는 뜻입니다. 흐름도만 크게 열기

용어를 평범한 문장으로 바꾸기

독일어와 영어 용어를 소리만 외우지 말고, 아래 설명을 자신의 말로 다시 말해 보세요.

Hit / Miss: 찾는 block이 cache에 있음 / 없음
Block: cache가 memory에서 한 번에 가져오는 연속 Byte 묶음
Set / Way: block이 들어갈 후보 묶음 / 그 묶음 안의 칸
Tag: 같은 set으로 온 여러 memory block을 구분하는 상위 주소
AMAT: Average Memory Access Time, 확률을 반영한 평균 접근 시간

개념을 처음부터 연결하기

1. Bit 수 구하기

block이 8 Byte이면 offset은 3 bit, 4개 set이면 set index는 2 bit가 필요합니다. 16-bit 주소에서 나머지 11 bit가 tag입니다. 로그 계산은 아래 수식 블록에 따로 표시합니다.

2. 같은 block 알아보기

주소를 block size로 내림한 block base가 같으면 같은 block입니다. 0x0080과 0x0084는 모두 0x0080–0x0087 block에 있어 첫 접근 뒤 두 번째는 hit가 될 수 있습니다.

3. Miss type 판정

그 block을 처음 본다면 Compulsory입니다. 전에 봤지만 다른 block에 밀렸고 전체 cache에는 공간이 있었을 상황이면 Conflict입니다. cache 전체 용량 부족 때문에 밀렸다면 Capacity입니다.

이 챕터에서 계속 사용할 손풀이 표

아래 표는 정답표가 아니라 작업 기억을 외부에 꺼내 놓는 worksheet입니다. 소문제를 풀 때마다 빈 칸을 직접 채우세요.

Cache 접근 상태 worksheet
접근 전	이번 접근	접근 후
set/way의 현재 tag	주소·block base 계산	set/way 갱신
과거 방문 block 목록	tag·set·offset 분해	seen 목록 갱신
replacement 상태	Hit/Miss type 판정	다음 접근용 snapshot

수식은 위아래 구조로 읽기

평문으로 제곱과 분수를 이어 쓰면 구조를 놓치기 쉽습니다. 아래 수식은 브라우저의 MathML로 렌더되며, 지수·아래첨자·분수를 실제 수학 표기처럼 보여 줍니다.

2단계 cache의 AMAT

AMAT = T_{L 1} + {MR}_{L 1} \times (T_{L 2} + {MR}_{L 2} \times T_{Mem})

아래 단계의 비용은 바로 위 cache에서 miss가 났을 때만 지불합니다.

주소 field의 bit 수

b_{offset} = \log_{2} (BlockBytes), b_{set} = \log_{2} (SetCount)

8-byte block은 offset 3 bit, 4 sets는 set index 2 bit를 사용합니다.

작은 숫자로 한 번 직접 해보기

8-byte block, 4 sets에서 주소 0x009C: offset=0x009C mod 8=4, block number=0x009C//8, set=block number mod 4=3, tag=address//32=0x004입니다.

이 예제에서 중요한 것은 숫자 자체가 아니라, 어떤 값을 먼저 구하고 그 결과를 다음 계산에 넣는지입니다. 종이에 중간값을 생략하지 않고 적어 보세요.

초보자가 자주 멈추는 지점

주소가 다르면 무조건 다른 cache block인가요?

아닙니다. block size가 8 Byte면 0x80과 0x84는 같은 block입니다. 주소를 block boundary로 내린 값이 같은지 먼저 확인합니다.

전에 본 tag면 항상 hit인가요?

현재 해당 set의 way에 남아 있어야 hit입니다. history에만 있고 이미 교체됐다면 miss이며, history는 miss type을 정할 때 사용합니다.

AMAT에서 L2 시간을 항상 더하나요?

L2는 L1 miss일 때만 접근합니다. 따라서 L2 이하 비용 전체에 L1 miss rate를 곱해야 하며, memory도 L2 miss일 때만 발생합니다.

시험지에서 손으로 쓰는 순서

AMAT는 miss rate=1-hit rate로 바꾸고 안쪽 level부터 계산합니다.
trace 전 address sequence를 loop별로 먼저 펼칩니다.
각 주소의 block base, offset, set, tag를 계산합니다.
접근 직전 cache state와 전체 방문 history로 hit/miss type을 정합니다.
판정 직후 set/way 상태를 반드시 갱신합니다.

이 순서를 외우는 목적은 답을 암기하는 것이 아닙니다. 중간 과정을 답안지에 남겨 부분점수를 얻고, 어디에서 잘못됐는지 스스로 찾기 위한 체크포인트입니다.

26개 소문제로 개념 적용하기

각 소문제에는 이 장의 설명을 다시 포함한 독립 수업 페이지가 있습니다. 따라서 링크로 바로 들어가도 선행지식 없이 읽을 수 있습니다.

8a-1
기존 L1의 AMAT
L1 2 cycle/80%, L2 15 cycle/75%, memory 200 cycle의 AMAT를 계산하세요. · 4 micro-work
독립 수업 열기 →
8a-2
느리지만 잘 맞는 새 L1
L1이 4 cycle/90%가 되면 개선인지 비교하세요. · 4 micro-work
독립 수업 열기 →
8b-1
Direct-mapped Zugriff #1
Set 1에 Tag 0x0111가 접근합니다. Hit/Miss type을 판정하세요. · 4 micro-work
독립 수업 열기 →
8b-2
Direct-mapped Zugriff #2
Set 3에 Tag 0x0222가 접근합니다. Hit/Miss type을 판정하세요. · 4 micro-work
독립 수업 열기 →
8b-3
Direct-mapped Zugriff #3
Set 5에 Tag 0x0333가 접근합니다. Hit/Miss type을 판정하세요. · 4 micro-work
독립 수업 열기 →
8b-4
Direct-mapped Zugriff #4
Set 1에 Tag 0x0444가 접근합니다. Hit/Miss type을 판정하세요. · 4 micro-work
독립 수업 열기 →
8b-5
Direct-mapped Zugriff #5
Set 3에 Tag 0x0222가 접근합니다. Hit/Miss type을 판정하세요. · 4 micro-work
독립 수업 열기 →
8b-6
Direct-mapped Zugriff #6
Set 1에 Tag 0x0111가 접근합니다. Hit/Miss type을 판정하세요. · 4 micro-work
독립 수업 열기 →
8b-7
Direct-mapped Zugriff #7
Set 5에 Tag 0x0555가 접근합니다. Hit/Miss type을 판정하세요. · 4 micro-work
독립 수업 열기 →
8b-8
Direct-mapped Zugriff #8
Set 1에 Tag 0x0444가 접근합니다. Hit/Miss type을 판정하세요. · 4 micro-work
독립 수업 열기 →
8b-9
Direct-mapped Zugriff #9
Set 5에 Tag 0x0333가 접근합니다. Hit/Miss type을 판정하세요. · 4 micro-work
독립 수업 열기 →
8b-10
Direct-mapped Zugriff #10
Set 3에 Tag 0x0666가 접근합니다. Hit/Miss type을 판정하세요. · 4 micro-work
독립 수업 열기 →
8b-11
Direct-mapped Zugriff #11
Set 3에 Tag 0x0222가 접근합니다. Hit/Miss type을 판정하세요. · 4 micro-work
독립 수업 열기 →
8b-12
Direct-mapped Zugriff #12
Set 1에 Tag 0x0444가 접근합니다. Hit/Miss type을 판정하세요. · 4 micro-work
독립 수업 열기 →
8c-1
4-way Cache Zugriff #1
주소 0x0080의 Offset/Set/Tag와 Hit/Miss를 구하세요. · 5 micro-work
독립 수업 열기 →
8c-2
4-way Cache Zugriff #2
주소 0x0084의 Offset/Set/Tag와 Hit/Miss를 구하세요. · 5 micro-work
독립 수업 열기 →
8c-3
4-way Cache Zugriff #3
주소 0x0100의 Offset/Set/Tag와 Hit/Miss를 구하세요. · 5 micro-work
독립 수업 열기 →
8c-4
4-way Cache Zugriff #4
주소 0x0088의 Offset/Set/Tag와 Hit/Miss를 구하세요. · 5 micro-work
독립 수업 열기 →
8c-5
4-way Cache Zugriff #5
주소 0x008C의 Offset/Set/Tag와 Hit/Miss를 구하세요. · 5 micro-work
독립 수업 열기 →
8c-6
4-way Cache Zugriff #6
주소 0x0104의 Offset/Set/Tag와 Hit/Miss를 구하세요. · 5 micro-work
독립 수업 열기 →
8c-7
4-way Cache Zugriff #7
주소 0x0090의 Offset/Set/Tag와 Hit/Miss를 구하세요. · 5 micro-work
독립 수업 열기 →
8c-8
4-way Cache Zugriff #8
주소 0x0094의 Offset/Set/Tag와 Hit/Miss를 구하세요. · 5 micro-work
독립 수업 열기 →
8c-9
4-way Cache Zugriff #9
주소 0x0108의 Offset/Set/Tag와 Hit/Miss를 구하세요. · 5 micro-work
독립 수업 열기 →
8c-10
4-way Cache Zugriff #10
주소 0x0098의 Offset/Set/Tag와 Hit/Miss를 구하세요. · 5 micro-work
독립 수업 열기 →
8c-11
4-way Cache Zugriff #11
주소 0x009C의 Offset/Set/Tag와 Hit/Miss를 구하세요. · 5 micro-work
독립 수업 열기 →
8c-12
4-way Cache Zugriff #12
주소 0x010C의 Offset/Set/Tag와 Hit/Miss를 구하세요. · 5 micro-work
독립 수업 열기 →

출처

Source: Probeklausur.pdf / Probeklausur Musterlösung und Hinweise.pdf · 시험 p16–18 · 공식 해설 p41–44. 공식 답의 숫자와 course-specific datapath/FSM 가정은 변경하지 않았습니다.