풀이 순서 (공식 5개)

① page offset 비트 = log₂(페이지 크기)
② VPN 비트       = 가상 주소 비트 − page offset
   PPN 비트       = 물리 주소 비트 − page offset
③ TLB index 비트  = log₂(TLB set 수),  TLB set 수 = 항목 수 ÷ way 수
   TLB tag 비트   = VPN − TLB index
④ 캐시 block offset = log₂(블록 크기)
   캐시 index       = log₂(set 수),  set 수 = 캐시 크기 ÷ 블록 크기 ÷ way 수
   캐시 tag         = 물리 주소 비트 − index − block offset
⑤ 비교: index + block offset ≤ page offset 이면 → 그 비트들은 번역 없이 가상 주소에서 바로 사용

Exercise 1

Consider a system with the following processor components and policies:

• A direct-mapped L1 data cache of size 4KB and block size of 16 bytes, indexed and tagged using physical addresses, and using a write-allocate, write-back policy
• A fully-associative data TLB with 4 entries and an LRU replacement policy
• Physical addresses of 32 bits, and virtual addresses of 40 bits
• Byte addressable memory
• Page size of 1MB

(1)

Which bits of the virtual address are used to obtain a virtual to physical translation from the TLB? Explain exactly how these bits are used to make the translation, assuming there is a TLB hit.

Exercise 1에 적용

주어진 값: 가상 주소 40비트, 물리 주소 32비트, 페이지 1 MB, TLB fully associative 4칸, 캐시 direct-mapped 4 KB, 블록 16 B

① page offset

1 MB = 2²⁰ → page offset = 20비트

② VPN, PPN

VPN = 40 − 20 = 20비트
PPN = 32 − 20 = 12비트

③ TLB 나누기

fully associative는 set이 1개(모든 칸이 한 set)라서:

TLB index = log₂(1) = 0비트
TLB tag   = 20 − 0 = 20비트 (VPN 전부)

④ 캐시 나누기

block offset = log₂(16)          = 4비트
set 수       = 4 KB ÷ 16 B ÷ 1   = 256 → index = log₂(256) = 8비트
tag          = 32 − 8 − 4        = 20비트

⑤ 번역 없이 쓸 수 있는 비트 찾기

page offset(하위 20비트)과 캐시 필드를 비트 번호로 겹쳐 봅니다.

물리 주소 비트:  31 ........ 20 | 19 .... 12 | 11 .... 4 | 3 .. 0
page 기준:       [   PPN 12    |        page offset 20             ]
캐시 기준:       [          tag 20          |  index 8  | offset 4 ]

• block offset (bit 3~0), index (bit 11~4) → page offset 안 → 가상 주소에서 바로
• tag 하위 8비트 (bit 19~12) → page offset 안 → 가상 주소에서 바로
• tag 상위 12비트 (bit 31~20) → PPN → 번역 후에만

(1) TLB 번역에 쓰는 비트
page offset 계산 → 20비트 (번역 안 함)
나머지가 VPN → 상위 20비트 (bit 39~20)
TLB 구조로 VPN 나누기 → fully associative라 index 0, tag 20
hit 과정 서술: VPN 20비트를 4개 항목의 tag와 동시 비교 → 일치하는 valid 항목의 PPN(12비트) 읽기 → PPN + page offset = 물리 주소 32비트

The virtual address is 40 bits long. Because the virtual page size is 1MB = 2^20 bytes, and memory is byte addressable, the virtual page
offset is 20 bits. Thus, the first 40- 20=20 bits are used for address translation at the TLB. Since the TLB is fully associative, all of these bits are used for the tag; i.e., there are no index bits.
When a virtual address is presented for translation, the hardware first checks to see if the 20 bit tag is present in the TLB by comparing it to all other entries simultaneously. If a valid match is found (i.e., a TLB hit), the page frame number is read directly from the TLB.

---

(2)

Which bits of the virtual or physical address are used as the tag, index, and block offset bits for accessing the L1 data cache? Explicitly specify which of these bits can be used directly from the virtual address without any translation

(2) 캐시의 tag, index, offset
캐시가 어느 주소를 쓰는지 확인 → “physically indexed and tagged”이니 물리 주소
block offset → index → tag 순서로 계산 (4, 8, 20)
비트 번호 적기 → offset 3~0, index 11~4, tag 31~12
page offset과 겹쳐 보기 → 하위 20비트는 가상 주소에서 바로, 상위 12비트만 번역 필요

