Original German, Korean translation, method, source-grounded solution, recall-answer audit, wrong-answer explanations, active recall, and source citations are separated below.
No active weak-topic rows currently map to this Aufgabe.
Subproblem learning view
소문제별 1타 강사식 풀이 교실
문제를 읽은 직후 필요한 개념을 직관적으로 잡고, 같은 순서로 손풀이를 재현하도록 구성했습니다.
Teilaufgabe
8a
4 points
Original German
Folgende Hits und Misses in einem Programm:
Zugriff
1
2
3
4
5
6
7
8
9
10
Cache Status
Hit
Compulsory Miss
Hit
Capacity Miss
Hit
Hit
Hit
Hit
Hit
Conflict Miss
Cache Zugriff dauert 3 Zyklen und Hauptspeicherzugriff dauert 100 Zyklen. Berechne Miss Rate und AMAT (average memory access time).
Recall-Loesung: Miss Rate 3/10 = 0.3, AMAT 3 + 100 * 0.3 = 33 Zyklen.
한국어 문제
10번의 Speicherzugriff에 대해 Hit/Miss 종류가 주어진다. Cache 접근 시간은 3 Takte, Hauptspeicher 접근 시간은 100 Takte이다. Miss Rate와 AMAT, 즉 average memory access time을 구하라.
한 줄 핵심
miss rate = misses/accesses, AMAT = hit time + miss rate × miss penalty로 계산하고 단위를 cycle로 맞춘다.
0. 초보자 개념 다리
평균 대기시간은 매번 드는 hit time에 가끔 생기는 긴 miss penalty의 기대값을 더한 것이다.
1. 이 문제의 풀이 루틴
miss rate=misses/accesses를 구한다.
시간 단위를 통일한다.
AMAT=hit time+miss rate×miss penalty를 적용한다.
범위와 단위를 검산한다.
2. 왜 이 방법이 맞을까?
모든 access가 hit lookup 비용을 내고 miss 비율만큼 추가 penalty를 낸다.
3. 시험장 실수 방지
문제에서 miss time과 추가 miss penalty 중 무엇을 주었는지 확인한다.
최대 상세 해설 · 8a 깊이 학습: Miss Rate를 세고 AMAT를 단위까지 계산하기
이 강의의 도착점
Hit/Miss 기록에서 Miss의 종류와 무관하게 전체 Miss 수를 정확히 세고, 주어진 Cache-Zugriffszeit와 Hauptspeicher-Zeit를 현재 강의의 AMAT 식에 대입하여 Miss Rate와 평균 접근 시간을 독립적으로 계산한다.
0. 정말 아무것도 모른다면 여기서 시작
Cache 접근 하나의 결과는 Hit 또는 Miss다. Miss 앞에 Compulsory, Conflict, Capacity가 붙어도 모두 Miss 한 번으로 센다.
Miss Rate는 ‘Miss가 몇 번인가’를 ‘전체 Speicherzugriff가 몇 번인가’로 나눈 비율이다. Prozent로 쓸 때만 마지막에 100을 곱한다.
이 문제에서 사용하는 현재 강의식은 AMAT = Cache-Zugriffszeit + Miss Rate × Hauptspeicher-Zeit이다. 따라서 모든 접근이 먼저 부담하는 Cache 시간 3 Zyklen에 Miss일 때 추가되는 평균 비용을 더한다.
SoSe25 자료는 공식 Klausur나 공식 Musterlösung이 아니라 Gedächtnisprotokoll의 회상 재구성이다. 아래의 10개 상태와 3/100 Zyklen은 회상 문제에 적힌 값이며, 계산 과정은 현행 강의·Übung 자료로 다시 확인한 학습용 해설이다.
회상 원문의 표현만으로 100 Zyklen이 이미 Cache 확인 시간을 포함한 총 Miss-Zeit인지 모호하게 읽힐 수 있다. 이 자료는 현재 강의와 기존 Aufgabe-8 검증 기록이 채택한 ‘Cache 시간 뒤에 더해지는 Hauptspeicher 비용’ 해석을 명시적으로 사용한다.
1. 문제에 나오는 말부터 하나씩
Hit
요청한 Block이 Cache의 올바른 위치에 있고 Tag도 일치하여 Hauptspeicher까지 갈 필요가 없는 접근이다.
Miss
요청한 Block이 Cache에 없어 Hauptspeicher 계층에서 가져와야 하는 접근이다. Compulsory, Conflict, Capacity는 Miss의 원인을 더 자세히 나눈 이름이다.
Miss Rate
Anzahl Misses / Anzahl Zugriffe로 계산하는 Miss 비율이다.
Hit Rate
Anzahl Hits / Anzahl Zugriffe이며 Hit와 Miss만 가능하면 1 - Miss Rate와 같다.
AMAT
Average Memory Access Time, 즉 여러 Speicherzugriff에 걸친 평균 접근 시간이다.
Cache-Zugriffszeit
Cache가 Hit인지 확인하고 데이터를 읽는 데 필요한 기본 시간이다. 이 재구성 문제에서는 3 Zyklen이다.
Miss penalty
Miss 때문에 기본 Cache 접근 외에 추가로 부담하는 시간이다. 이 해설에서는 주어진 Hauptspeicher-Zeit 100 Zyklen을 이 추가 비용으로 사용한다.
Compulsory Miss
해당 Speicherblock을 처음 요청하여 발생하는 Miss다. Miss Rate를 셀 때는 다른 Miss 종류와 똑같이 한 번으로 센다.
Conflict Miss
총 용량은 충분하지만 mapping 또는 제한된 associativity 때문에 필요한 Block이 밀려나 발생하는 Miss다.
Capacity Miss
Cache 전체 용량이 working set을 담기에 부족하여 발생하는 Miss다.
2. 선생님과 같이 한 칸씩 푸는 과정
먼저 표의 열 개 접근에 번호 1부터 10까지 붙인다. 분모는 이미 10 Zugriffe로 확정된다.
Miss라는 단어가 붙은 열만 표시한다. #2는 Compulsory Miss, #4는 Capacity Miss, #10은 Conflict Miss다.
세 종류의 원인은 다르지만 모두 Miss이므로 분자는 3 Misses다. 나머지 일곱 접근은 Hit다.
Miss Rate를 분수로 쓰면 3/10이다. 소수로는 0.3, Prozent로는 30%다.
따라서 이 재구성과 현재 강의식에 따른 답은 Miss Rate = 30%, AMAT = 33 Zyklen이다. 이는 공식 SoSe25 Musterlösung이 아니라, Gedächtnisprotokoll의 입력값을 현행 자료의 공식으로 감사한 학습용 결과다.
4. 이제 정확한 개념으로 한 단계 더 깊게
Miss Rate를 구할 때 Miss의 원인은 가중치에 영향을 주지 않는다. 문제에서 종류별로 서로 다른 penalty를 따로 주지 않는 한 Compulsory, Conflict, Capacity Miss를 모두 같은 Miss로 센다.
AMAT 식에서 Miss Rate는 반드시 0.3과 같은 무차원 비율이어야 한다. 30%를 계산기에 넣을 때는 0.30으로 변환해야 한다.
t_cache + m × penalty 형태는 모든 접근에서 Cache 조회가 먼저 일어나고, Miss 비율만큼 추가 비용을 낸다는 기대값 계산이다.
문헌에 따라 Miss penalty와 Miss time의 정의가 다를 수 있다. 그래서 시험에서는 식을 먼저 적고 주어진 시간값을 어느 항으로 해석했는지 드러내는 것이 안전하다.
이 재구성 해설의 33 Zyklen은 100 Zyklen을 Cache 조회 후 추가 Hauptspeicher 비용으로 해석한다. 이는 기존 SoSe25 Aufgabe-8 검증 기록 및 현재 학습자료의 해석과 일치한다.
Hit Rate는 필수 답이 아니어도 강력한 검산 도구다. Hit 수와 Miss 수의 합이 전체 접근 수와 맞지 않으면 AMAT 이전에 개수부터 고쳐야 한다.
평균 시간은 개별 Hit 시간보다 작을 수 없다. 이 문제에서 33은 기본 3보다 크고, 모든 접근이 Miss일 때의 3 + 100보다 작으므로 범위 검산을 통과한다.
5. 시험장에서 그대로 쓰는 단계별 풀이
표에서 전체 접근 수 N=10을 적는다.
이름에 Miss가 들어가는 접근 #2, #4, #10을 표시하고 M=3을 적는다.
Miss Rate = M/N = 3/10 = 0.3 = 30%를 계산한다.
선택 검산으로 Hit Rate = 7/10 = 70%와 합 100%를 확인한다.
단위를 포함한 AMAT 식 3 Zyklen + 0.3 × 100 Zyklen을 쓴다.
곱셈을 먼저 계산해 추가 평균 비용 30 Zyklen을 얻는다.
최종값 33 Zyklen과 사용한 시간 해석을 한 문장으로 명시한다.
6. 예시와 변형 문제 연결
원문 표의 #2, #4, #10만 다시 색칠한다고 생각하면 종류 이름에 흔들리지 않는다. 세 칸 모두 Miss이므로 M=3이고 나머지 일곱 칸은 Hit다.
기대값 관점으로 같은 계산을 말하면, 매 접근마다 3 Zyklen을 지불하고 열 번 중 평균 30%에서만 추가 100 Zyklen을 지불한다. 따라서 평균 추가 비용은 30 Zyklen이다.
경계값 검산: Miss Rate가 0이라면 같은 식은 3 Zyklen을, Miss Rate가 1이라면 103 Zyklen을 준다. 이 문제의 0.3은 그 사이이므로 33 Zyklen도 두 경계 사이에 있어야 한다.
표의 Capacity Miss 한 번을 실수로 빼면 2/10이 된다. 그러나 ‘Miss 종류를 모두 센다’는 규칙에 어긋나며, 표에 적힌 세 Miss 칸과도 맞지 않는다.
7. 독일어 만점 답안 템플릿
Es gibt 10 Speicherzugriffe und drei Misses (#2, #4 und #10). Daher beträgt die Miss Rate 3/10 = 0,3 = 30 %. Mit der hier verwendeten Formel AMAT = t_Cache + Miss Rate · t_Hauptspeicher ergibt sich AMAT = 3 + 0,3 · 100 = 33 Zyklen. Die Rechnung verwendet die im Gedächtnisprotokoll rekonstruierten Werte und ist keine offizielle SoSe25-Musterlösung.
8. 자주 나오는 오답과 교정
Compulsory Miss만 세기: Miss Rate에는 #2뿐 아니라 Capacity Miss #4와 Conflict Miss #10도 들어간다.
Hit 일곱 번을 분자로 사용해 70%를 Miss Rate라고 쓰기: 70%는 Hit Rate다.
30%를 식에 숫자 30으로 넣기: Prozent를 소수 0.3으로 바꿔야 한다.
3 × 0.3 + 100으로 계산하기: 현재 강의식에서는 3 Zyklen이 모든 접근의 기본 시간이고 100 Zyklen이 Miss일 때의 추가 비용이다.
단위를 생략하기: Rate에는 단위가 없지만 AMAT 결과에는 Zyklen이 필요하다.
Miss 종류마다 다른 시간이 든다고 임의로 가정하기: 문제는 종류별 penalty를 따로 주지 않는다.
33 Zyklen을 공식 SoSe25 정답이라고 단정하기: 원본은 Gedächtnisprotokoll이며 공식 Klausur/Lösung이 아니다.
시간 표현의 해석을 숨기기: recall 문구가 모호할 수 있으므로 사용한 t_cache + m·t_memory 해석을 식으로 명시한다.
9. 답을 보지 않고 확인하기
이 표에서 전체 Zugriff 수와 Miss 수는 각각 얼마인가?
Compulsory, Capacity, Conflict Miss는 Miss Rate에서 서로 다르게 세는가?
3/10을 소수와 Prozent로 각각 어떻게 쓰는가?
이 해설에서 사용하는 AMAT 식과 각 항의 단위는 무엇인가?
Miss 때문에 평균적으로 추가되는 시간은 몇 Zyklen인가?
최종 AMAT가 3보다 크고 103보다 작은 이유는 무엇인가?
왜 33 Zyklen을 공식 SoSe25 Musterlösung이라고 부르면 안 되는가?
확인문제 정답 보기
전체는 10 Zugriff이고, Miss는 #2, #4, #10의 세 번이다.
아니다. 종류는 원인을 구분하지만 이 문제의 Miss Rate에서는 각각 한 번의 Miss로 동일하게 센다.
3/10 = 0.3 = 30%다.
AMAT = t_cache + Miss Rate × t_Hauptspeicher이며 시간 항과 결과의 단위는 Zyklen, Miss Rate는 무차원이다.
0.3 × 100 Zyklen = 30 Zyklen이다.
Miss Rate 0이면 3 Zyklen, 1이면 103 Zyklen이고 이 문제의 Miss Rate 0.3은 그 사이이기 때문이다.
문제와 수치의 출처가 공식 시험·공식 해답이 아니라 Gedächtnisprotokoll의 회상 재구성이기 때문이다.
Interactive practice
AMAT calculator
access/miss/hit time/miss penalty를 입력해 miss rate와 AMAT를 계산하세요.
Die Daten werden in einem 2-way set associative Cache mit 4 Sets, einer Blockgroesse von einem Wort und einer Adressbreite von 16 Bit eingetragen. Trage in die Tabelle Tags, Set-Index und Byte-Offset ein.
Normalisierungsnotiz: addi t2, t2 -1 ist syntaktisch unvollstaendig; gemeint ist addi t2, t2, -1. Die Schleife laeuft wegen t2 = 4 viermal und erzeugt acht Datenzugriffe, jeweils lb, dann lw.
한국어 문제
주어진 RISC-V 코드에서 실제로 실행되는 lb와 lw의 Datenadresse를 순서대로 구한다. 그 주소들을 16-bit Adresse로 보고, 2-way set associative Cache, 4 Sets, Blockgroesse 1 Wort 조건에서 Tag, Set-Index, Byte-Offset으로 나누어 표를 채워라.
한 줄 핵심
address를 Tag | Set-Index | Byte-Offset으로 bit 단위 분해한다. block size와 set 수에서 각 bit 수를 먼저 구한다.
0. 초보자 개념 다리
주소는 어느 단지(Tag)·몇 동(Set)·집 안 어느 칸(Offset)인지로 나뉜다.
1. 이 문제의 풀이 루틴
offset bits=log2(block bytes)를 구한다.
sets=capacity/(block bytes×ways), index bits=log2(sets)를 구한다.
남은 상위 bits를 Tag로 둔다.
주소별 set/tag와 way·LRU를 갱신한다.
2. 왜 이 방법이 맞을까?
하위 bits는 block 내부, 그 위 bits는 set 선택, 상위 bits는 block 식별에 쓰인다.
3. 시험장 실수 방지
1 Wort를 1 byte로 보지 않는다. RV32 word는 보통 4 bytes다.
최대 상세 해설 · 8b 깊이 학습: 동적 주소를 만든 뒤 2-way Cache의 Tag·Set·Offset 자르기
이 강의의 도착점
RISC-V Schleife에서 실제 lb/lw Datenadresse 여덟 개를 실행 순서대로 추적하고, 16-bit Byte-Adresse를 2-way set associative Cache의 12-bit Tag, 2-bit Set-Index, 2-bit Byte-Offset으로 일관되게 분해한다.
0. 정말 아무것도 모른다면 여기서 시작
이 문제는 두 단계다. 먼저 코드가 만드는 실제 주소를 구하고, 그 다음 각 주소를 Cache field로 나눈다. 두 단계를 섞으면 register update 시점을 놓치기 쉽다.
Data Cache 접근으로 세는 instruction은 여기서 lb와 lw뿐이다. li, addi, bne은 이 표의 Datenzugriff가 아니다.
RISC-V 주소는 Byte-Adresse다. 1 Wort = 4 Byte이므로 Block 안에서 byte 하나를 고르려면 가장 낮은 2 Bit가 Byte-Offset이어야 한다.
4 Sets = 2^2이므로 그 다음 2 Bit가 Set-Index다. 16-bit Adresse에서 남은 16-2-2=12 Bit가 Tag다.
2-way는 한 Set 안에 두 자리가 있다는 뜻이다. 어느 Way를 쓸지는 주소에 들어 있지 않으며, Tag/Set/Offset field 폭을 계산할 때 Way bit를 추가하면 안 된다.
SoSe25 원문은 공식 Klausur가 아닌 Gedächtnisprotokoll이다. 아래 코드, 주소열, Cache 조건은 recall 재구성을 현행 Übung 11/12와 Vorlesung Teil 3의 주소 분해 규칙으로 다시 확인한 것이며 공식 채점표가 아니다.
회상 코드의 addi t2, t2 -1은 쉼표가 빠진 불완전한 표기다. 기존 검증 자료와 이 해설은 의도된 명령을 addi t2, t2, -1로 정규화하고 정확히 네 번 반복한다고 명시한다.
1. 문제에 나오는 말부터 하나씩
effektive Adresse
Load/Store가 실제로 접근하는 주소다. lb t4,0x8(t0)에서는 현재 t0 + 0x8, lw t5,0x0(t1)에서는 현재 t1 + 0이다.
Byte-Adresse
주소 하나가 Byte 하나를 가리키는 방식이다. 그래서 4-Byte Block에는 네 Byte 위치를 고르는 2 offset bits가 필요하다.
Block
Cache와 Hauptspeicher 사이에서 함께 이동하는 연속된 Byte 묶음이다. 이 문제의 한 Block은 한 32-bit Wort, 즉 4 Byte다.
Byte-Offset
선택된 Block 내부에서 몇 번째 Byte인지를 나타내는 최하위 bit field다.
Set-Index
Cache의 여러 Set 중 어느 Set을 검사할지 고르는 주소 field다.
Tag
같은 Set으로 mapping되는 여러 Hauptspeicher Block을 서로 구별하는 주소의 상위 field다.
2-way set associative
각 주소는 한 Set으로 mapping되지만 그 Set 안의 두 Way 중 하나에 저장될 수 있는 Cache 조직이다.
Way
한 Set 안의 저장 자리다. Way 선택은 Cache 내부 비교·교체 문제이며 주소 field가 아니다.
alignment
여러 Byte를 읽는 접근이 알맞은 주소 경계에 놓이는 조건이다. 이 문제의 lw 주소들은 모두 4의 배수여서 offset 0이다.
shift와 mask
주소 field를 안전하게 추출하는 연산이다. 이 문제에서는 tag=addr>>4, set=(addr>>2)&3, offset=addr&3을 쓴다.
2. 선생님과 같이 한 칸씩 푸는 과정
초기값을 적는다: t0=0x120, t1=0x300, t2=4. 각 iteration에서 두 load를 먼저 실행한 뒤 t0+=3, t1+=8, t2-=1을 수행한다.
Iteration 1의 lb 주소는 0x120+0x8=0x128, 이어지는 lw 주소는 0x300이다. 그 뒤 register는 t0=0x123, t1=0x308, t2=3이 된다.
Iteration 2의 주소는 0x123+0x8=0x12B, 이어서 0x308이다. update 뒤에는 t0=0x126, t1=0x310, t2=2다.
Iteration 3의 주소는 0x126+0x8=0x12E, 이어서 0x310이다. update 뒤에는 t0=0x129, t1=0x318, t2=1이다.
Iteration 4의 주소는 0x129+0x8=0x131, 이어서 0x318이다. update 뒤 t2=0이므로 loop가 끝난다.
따라서 프로그램 순서의 여덟 주소는 0x128, 0x300, 0x12B, 0x308, 0x12E, 0x310, 0x131, 0x318이다. lb 네 개만 먼저 쓰고 lw 네 개를 나중에 쓰면 실행 순서를 잃는다.
이제 field 폭을 고정한다. Block 4 Byte이므로 offset 2 Bit, 4 Sets이므로 set 2 Bit, 16-bit Adresse이므로 tag 12 Bit다. 모양은 Tag[15:4] | Set[3:2] | Offset[1:0]이다.
1 Wort = 4 Byte -> Byte-Offset = 2 Bit
4 Sets -> Set-Index = 2 Bit
16-bit Adresse -> Tag = 12 Bit
Tag = address >> 4
Set = (address >> 2) & 0x3
Offset = address & 0x3
Zugriff
Adresse
Tag
Set
Byte-Offset
#1
0x128
0x12
2
0
#2
0x300
0x30
0
0
#3
0x12B
0x12
2
3
#4
0x308
0x30
2
0
#5
0x12E
0x12
3
2
#6
0x310
0x31
0
0
#7
0x131
0x13
0
1
#8
0x318
0x31
2
0
2-way는 각 Set의 Way 수이며 주소에 별도의 Way field를 만들지 않는다. 이 표는 recall 문제를 현재 주소 분해 규칙으로 독립 검산한 결과이지 공식 SoSe25 Musterlösung의 전사가 아니다.
4. 이제 정확한 개념으로 한 단계 더 깊게
주소 생성과 주소 분해는 별도 작업이다. base+immediate와 loop update로 effektive Adresse를 먼저 확정해야 그 뒤의 Tag/Set/Offset도 맞는다.
Block 크기는 Byte 단위로 바꿔야 한다. 1 Wort가 offset 0 Bit라는 뜻이 아니라, 32-bit Wort라면 4 Byte이므로 offset 2 Bit다.
Set 수가 4라서 필요한 index는 2 Bit다. Associativity 2-way는 각 Set 안의 비교 가능한 Tag가 둘이라는 뜻이지 Set 수를 8로 바꾸는 뜻이 아니다.
주소 field 폭의 합은 전체 주소 폭과 같아야 한다. 이 문제에서는 12+2+2=16이다.
같은 Block 안의 주소는 Tag와 Set이 같고 Offset만 다르다. 0x128과 0x12B는 이 규칙을 보여 주는 가장 좋은 검산 쌍이다.
같은 Tag라고 같은 Cache 위치인 것은 아니다. 0x300과 0x308은 Tag가 0x30으로 같지만 Set이 각각 0과 2다.
lb는 byte 하나를 읽으므로 offset 1,2,3도 자연스럽다. 반면 이 문제의 lw 주소들은 4-Byte 정렬이라 offset 0이다.
Tag를 12 Bit로 쓴다고 반드시 세 자리 hex의 leading zero를 표에 써야 하는 것은 아니다. 예를 들어 0x012와 0x12는 같은 tag 값이지만 표기 형식은 일관되게 유지해야 한다.
Field 계산만 묻는 문제에는 replacement policy가 필요 없다. Hit/Miss 및 final state는 초기 cache state와 LRU 같은 policy가 주어진 경우에만 유일하게 결정된다.
5. 시험장에서 그대로 쓰는 단계별 풀이
loop 표에 각 iteration 시작 시점의 t0, t1, t2를 적는다.
각 행에서 lb: t0+0x8, 이어서 lw: t1을 계산하고 실행 순서대로 주소를 기록한다.
두 load를 기록한 다음에만 t0+=3, t1+=8, t2-=1을 적용한다.
t2가 0이 될 때까지 네 iteration, 여덟 Datenzugriff가 있는지 확인한다.
4 Byte -> 2 offset bits, 4 Sets -> 2 set bits, 16-2-2 -> 12 tag bits를 먼저 적는다.
각 주소에 tag=addr>>4, set=(addr>>2)&3, offset=addr&3을 같은 순서로 적용한다.
0x128/0x12B의 same-block 관계와 모든 lw의 offset 0으로 표를 검산한다.
요구되지 않은 cache replacement 결과는 쓰지 않고, 필요하면 초기 상태와 policy가 추가로 필요하다고 명시한다.
6. 예시와 변형 문제 연결
0x12B의 마지막 hex digit B는 binary 1011이다. 아래 2 Bit 11이 offset 3이고 그 위 2 Bit 10이 set 2다. 마지막 hex digit 전체를 Set으로 읽으면 안 된다.
0x128과 0x12B는 주소 차이가 3 Byte이고 둘 다 0x128..0x12B Block 안에 있다. 따라서 둘의 Tag 0x12와 Set 2는 같고 Offset만 0과 3으로 다르다.
0x310은 0x310>>4=0x31, (0x310>>2)&3=0, 0x310&3=0이므로 (0x31,0,0)이다. shift/mask 순서가 한 행 전체를 기계적으로 만든다.
2-way를 보고 Way bit 하나를 주소에 추가하면 field 합이 17 Bit가 되거나 Set 폭을 잘못 줄이게 된다. 주소는 Set까지만 고르고 두 Way의 Tag를 병렬 비교한다.
원문 addi t2, t2 -1을 그대로 유효한 assembly라고 가정하면 parsing 단계가 깨진다. 이 학습 자료는 recall의 누락된 쉼표를 명시적으로 보정한 addi t2,t2,-1을 사용한다.
7. 독일어 만점 답안 템플릿
Die Schleife läuft nach der Normalisierung zu addi t2,t2,-1 viermal. Die Datenadressen lauten in Ausführungsreihenfolge 0x128, 0x300, 0x12B, 0x308, 0x12E, 0x310, 0x131, 0x318. Ein Wort umfasst 4 Byte, also gibt es 2 Offset-Bits; 4 Sets benötigen 2 Set-Bits; damit bleiben bei 16 Bit 12 Tag-Bits. Mit Tag=Adresse>>4, Set=(Adresse>>2)&3 und Offset=Adresse&3 erhält man: (0x12,2,0), (0x30,0,0), (0x12,2,3), (0x30,2,0), (0x12,3,2), (0x31,0,0), (0x13,0,1), (0x31,2,0). Die 2-way-Assoziativität erzeugt kein zusätzliches Adressfeld.
8. 자주 나오는 오답과 교정
각 iteration의 lb 네 개를 먼저 나열하고 lw를 나중에 나열하기: 실제 실행 순서는 매 iteration마다 lb, lw다.
load 전에 t0+=3 또는 t1+=8을 적용하기: register update는 두 load 뒤에 일어난다.
lb만 Datenzugriff라고 세거나 lw만 세기: loop마다 두 load가 있어 총 여덟 접근이다.
1 Wort를 1 Byte로 보고 offset 0 Bit라고 쓰기: 여기서 한 Wort는 4 Byte이므로 offset은 2 Bit다.
2-way 때문에 주소에 Way bit가 있다고 쓰기: Way는 Cache 내부 선택이며 주소 field가 아니다.
마지막 hex digit를 통째로 Set이라고 읽기: Set과 Offset이 같은 hex digit 안의 각 2 Bit를 나눠 쓴다.
0x12B의 offset을 0으로 만들기: lb는 byte 접근이고 이 주소의 offset은 3이다.
Tag/Set/Offset만 묻는데 임의 LRU 상태를 공식 답처럼 추가하기: replacement 결과에는 별도 초기 상태와 policy 가정이 필요하다.
회상 코드의 쉼표 누락을 말없이 수정하기: addi t2,t2,-1로 정규화했다는 사실을 밝혀야 한다.
재구성 표를 공식 시험 정답으로 단정하기: 현행 자료로 계산은 검증했지만 SoSe25 원본과 공식 Lösung은 없다.
9. 답을 보지 않고 확인하기
이 loop에는 몇 iteration과 몇 Datenzugriff가 있는가?
첫 두 iteration의 lb, lw 주소를 실행 순서대로 쓰면 무엇인가?
Blockgroesse 1 Wort가 왜 2 Byte-Offset bits를 요구하는가?
4 Sets과 16-bit Adresse에서 Set과 Tag는 각각 몇 Bit인가?
0x12B의 Tag, Set, Byte-Offset은 무엇인가?
0x128과 0x12B의 Tag와 Set이 같은 이유는 무엇인가?
2-way가 주소에 Way bit 하나를 추가하지 않는 이유는 무엇인가?
여덟 주소 중 lb의 offset 열과 lw의 offset 열은 각각 무엇인가?
8b의 field 표만 계산할 때 replacement policy가 필요하지 않은 이유는 무엇인가?
확인문제 정답 보기
t2=4에서 시작해 네 iteration이며, iteration마다 lb와 lw가 하나씩 있어 여덟 Datenzugriff다.
0x128, 0x300, 0x12B, 0x308이다.
주소가 Byte-Adresse이고 한 32-bit Wort가 4 Byte이므로 Block 안 네 위치를 고르는 log2(4)=2 Bit가 필요하다.
Set은 log2(4)=2 Bit, Tag는 16-2-2=12 Bit다.
Tag 0x12, Set 2, Byte-Offset 3이다.
둘 다 같은 4-Byte Block 0x128..0x12B에 속하므로 상위 Tag/Set field가 같고 내부 byte 위치만 다르다.
주소는 하나의 Set을 고르고, 그 Set 안 두 Way의 Tag를 Cache가 병렬 비교하기 때문이다.
lb는 0,3,2,1, lw는 모두 0이다.
Tag/Set/Offset은 주소와 Cache geometry만으로 정해진다. 교체는 실제 state를 추적할 때만 필요하다.
Interactive practice
Tag | Set | Offset splitter
주소를 선택해 16-bit field와 2-way cache 위치를 확인하세요.
Teilaufgabe
8c
4 points
Original German
Fuehre diese Speicherzugriffe nun in einem Direct-Mapped Cache mit 8 Bloecken und einer Blockgroesse von einem Wort aus. Tag und Set sind gegeben. Sage, um welche Art Miss es sich handelt: Compulsory, Conflict oder Capacity.
Zugriff
#1
#2
#3
#4
#5
Tag
0x0FFE
0x0004
0x0FFE
0x0009
0x0FFE
Set
4
6
4
6
7
Hit/Miss Typ
Compulsory Miss
Compulsory Miss
Zugriff
#6
#7
#8
#9
#10
Tag
0x0004
0x0009
0x0009
0x0FFE
0x0FFE
Set
6
4
6
4
7
Hit/Miss Typ
Normalisierungsnotiz: Im Recall steht Cumpolsory; gemeint ist Compulsory.
한국어 문제
이번에는 Direct-Mapped Cache, 8 Blocks, Blockgroesse 1 Wort에서 주어진 Tag/Set 순서대로 접근한다. 각 접근이 Hit인지, Miss라면 Compulsory Miss, Conflict Miss, Capacity Miss 중 무엇인지 분류하라.
한 줄 핵심
각 block의 첫 접근은 compulsory miss다. 이미 본 block의 eviction은 전체 용량과 mapping을 비교해 conflict/capacity로 구분한다.
0. 초보자 개념 다리
Direct-mapped Cache는 각 block이 놓일 line이 하나뿐이라 같은 line을 요구하면 서로 밀어낸다.
1. 이 문제의 풀이 루틴
address를 block number로 바꾼다.
index=block mod lines, tag=block div lines를 구한다.
valid/tag 비교 후 cache를 갱신한다.
첫 접근은 compulsory로 둔다.
재접근 miss는 fully-associative 기준과 비교해 conflict/capacity를 가른다.
2. 왜 이 방법이 맞을까?
miss 종류는 mapping 제한을 없앴을 때도 miss인지로 구분한다.
3. 시험장 실수 방지
eviction된 모든 재접근을 capacity miss라고 하지 않는다.
최대 상세 해설 · 8c 깊이 학습: Direct-Mapped Cache를 한 줄씩 추적해 Hit와 3C Miss 분류하기
이 강의의 도착점
비어 있는 8-Block Direct-Mapped Cache에서 주어진 (Tag, Set) 열을 순서대로 적용하고, valid/tag 비교와 ‘이 Block을 전에 본 적 있는가’ 기록을 분리하여 Hit, Compulsory Miss, Conflict Miss를 판정하며 Capacity Miss가 없는 이유를 설명한다.
0. 정말 아무것도 모른다면 여기서 시작
Direct-mapped Cache에서는 각 Set에 자리가 정확히 하나뿐이다. 어떤 주소가 Set 6으로 가면 Set 6의 현재 Tag 하나와만 비교한다.
Hit의 조건은 두 개다: 그 Set의 valid bit가 1이고 저장된 Tag가 요청 Tag와 같아야 한다. Set 번호만 같다고 Hit가 아니다.
Compulsory Miss를 판단하려면 Cache 현재 상태와 별도로 ‘이 정확한 memory Block을 과거에 한 번이라도 요청했는가’를 기록해야 한다. 이 문제에서는 주어진 (Tag, Set) 쌍을 Block 식별자로 사용한다.
전에 본 Block인데 현재 mapped Set에 없다면 Conflict와 Capacity를 구분한다. 같은 총 용량의 fully associative Cache라면 남아 있을 수 있었는지를 생각한다.
이 재구성 trace에는 서로 다른 Block이 다섯 개뿐이고 Cache 전체는 여덟 Block을 담는다. 따라서 반복 Block의 Miss는 총 용량 부족이 아니라 direct mapping 충돌에 의한 Conflict Miss다.
아래 분류는 Cache가 처음에 비어 있다는 기존 Aufgabe-8 재구성의 조건을 사용한다. 초기 내용이 주어지지 않는 다른 문제에서는 첫 접근의 Hit/Miss를 임의로 정할 수 없으므로 반드시 조건을 확인해야 한다.
SoSe25의 표와 recall 답은 공식 Klausur 또는 공식 Lösung이 아니다. 여기서는 Gedächtnisprotokoll의 Tag/Set 열을 현행 Übung 11/12의 valid/tag trace와 3C 분류 규칙으로 다시 검산한다.
1. 문제에 나오는 말부터 하나씩
Direct-Mapped Cache
각 memory Block이 정확히 하나의 Set으로 mapping되고, 각 Set에는 Way가 하나뿐인 Cache다.
Valid-Bit
해당 Cache entry의 Tag/Data가 실제로 유효한지를 나타낸다. 초기 empty Cache의 모든 valid bit는 0이다.
서로 다른 Block은 (0x0FFE,4), (0x0004,6), (0x0009,6), (0x0FFE,7), (0x0009,4)의 다섯 개이고 Cache 용량은 여덟 Block이다. 따라서 Capacity Miss는 없으며 #6, #8, #9는 mapping 충돌에 의한 Conflict Miss다. 이 결과는 recall 표를 현행 규칙으로 검산한 학습용 답이며 공식 SoSe25 Musterlösung은 아니다.
4. 이제 정확한 개념으로 한 단계 더 깊게
Cache 현재 상태와 과거 방문 기록은 서로 다르다. 현재 없더라도 과거에 본 Block이면 Compulsory가 아니며, 과거에 처음이라면 기존 entry를 교체하더라도 Compulsory다.
같은 Tag만으로 같은 Block이라고 판단할 수 없다. #1의 (0x0FFE,4)와 #5의 (0x0FFE,7)은 Set이 다르므로 서로 다른 Block이다.
같은 Set만으로 Hit라고 판단할 수도 없다. #4는 Set 6이 valid이지만 저장 Tag 0x0004와 요청 Tag 0x0009가 달라 Miss다.
Direct-mapped에서는 replacement policy를 선택하지 않는다. 새 Tag가 같은 Set에 오면 기존 Tag를 반드시 교체한다.
처음 보는 Block이 occupied Set에 들어오며 기존 Block을 밀어내도 그 첫 접근의 종류는 Compulsory Miss다. #4와 #7이 그 예다.
Conflict Miss는 ‘전에 본 Block’이라는 조건과 ‘총 용량이 충분했다’는 조건을 함께 확인한다. 단순히 eviction이 있었다는 이유만으로 Conflict라고 부르지 않는다.
Capacity Miss는 현재 direct-mapped state만 보고 판정하지 않는다. 같은 크기의 fully associative Cache에서도 Block이 사라졌을지를 비교해야 한다.
이 trace의 다섯 distinct blocks는 8-block capacity보다 적으므로 fully associative Cache에서는 모두 유지할 수 있다. 반복 Miss 세 번은 모두 mapping이 만든 Conflict다.
분류 개수 검산은 유용하다. 이 문제에서는 5 Compulsory + 3 Conflict + 0 Capacity + 2 Hit = 10 Zugriffe다.
초기 Cache state는 결과에 영향을 준다. 이 해설은 기존 재구성처럼 empty start를 명시했으며, 알려지지 않은 초기 Tag를 임의로 만들지 않는다.
5. 시험장에서 그대로 쓰는 단계별 풀이
각 Set에 valid와 tag 한 칸을 그려 Direct-Mapped 상태표를 만든다.
현재 Cache와 별도로 지금까지 본 (Tag,Set) 쌍의 seen 목록을 만든다.
각 접근에서 먼저 mapped Set의 valid/tag를 비교해 Hit인지 Miss인지 판정한다.
seen에 있다면 같은 용량의 fully associative Cache에서도 사라졌을지 판단해 Conflict와 Capacity를 구분한다.
Miss 뒤에는 해당 Set의 기존 Tag를 요청 Tag로 교체하고 valid를 1로 만든다.
Hit 뒤에는 Direct-Mapped tag 상태를 바꾸지 않는다.
마지막에 distinct block 수 5와 전체 capacity 8을 비교하고, 분류 개수 합이 10인지 검산한다.
6. 예시와 변형 문제 연결
#4는 Set 6에서 기존 0x0004를 밀어내지만 (0x0009,6)의 첫 접근이므로 Compulsory Miss다. ‘교체가 발생했다’와 ‘Conflict Miss다’는 같은 말이 아니다.
#5의 요청 Tag 0x0FFE는 #1에서 본 것처럼 보이지만 Set 7과 Set 4는 다른 주소 field다. exact pair (0x0FFE,7)은 처음이므로 Compulsory Miss다.
#6은 #2의 (0x0004,6)을 다시 요청한다. #4가 동일 Set에 0x0009를 넣어 밀어냈고 전체 다섯 Block은 용량 8에 들어가므로 Conflict Miss다.
#10은 (0x0FFE,7)을 #5에서 넣은 뒤 Set 7에 다른 Tag가 한 번도 들어오지 않았다. valid와 tag가 모두 맞아 Hit다.
만약 distinct block 수만 세고 모든 재접근을 Hit라고 하면 mapping을 무시한 것이다. Direct-Mapped Cache는 빈 다른 Set이 남아 있어도 Set 4나 Set 6의 충돌을 피할 수 없다.
7. 독일어 만점 답안 템플릿
Ich simuliere den anfangs leeren Direct-Mapped Cache setweise und vergleiche jeweils Valid-Bit und Tag. Die Zugriffe ergeben der Reihe nach: Compulsory Miss, Compulsory Miss, Hit, Compulsory Miss, Compulsory Miss, Conflict Miss, Compulsory Miss, Conflict Miss, Conflict Miss, Hit. Die wiederholten Misses #6, #8 und #9 sind Conflict Misses: Es kommen nur fünf verschiedene (Tag,Set)-Blöcke vor, während der Cache acht Blöcke aufnehmen kann; bei voller Assoziativität wäre die Kapazität ausreichend. Eine Capacity Miss tritt daher nicht auf. Die Einordnung bezieht sich auf die rekonstruierte Recall-Aufgabe, nicht auf eine offizielle SoSe25-Musterlösung.
8. 자주 나오는 오답과 교정
Set 번호가 같으면 Hit라고 쓰기: valid bit와 Tag가 모두 일치해야 한다.
Tag가 같으면 같은 Block이라고 쓰기: 이 표에서는 Tag와 Set의 쌍이 Block을 식별한다.
현재 Cache에 없는 모든 Block을 Compulsory라고 쓰기: 과거에 본 적이 있는지도 별도로 확인해야 한다.
새 Block이 기존 Block을 교체하면 곧바로 Conflict Miss라고 쓰기: 새 Block의 첫 접근인 #4와 #7은 Compulsory Miss다.
eviction이 있었으므로 Capacity Miss라고 쓰기: 전체 용량과 fully associative 비교가 필요하다.
#6을 Capacity Miss로 분류하기: 다섯 distinct blocks는 여덟 Block 용량 안에 들어가며, 같은 Set 6 충돌이 원인이다.
#5를 Hit로 분류하기: 같은 Tag 0x0FFE라도 Set 7의 exact Block은 처음 요청된다.
#10 전에 Set 7도 다른 접근이 바꿨다고 착각하기: #6~#9는 Set 4 또는 6만 사용하므로 Set 7의 0x0FFE가 남는다.
Direct-Mapped trace에 LRU를 적용하기: Set마다 Way가 하나라 replacement 선택이 없다.
초기 Cache 내용을 임의로 가정하고 숨기기: 이 해설은 empty start를 명시하며 다른 초기 상태에서는 결과가 달라질 수 있다.
recall 분류를 공식 SoSe25 채점 기준이라고 부르기: Gedächtnisprotokoll은 비공식 회상 자료다.
9. 답을 보지 않고 확인하기
Direct-Mapped Cache에서 Hit가 되기 위한 두 조건은 무엇인가?
이 문제에서 exact memory Block을 식별하는 정보는 무엇인가?
#4가 기존 Set-6 Block을 교체하면서도 Compulsory Miss인 이유는 무엇인가?
#5가 #1과 같은 Tag를 가져도 Compulsory Miss인 이유는 무엇인가?
#6이 Conflict Miss인 상태 변화 과정을 설명하라.
#7과 #8의 분류는 각각 무엇이며 왜 다른가?
#9가 Capacity Miss가 아닌 이유는 무엇인가?
#10이 Hit인 이유는 무엇인가?
전체 trace의 Compulsory, Conflict, Capacity, Hit 개수는 각각 얼마인가?
왜 초기 Cache 상태를 명시해야 하는가?
확인문제 정답 보기
Mapped Set의 valid bit가 1이고 저장 Tag가 요청 Tag와 같아야 한다.
이미 주어진 (Tag, Set) 쌍이 exact Block을 식별한다.
(0x0009,6) 자체는 trace에서 처음 요청되는 Block이기 때문이다. 첫 접근 Miss는 교체 여부와 무관하게 Compulsory다.
#1은 (0x0FFE,4)이고 #5는 (0x0FFE,7)이므로 Set이 달라 서로 다른 Block이다.
#2에서 (0x0004,6)을 넣었고 #4의 (0x0009,6)이 이를 교체했다. #6에서 이미 본 0x0004를 다시 요청하지만 없고 총 용량은 충분하므로 Conflict Miss다.
#7의 (0x0009,4)는 첫 접근이라 Compulsory Miss이고, #8의 (0x0009,6)은 #4에서 본 뒤 #6에 의해 밀려난 재접근이라 Conflict Miss다.
전체 distinct blocks가 다섯 개로 8-block cache 용량보다 적어 fully associative Cache라면 모두 남아 있을 수 있기 때문이다.
#5에서 넣은 (0x0FFE,7) 뒤로 Set 7을 바꾼 접근이 없어서 valid와 tag가 그대로 일치한다.
Compulsory 5회, Conflict 3회, Capacity 0회, Hit 2회다.
초기 valid/tag 내용에 따라 첫 접근들이 Hit 또는 Miss인지 달라질 수 있기 때문이다. 이 해설은 empty start를 사용한다.
Wichtig: Die Recall-Loesung wird nicht als offizielle Musterloesung behandelt. Alle Rechenschritte unten sind gegen die aktuellen Uebung/Loesung 11-12 und Vorlesung Teil 3 nachgerechnet.
Original German
8a) (ca. 4 Punkte)
Folgende Hits und Misses in einem Programm:
Zugriff
1
2
3
4
5
6
7
8
9
10
Cache Status
Hit
Compulsory Miss
Hit
Capacity Miss
Hit
Hit
Hit
Hit
Hit
Conflict Miss
Cache Zugriff dauert 3 Zyklen und Hauptspeicherzugriff dauert 100 Zyklen. Berechne Miss Rate und AMAT (average memory access time).
Recall-Loesung: Miss Rate 3/10 = 0.3, AMAT 3 + 100 * 0.3 = 33 Zyklen.
Die Daten werden in einem 2-way set associative Cache mit 4 Sets, einer Blockgroesse von einem Wort und einer Adressbreite von 16 Bit eingetragen. Trage in die Tabelle Tags, Set-Index und Byte-Offset ein.
Normalisierungsnotiz: addi t2, t2 -1 ist syntaktisch unvollstaendig; gemeint ist addi t2, t2, -1. Die Schleife laeuft wegen t2 = 4 viermal und erzeugt acht Datenzugriffe, jeweils lb, dann lw.
8c) (ca. 4 Punkte)
Fuehre diese Speicherzugriffe nun in einem Direct-Mapped Cache mit 8 Bloecken und einer Blockgroesse von einem Wort aus. Tag und Set sind gegeben. Sage, um welche Art Miss es sich handelt: Compulsory, Conflict oder Capacity.
Zugriff
#1
#2
#3
#4
#5
Tag
0x0FFE
0x0004
0x0FFE
0x0009
0x0FFE
Set
4
6
4
6
7
Hit/Miss Typ
Compulsory Miss
Compulsory Miss
Zugriff
#6
#7
#8
#9
#10
Tag
0x0004
0x0009
0x0009
0x0FFE
0x0FFE
Set
6
4
6
4
7
Hit/Miss Typ
Normalisierungsnotiz: Im Recall steht Cumpolsory; gemeint ist Compulsory.
Korean Translation
8a)
10번의 Speicherzugriff에 대해 Hit/Miss 종류가 주어진다. Cache 접근 시간은 3 Takte, Hauptspeicher 접근 시간은 100 Takte이다. Miss Rate와 AMAT, 즉 average memory access time을 구하라.
8b)
주어진 RISC-V 코드에서 실제로 실행되는 lb와 lw의 Datenadresse를 순서대로 구한다. 그 주소들을 16-bit Adresse로 보고, 2-way set associative Cache, 4 Sets, Blockgroesse 1 Wort 조건에서 Tag, Set-Index, Byte-Offset으로 나누어 표를 채워라.
8c)
이번에는 Direct-Mapped Cache, 8 Blocks, Blockgroesse 1 Wort에서 주어진 Tag/Set 순서대로 접근한다. 각 접근이 Hit인지, Miss라면 Compulsory Miss, Conflict Miss, Capacity Miss 중 무엇인지 분류하라.
Concept Lesson
Cache는 Prozessor 가까이에 있는 작고 빠른 Speicher이다. Vorlesung Teil 3 pages 4-8은 Cache Hit가 요청한 Daten이 Cache에 있는 경우, Cache Miss가 Hauptspeicher에서 가져와야 하는 경우라고 설명하고, AMAT 공식을 AMAT = t_cache + miss rate * t_main memory로 둔다.
주소 분해는 시험에서 가장 먼저 해야 한다. Uebung 11과 Loesung 11은 Adresse를 Tag | Set-Index | Byte-Offset으로 나눈다. Byte-Offset은 Block 안의 byte 위치, Set-Index는 어느 Set을 볼지, Tag는 그 Set 안에서 실제 Block이 맞는지 식별한다. 이 Aufgabe 8b에서는 Blockgroesse가 1 Wort이고 32-bit Wort를 쓰므로 Block은 4 Byte, 따라서 Byte-Offset은 2 Bit이다. 4 Sets이므로 Set-Index도 2 Bit이다. 전체 주소가 16 Bit라서 Tag는 16 - 2 - 2 = 12 Bit이다.
Associativity는 한 Set 안에 몇 개의 Way가 있는지다. Direct-mapped Cache는 Set마다 Way가 1개라서 같은 Set으로 오는 다른 Tag들이 서로 바로 verdrängen된다. 2-way set associative Cache는 Set마다 두 자리(Ways)가 있어 conflict misses가 줄어든다. Vorlesung Teil 3 pages 22-32와 Loesung 11 pages 7-10이 이 방식의 trace를 보여준다.
Miss 종류는 이렇게 구분한다. 첫 접근이면 Compulsory Miss이다. 이미 본 Block인데 다시 필요할 때 없어졌다면, Cache 전체 용량이 충분했는지 본다. 전체 Cache Blocks 수보다 적은 서로 다른 Block들만 사이에 있었는데도 mapping 때문에 밀려났으면 Conflict Miss이다. 전체 용량 자체가 부족해서 밀려났으면 Capacity Miss이다. Loesung 12 pages 1-6이 이 기준과 LRU trace를 공식적으로 사용한다.
LRU는 Least Recently Used, 가장 오래 안 쓴 Block을 교체하는 전략이다. Pseudo-LRU는 정확한 최근 사용 순서를 모두 저장하지 않고 더 싼 근사 정보를 저장한다. Loesung 12 pages 1-4는 Pseudo-LRU가 echte LRU보다 하드웨어가 단순하지만 항상 정확하지는 않다고 설명한다.
Write policy는 Store에서 중요하다. Write-through는 Cache에 쓴 값을 매번 Hauptspeicher에도 쓴다. Write-back은 Cache Block만 바꾸고 Dirty-Bit를 세운 뒤, 그 dirty Block이 나중에 verdrängt될 때 Hauptspeicher에 쓴다. Valid-Bit는 Cache entry가 유효한지 표시한다. Vorlesung Teil 3 pages 66-78과 Loesung 12 pages 7-8이 이 차이를 다룬다.
학생들이 자주 틀리는 이유는 세 가지다. 첫째, lb는 1 Byte load라서 Byte-Offset이 의미 있는데도 lw처럼 무조건 offset 0이라고 생각한다. 둘째, Set을 주소의 hex digit 하나로 찍는다. 반드시 bit를 잘라야 한다. 셋째, Capacity Miss와 Conflict Miss를 "뭔가 evict 되었으니 capacity"처럼 감으로 고른다. 반드시 전체 cache capacity와 mapping을 비교해야 한다.
Problem Interpretation
Given:
8a: 10 accesses, 3 misses, cache hit/access time 3 cycles, memory miss penalty/access time 100 cycles.
8b: t0 = 0x120, t1 = 0x300, t2 = 4; loop body has lb 0x8(t0) and lw 0x0(t1).
8b: actual address sequence plus Tag, Set-Index, Byte-Offset.
8b optional state check: how associativity changes hit/miss if the cache starts empty.
8c: Hit/Miss type for each Tag/Set pair.
Constraints and traps:
lb and lw are both memory accesses; li, addi, bne do not access data cache here.
The loop updates t0 by 3 and t1 by 8 after both memory accesses.
Byte address, not word address: offset bits are the lowest 2 bits for a one-word block.
In 8b, the original prompt asks only Tag/Set/Offset, not replacement. If a cache state is requested, state the replacement assumption, for example LRU.
In 8c, there are only five distinct (Tag, Set) Blocks and the cache has 8 total Blocks. Repeated misses cannot be Capacity Misses under this sequence; they are Conflict Misses.
Core formulas:
Miss Rate = #Misses / #Accesses
AMAT = cache access time + miss rate * main memory access time
block_offset_bits = log2(block size in bytes)
set_index_bits = log2(number of sets)
tag_bits = address_bits - set_index_bits - block_offset_bits
block_number = floor(address / block_size)
set_index = block_number mod number_of_sets
tag = floor(block_number / number_of_sets)
Count the memory accesses only. Ignore ALU/branch instructions for data-cache tables unless the task explicitly asks for instruction cache.
Write the dynamic register values before splitting addresses.
Derive bit widths: offset bits, set bits, tag bits.
For every address, write binary or at least use shifts/masks: tag = addr >> 4, set = (addr >> 2) & 3, offset = addr & 3.
For hit/miss classification, keep a cache state table. A hit needs both valid entry and matching tag in the mapped Set.
For miss type, first ask "Have I ever seen this exact memory Block before?" If no, Compulsory. If yes, compare with a fully associative cache of the same capacity: if it could have stayed, Conflict; if not, Capacity.
Only after the trace is finished compare with the recall solution.
Detailed Solution
8a) Miss Rate and AMAT
The table contains three misses: access #2 Compulsory Miss, #4 Capacity Miss, and #10 Conflict Miss.
This matches the recalled table. The most important sanity checks are:
0x128 and 0x12B are in the same 4-byte block 0x128..0x12B, so they have the same Tag and Set but different Byte-Offset.
0x300 and 0x308 have the same Tag 0x30 but different Set because bit field addr[3:2] changes from 00 to 10.
lb at 0x12B can have Byte-Offset 3; a byte load does not need word alignment.
8b) Optional Cache State Check Under LRU
The original 8b only asks for fields. If a tutor asks for cache state too, one valid assumption is an initially empty 2-way cache with LRU replacement as in Loesung 12 pages 1-6.
#
Address
Tag
Set
Offset
Hit/Miss under empty 2-way LRU
State change in relevant Set
1
0x128
0x12
2
0
Compulsory Miss
Set 2 gets tag 0x12
2
0x300
0x30
0
0
Compulsory Miss
Set 0 gets tag 0x30
3
0x12B
0x12
2
3
Hit
Same block as #1, tag 0x12 becomes most recent
4
0x308
0x30
2
0
Compulsory Miss
Set 2 gets tag 0x30 in the other Way
5
0x12E
0x12
3
2
Compulsory Miss
Set 3 gets tag 0x12
6
0x310
0x31
0
0
Compulsory Miss
Set 0 gets tag 0x31 in the other Way
7
0x131
0x13
0
1
Compulsory Miss
Set 0 is full; under LRU, replace older tag 0x30
8
0x318
0x31
2
0
Compulsory Miss
Set 2 is full; under LRU, replace older tag 0x12
No 8b replacement result is part of the recalled official prompt. The state table is a learning extension to show how associativity and LRU would matter.
8c) Direct-Mapped Cache Simulation
Direct-mapped means each Set has exactly one slot. A Hit requires cache[set].valid = 1 and cache[set].tag = requested tag.
Detailed trace:
#
Tag
Set
Before relevant Set
Result
Why
After relevant Set
1
0x0FFE
4
invalid
Compulsory Miss
first access to block (0x0FFE, 4)
set 4 = 0x0FFE
2
0x0004
6
invalid
Compulsory Miss
first access to block (0x0004, 6)
set 6 = 0x0004
3
0x0FFE
4
0x0FFE
Hit
valid and tag matches
set 4 = 0x0FFE
4
0x0009
6
0x0004
Compulsory Miss
first access to (0x0009, 6); it replaces (0x0004, 6)
set 6 = 0x0009
5
0x0FFE
7
invalid
Compulsory Miss
first access to (0x0FFE, 7)
set 7 = 0x0FFE
6
0x0004
6
0x0009
Conflict Miss
(0x0004, 6) was seen at #2 but got replaced by same-set block #4
set 6 = 0x0004
7
0x0009
4
0x0FFE
Compulsory Miss
first access to (0x0009, 4); replaces (0x0FFE, 4)
set 4 = 0x0009
8
0x0009
6
0x0004
Conflict Miss
(0x0009, 6) was seen at #4 but got replaced by same-set block #6
set 6 = 0x0009
9
0x0FFE
4
0x0009
Conflict Miss
(0x0FFE, 4) was seen at #1/#3 but got replaced by same-set block #7
Therefore, the repeated misses #6, #8, #9 are not Capacity Misses. The cache would have enough total slots if it were fully associative; they miss because direct mapping forces collisions in Set 4 or Set 6.
With 2 offset bits and 2 set bits, all recalled entries match.
8c #6, #8, #9 are Conflict Misses.
Correct
Each is a repeated block evicted by same-set mapping while total capacity is sufficient.
8c #7 is Compulsory Miss.
Correct
(0x0009, Set 4) has not appeared before.
8b has a unique final cache state.
Incomplete if claimed
The original prompt does not specify replacement policy. A final state after replacements needs an assumption such as LRU.
First likely error source: treating hex digits as fields without deriving bit widths. Violated rule: source material splits addresses by Tag | Set-Index | Byte-Offset; bit counts must come from block size and number of Sets, not from visual hex grouping.
Why a student chooses it: They think the Cache is word-addressed.
Why it is wrong: RISC-V data addresses are byte addresses. A 32-bit Wort has 4 Byte, so one-word block still needs 2 Byte-Offset bits.
Violated rule: Byte-Offset = log2(block size in bytes).
Fast check: lb at 0x12B must be able to select byte 3 of the word block 0x128..0x12B.
Corrected approach: Use offset = address & 0x3.
Wrong answer 2: "0x12B has Set 0xB or Set 3 because the last hex digit is B."
Why a student chooses it: Hex digits are tempting shortcuts.
Why it is wrong: The lowest 2 bits are Byte-Offset, not Set. For 0x12B, binary ending is 1011: offset 11 = 3, set bits are the next two bits 10 = 2.
Violated rule: fields are bit slices, not arbitrary hex characters.
Fast check: Compute (0x12B >> 2) & 0x3 = 2.
Corrected approach: Always shift away offset bits before taking Set bits.
Wrong answer 3: "Access #6 in 8c is Capacity Miss."
Why a student chooses it: The old block is gone, so they associate eviction with capacity.
Why it is wrong: Only five distinct blocks occur in the whole sequence, while the cache can hold eight blocks. The miss happens because Set 6 can hold only one tag in a direct-mapped cache.
Violated rule: Capacity Miss requires insufficient total cache capacity under an ideal mapping; Conflict Miss is mapping/associativity pressure.
Fast check: Count distinct (Tag, Set) pairs so far and compare with 8 total blocks.
Corrected approach: #6 is Conflict Miss.
Wrong answer 4: "A 2-way set associative cache cannot have conflict misses."
Why a student chooses it: They remember that associativity reduces conflict misses.
Why it is wrong: It reduces them but does not eliminate them unless the cache is fully associative or the working set fits per Set.
Violated rule: Set associative caches still map each address to exactly one Set; only the Way is flexible.
Fast check: If three different tags map to the same 2-way Set, one must be replaced.
Corrected approach: Track Set occupancy and replacement policy.
Wrong answer 5: "Write-back writes to Hauptspeicher on every Store Hit."
Why a student chooses it: They mix up Write-back and Write-through.
Why it is wrong: Write-back updates Cache and Dirty-Bit; Hauptspeicher is updated only when a dirty block is evicted.
Violated rule: Dirty-Bit exists precisely to defer memory writes.
Fast check: Loesung 12 pages 7-8 has the first Store Miss load and dirty the block; later hits do not immediately write back.
Corrected approach: Say Write-through: every store writes memory. Write-back: dirty on cache update, write memory on dirty eviction.
Exam-Room Method
Time budget:
3 minutes: 8a formula and count.
5 minutes: 8b loop trace and bit-width derivation.
If you forget a table entry, still show the bit-width derivation.
If you are unsure about miss type, write the cache state before/after each access.
For Capacity vs Conflict, explicitly count distinct blocks and cache capacity.
Last check:
Do all lw addresses end with offset 0? In this task, yes.
Do lb addresses have offsets 0, 3, 2, 1? Yes, because t0 increases by 3.
Are any 8c repeated misses Capacity Misses? No, only five distinct blocks for eight available cache blocks.
Active Recall
Questions
Concept check: In Tag | Set-Index | Byte-Offset, what does Byte-Offset select?
Hand calculation: For address 0x12B in 8b, compute Tag, Set, and Byte-Offset.
Trace: Starting with t0 = 0x120, what are the four lb 0x8(t0) addresses?
Miss classification: Why is 8c access #8 a Conflict Miss and not a Capacity Miss?
Transfer: For a 16-bit address, 8 Sets, and 16-byte blocks, how many Tag bits are there?
Policy check: What is the difference between Write-through and Write-back?
Answers
Byte-Offset selects the exact byte position inside the cache block.
0x12B >> 4 = 0x12; (0x12B >> 2) & 3 = 2; 0x12B & 3 = 3, so Tag 0x12, Set 2, Offset 3.
0x128, 0x12B, 0x12E, 0x131.
(0x0009, Set 6) was loaded at #4, evicted by (0x0004, Set 6) at #6, and requested again at #8. The cache has 8 total blocks and only 5 distinct requested blocks, so total capacity is enough; the direct-mapped Set collision caused the miss.
Offset bits log2(16) = 4; Set bits log2(8) = 3; Tag bits 16 - 4 - 3 = 9.
Write-through writes every Store to Hauptspeicher immediately. Write-back writes modified data first only to Cache, sets Dirty-Bit, and writes to Hauptspeicher when the dirty Block is evicted.
Sources
Gedächtnisprotokoll Rechnerorganisation SoSe25.md#aufgabe-8: recalled original task and recalled solution, unverified and not official.
Uebung\Uebung 11.pdf pages 1-4: cache theory questions, address fields, AMAT exercise, direct-mapped and 2-way cache tracing.
Uebung\Loesung 11.pdf pages 1-6: official definitions for cache hierarchy, hit/miss, Tag | Set-Index | Byte-Offset, bit calculations, AMAT formula and hit/miss rate.
Uebung\Loesung 11.pdf pages 7-10: official direct-mapped and 2-way set associative trace examples with Tag/Set and final cache state.
Uebung\Loesung 12.pdf pages 1-4: official definitions of Capacity vs Conflict Miss, LRU, Pseudo-LRU, Write-through, Write-back, Valid-Bit and Dirty-Bit.
Uebung\Loesung 12.pdf pages 4-6: official LRU trace and classification showing a Conflict Miss when capacity is sufficient.
Uebung\Loesung 12.pdf pages 7-8: official Write-through without Write-Allocate and Write-back with Write-Allocate comparison.
Vorlesung\Rechnerorganisation - Teil 3.pdf pages 7-12: miss rate, hit rate, AMAT, cache organization and address fields.
Vorlesung\Rechnerorganisation - Teil 3.pdf pages 22-32: direct-mapped conflict examples and N-way set associative cache behavior.
Vorlesung\Rechnerorganisation - Teil 3.pdf pages 55-57: replacement policy and LRU use bit.
Vorlesung\Rechnerorganisation - Teil 3.pdf pages 64-78: reducing miss rate, write policy, write-through/write-back examples.
Completion Check
[x] Metadata included.
[x] Original German problem included with normalization notes.
[x] Korean translation included.
[x] Beginner-first concept lesson included.
[x] Problem interpretation includes Given, Find, Constraints, traps, formulas, and required intermediate state.
[x] Repeatable solving procedure appears before the answer.
[x] AMAT and miss rate independently recalculated.
[x] Actual lb/lw address sequence independently traced.
[x] Block/offset/index/tag bit split independently checked.
[x] Associativity and optional cache state discussed without inventing an unspecified replacement policy.
[x] Direct-mapped cache state for 8c fully traced.
[x] Compulsory, conflict, and capacity miss rules applied and audited.
[x] LRU/Pseudo-LRU and write policy covered from current sources.