Since the cache is physically indexed and physically tagged, all of the bits from accessing the cache must come from the physical address. However, since the lowest 20 bits of the virtual address form the page offset and are therefore not translated, these 20 bits can be used directly from the virtual address. The remaining 12 bits (of the total
of 32 bits in the physical address) must be used after translation. Since the block size is 16 bytes = 2^4 bytes, and memory is byte addressable, the lowest 4 bits are used as block offset. Since the cache is direct mapped, the number of sets is 4KB/16 bytes = 2^8. Therefore, 8 bits are needed for the index. The remaining 32-8-4 = 20 bits are needed for the tag. As mentioned above, the index and offset bits can be used before translation while the tag bits must await the translation for the 12 uppermost bits.

---

Exercise 2

Consider a virtual memory system where a TLB access takes 4ns and there is a single level of 64KB, a 4-way set associative, 16-byte block, writeback data cache with the following parameters:

• indexing the cache to access the data portion takes 10ns
• indexing the tag array of the data cache takes 8ns
• tag comparisons take 3ns
• multiplexing the output data takes 1ns

Assume these are the only parts that affect the cache access time. Assume the page size is 4KB. Calculate the amount of time it takes to get data from the cache on a hit, including any needed TLB access time.

• If can access TLB and cache simulatenously Max( Max(TLB access, Tag index)+tag comparison, Data access) + Mux

• If cannot access TLB and cache concurrently TLB access + Max (Tag index + tag comparison, Data access) + Mux

---

풀이 순서

① 캐시 비트 계산: index + block offset
② page offset 계산
③ 비교: index + offset ≤ page offset 이면 병렬, 아니면 직렬
④ 맞는 공식에 시간 넣기

① 캐시 index + block offset

block offset = log₂(16 B) = 4비트
set 수       = 64 KB ÷ (4-way × 16 B) = 1024 → index = log₂(1024) = 10비트
합계         = 10 + 4 = 14비트

② page offset

페이지 4 KB = 2¹² → page offset = 12비트

③ 비교

캐시에 필요한 비트 14  >  page offset 12

index 비트 중 2비트가 page offset 밖(페이지 번호 쪽)에 있습니다. 이 2비트는 번역을 해야 알 수 있어서, TLB 번역이 끝나기 전에는 어느 set을 읽을지조차 정할 수 없습니다. 그래서 직렬(serial)로 접근해야 합니다.

④ 직렬 공식에 대입

TLB access + max(tag index + tag comparison, data access) + mux
= 4 + max(8 + 3, 10) + 1
= 4 + max(11, 10) + 1
= 4 + 11 + 1
= 16 ns

시간 순서로 보기

직렬(이 문제)과, 만약 병렬이 가능했다면 어떻게 되는지를 나란히 그리면 이렇습니다.

공식의 각 부분이 왜 그렇게 생겼나

직렬 공식: TLB + max(tag index + 비교, data index) + mux

1. TLB (4 ns): index 비트 일부가 페이지 번호에서 오니까, 번역이 끝나야 캐시 접근을 시작할 수 있습니다.
2. tag 배열과 data 배열은 동시에 읽음: 같은 index로 두 배열을 같이 엽니다.
   • tag 쪽: 읽기 8 ns + 비교 3 ns = 4 + 11 = 15 ns에 hit 신호
   • data 쪽: 읽기 10 ns = 4 + 10 = 14 ns에 데이터 준비
3. max: mux는 둘 다 준비돼야 동작합니다. 4-way라서 4개 way의 데이터가 다 나와 있어야 하고, 그중 어느 way가 hit인지(비교 결과)도 알아야 고를 수 있기 때문입니다. 그래서 늦은 쪽(15 ns)을 기다립니다.
4. mux (1 ns): hit한 way의 데이터를 골라 내보냄 → 16 ns

병렬 공식: max(max(TLB, tag index) + 비교, data index) + mux

• tag 배열 읽기가 TLB와 동시에 시작됩니다.
• 그런데 tag 비교에는 TLB가 준 물리 페이지 번호가 필요하므로, 비교는 TLB와 tag 읽기 둘 다 끝난 뒤에 합니다 → max(TLB, tag index) + 비교
• data 배열도 0부터 동시에 읽습니다.
• mux는 hit 신호와 data가 둘 다 준비된 뒤 → max(…) + mux

max(max(4, 8) + 3, 10) + 1 = max(11, 10) + 1 = 12 ns

병렬이 가능했다면 TLB 4 ns가 tag 읽기 8 ns 뒤에 숨겨져서 12 ns로 줄어듭니다.

Solutions
Bits required for indexing = log (64KB/4*16) = 10. Bits required for block offset = 4. Total bits required to access the cache = 14. Total bits for the page offset = 12. So physical indexing cannot proceed before translation. The virtual address must be translated before anything else can happen. So the 4ns delay of the TLB access must be added into the total. Accessing the data and tag arrays occurs in parallel. The data values are available after 4+10=14ns but the tag hit signal does not appear until 4+8+3=15ns. At this point, the correct way can be selected from the mux, which has an additional 1ns delay. Therefore, the total access time is 16ns.