• Data bases, file servers, … Growing interest in servers, server perf. Improved understanding in how to use multiprocessors effectively
• Especially server where significant natural TLP Advantage of leveraging design investment by replication
• Rather than unique design

“A parallel computer is a collection of processing elements that cooperate and communicate to solve large problems fast.”

Parallel Architecture = Computer Architecture + Communication Architecture

2 classes of multiprocessors WRT memory:

1. Centralized Memory Multiprocessor
• < few dozen processor chips (and < 100 cores)
• Small enough to share single, centralized memory

2. Distributed Memory multiprocessor
• Larger number chips and cores than 1.
• BW demands -> Memory distributed among processors

Centralized vs. Distributed Memory

Centralized Memory Multiprocessor

Also called symmetric multiprocessors (SMPs) because single main memory has a symmetric relationship to all processors

Can scale to a few dozen processors by using a switch and by using many memory banks

Although scaling beyond that is technically conceivable, it becomes less attractive as the number of processors sharing centralized memory increases

Distributed Memory Multiprocessor

Pro: Cost-effective way to scale memory bandwidth • If most accesses are to local memory Pro: Reduces latency of local memory accesses

Con: Communicating data between processors more complex

① 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 30), index (bit 114) → 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 30, index 114, 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.

1. Why we need translation at all

A TLB is a small, fast cache that remembers where virtual pages live in physical memory, so the CPU doesn’t have to read the page table from memory on every access.

1. Why we need translation at all

With virtual memory, every address a program uses is a virtual address. Before the CPU can fetch the data, it must turn that into a physical address (the real location in RAM).

An address is split into two parts:

Virtual address  = [ virtual page number (VPN) | offset ]
Physical address = [ physical frame number (PFN) | offset ]

• The offset (position inside the page) stays the same.
• Only the page number changes, and the page table says what it changes to.

Example (4 KB pages): virtual address 0x3ABC → VPN = 3, offset = 0xABC. The page table says “page 3 is in frame 7”, so the physical address is 0x7ABC.

2. The problem: two memory accesses for every one

The page table itself lives in main memory. So without help, every load or store needs:

1. one memory access to read the page table entry (to find the frame), then
2. one memory access to get the actual data.

That makes every memory access twice as slow.

3. The fix: the TLB

The TLB (Translation Lookaside Buffer) is a tiny, very fast cache inside the CPU that stores recently used page table entries (VPN → frame number). It’s typically only tens to a few thousand entries, and often fully associative.

Analogy: the page table is the full address book in a drawer (main memory). The TLB is a sticky note on your monitor with the few addresses you’ve looked up recently. You check the sticky note first and only open the drawer if the address isn’t there.

4. What happens on each access

There are four possible paths, from fastest to slowest:

Path 1, TLB hit + cache hit: The TLB gives the frame number immediately, the CPU forms the physical address, and the data is found in the cache. This is the common, fast case.

Path 2, TLB hit + cache miss: The translation is fast, but the data isn’t in the cache, so it comes from main memory.

Path 3, TLB miss, page is in memory: The translation isn’t on the “sticky note”, so the CPU (or OS) reads the page table in main memory. The page table says the page is in RAM, so its entry is copied into the TLB and the access is retried, now as a TLB hit.

Path 4, TLB miss, page is NOT in memory (page fault): The page table’s valid bit says the page is on disk. The OS must:

1. load the page from disk into a free frame in memory,
2. update the page table,
3. update the TLB,
4. restart the instruction.

Disk is extremely slow compared to memory, so this costs millions of cycles.

5. Slide question: “If TLB hit, where can you find the data?”

Answer: in the cache or in main memory, never on disk.

A TLB hit only tells you where the page is in physical memory. It says nothing about whether that particular block is in the cache.

• If the block is in the cache → cache (path 1)
• If not → main memory (path 2)

It can’t be on disk because the TLB only keeps entries for pages that are currently in physical memory. When the OS moves a page out to disk, it marks the page table entry invalid and removes (invalidates) that page’s TLB entry. So if the TLB has an entry, the page must be in RAM

6. Clearing up the slide’s wording: TLB miss ≠ page fault

The slide jumps quickly from “TLB miss” to “page fault”, but they’re different events:

• Most TLB misses are not page faults. The page table usually says “the page is in memory, frame X”, and you just refill the TLB.
• A page fault happens only when the page table says the page is not in memory.
• The slide says the page table “may not be in the memory”. More precisely, it’s the page (the data) that may be on disk. The page table normally stays in memory.

7. Summary in one picture

Virtual address
   │
   ▼
 TLB ──hit──► physical address ──► cache ──miss──► main memory
   │
  miss
   ▼
 Page table (in memory)
   ├─ page in memory ──► update TLB ──► retry (now a TLB hit)
   └─ page NOT in memory ──► PAGE FAULT ──► OS loads page from disk
                                           ──► update page table + TLB ──► retry

Each virtual memory reference can cause two physical memory accesses

• One to fetch the page table
• One to fetch the data

To overcome this problem a high-speed cache is set up for page table entries

• Called a Translation Lookaside Buffer (TLB)
• TLB is a cache of the page table
• Contains page table entries that have been most recently used

Given a virtual address, processor examines the TLB

If page table entry is present (TLB hit), the page frame address is retrieved and the real address is formed

• Page frame address: physical memory location of that page

Question: if TLB hit, where can you find the data? Cache? Memory? Disk?

If page table entry is not found in the TLB (TLB miss), the page number is used to index the process page table which may not in the memory

• Causes a page fault: page is not in the memory
• Penalty: millions of cycles

First checks if page is already in main memory

• If not in main memory a page fault is issued

The TLB is updated to include the new page entry

A Hirerachy of Misses

1. TLB miss
2. Cache miss
3. Page fault
4. Multiple instances of any of these misses can occur for any single instruction

TLB (Direct mapped vs fully associative)

Both sides translate the same virtual address, page 5, offset 502, to the same real address, frame 37, offset 502. They differ in how they find “page 5 → frame 37”.

(a) Direct mapping: the page table

The page table has one entry for every virtual page, in order. So the page number is used directly as an index:

page 5  →  go straight to entry #5  →  frame 37

No searching is needed, because entry #5 always belongs to page 5. The entry doesn’t even need to store the page number.

(b) Associative mapping: the TLB

The TLB is tiny and holds only a few recently used pages, in any order (19, 511, 37, 27, 14, 1, 211, 5, 90, …). Page 5 could be in any slot, so:

• each TLB entry stores the page number (its tag) next to the page table entry, and
• the incoming page number (5) is compared against all entries at the same time.

The entry tagged 5 matches, and it gives frame 37. This is exactly a fully associative cache, where the page number is the tag.

Then: real address = frame number + same offset

Virtual:  [ page 5  | offset 502 ]
Real:     [ frame 37 | offset 502 ]    ← offset is copied unchanged

Why the TLB is usually (fully) associative

TLB misses are expensive (a page table walk), and the TLB is small, so having one comparator per entry is affordable. That’s why TLBs are typically fully associative or highly set associative. It’s the same reasoning as the victim cache.

Any problem with this design w.r.t performance ?

TLB Access Timing

Don’t want TLB in critical path to cache

• But, TLBs are early select -- have to match page name before accessing memory address
• Slow approach is: TLB page name -> TLB Page Frame Address -> Cache Access

The problem: the slow, serial path

The cache in this figure is physically addressed: its tags are physical addresses. So the obvious way to access it is:

TLB (translate page #) → get frame # → THEN access the cache
hit time = TLB time + cache time

The TLB lookup sits in the critical path of every load and store, which makes every cache hit slower.

The key observation: the offset bits never change

Translation only changes the page number. The page offset (low 12 bits for a 4 KB page) is identical in the virtual and physical address. So the CPU can start using those bits before translation finishes.

The solution: access the TLB and the cache at the same time

Here is how the figure’s numbers fit together:

Step by step, for one access:

1. At the same time:
   • the 20 high bits (virtual page number) go to the TLB, and
   • the 12 low bits (page offset) go straight to the 4 KB cache to select the block (“block select”). The cache reads out that block’s data and its stored 18-bit tag.
2. The TLB outputs the 18-bit page frame address (the physical page number).
3. Compare the TLB’s frame number with the cache’s tag: hit if they match.

The numbers in the figure:

• 4 KB pages → page offset = log₂(4096) = 12 bits, so VPN = 32 − 12 = 20 bits
• 4 KB direct-mapped cache → index + block offset = log₂(4096) = 12 bits, exactly the page offset
• Physical address = 18-bit frame + 12-bit offset = 30 bits (1 GB of physical memory), so the cache tag = 30 − 12 = 18 bits

This design is called virtually indexed, physically tagged (VIPT): the cache is indexed with bits taken from the virtual address, but compared against physical tags.

“Any requirements to use this method?” — Yes

The cache’s index bits and block offset bits must all come from the page offset, the bits that don’t change during translation:

index bits + block offset bits ≤ page offset bits
⇔  cache size ÷ associativity ≤ page size

In other words, one way of the cache must be no bigger than one page.

Why: if even one index bit came from the virtual page number, that bit could be different in the physical address. You’d then read the wrong set before knowing the translation. A related problem: two virtual addresses that map to the same physical address (aliases) could land in different sets, giving two copies of the same data.

How to get a bigger L1 and keep the trick

• Raise associativity: a bigger cache with more ways keeps each way at 4 KB. That’s why many L1 caches are 32 KB 8-way with 4 KB pages.
• Use bigger pages: the page offset gets more bits.
• Add hardware or OS support for aliases (for example, page coloring, where the OS makes sure the extra index bits are the same in the virtual and physical address).

Solution: Access TLB & cache concurrently Any requirements to use this method?

An Memory Hierarchy Example

• Page size 8KB
• TLB direct mapped with 256 entries
• L1 cache direct-mapped, 8KB
• L2 cache direct-mapped, 4MB
• Both use 64-byte blocks
• Virtual address 64 bits, physical address 41 bits
• Draw the figure of the memory hierarchy from virtual address to L2 cache access.

you should know how to draw below structure

검산: 합이 주소 길이와 맞는지

가상 주소: TLB tag 43 + TLB index 8 + page offset 13 = 64 ✓
물리 주소 (L1 기준): L1 tag 28 + index 7 + offset 6 = 41 ✓
물리 주소 (L2 기준): L2 tag 19 + index 16 + offset 6 = 41 ✓

2단계: 그림의 흐름

① 가상 주소를 둘로 나눔

64비트 = 가상 페이지 번호 51 | page offset 13

② TLB와 L1을 동시에 찾음 (지난번에 배운 parallel access, VIPT)

TLB 쪽: 페이지 번호 51비트 = TLB tag 43 | TLB index 8. index 8비트로 TLB 칸 하나를 고르고, 저장된 TLB tag(43)와 비교합니다 (왼쪽 =?). 같으면 TLB hit이고, 그 칸의 TLB data 28비트 = 물리 페이지 번호가 나옵니다. L1 쪽 (동시에): page offset 13비트 = L1 index 7 | block offset 6. 번역이 필요 없는 비트라 바로 L1 칸을 골라 L1 tag(28)와 data(512)를 읽습니다.

③ L1 hit 판단

TLB가 준 물리 페이지 번호 28비트(“L1 tag compare address”)와 L1에서 읽은 tag 28비트를 비교합니다 (가운데 =?). 같으면 L1 hit → block offset으로 원하는 워드를 골라 CPU로 보냅니다.

④ L1 miss면 물리 주소를 만들어 L2로

물리 주소 41비트 = 물리 페이지 번호 28 (TLB에서) | page offset 13 (원래 주소에서). 이걸 L2 기준으로 다시 나눕니다: L2 tag 19 | L2 index 16 | block offset 6

⑤ L2 접근

index 16비트로 L2 칸을 고르고, 저장된 tag(19)와 비교합니다 (아래 =?). 같으면 L2 hit → 데이터를 L1이나 CPU로 보냅니다.

왜 L1 tag를 43에서 28로 고쳤나

교과서 원래 그림에는 L1 cache tag <43>로 나와 있는데, 28이 맞습니다 (그래서 고쳐 쓰신 거예요).

L1 tag는 TLB가 준 물리 페이지 번호(28비트)와 비교됩니다. 비교하는 두 값의 길이가 같아야 하니 28비트입니다. 계산으로도 물리 주소 41 − index 7 − offset 6 = 28입니다.

43은 TLB tag 길이와 헷갈린 오타입니다.

왜 L1은 TLB와 동시에, L2는 번역 후에 접근하나

지난번 규칙을 적용하면:

동시 접근 조건: index 비트 + block offset 비트 ≤ page offset 비트

그래서 L1은 VIPT(가상 주소로 index, 물리 주소로 tag 비교)이고, L2는 번역이 끝난 물리 주소로만 접근합니다 (PIPT). L2는 L1 미스 뒤에야 접근하니, 그때는 이미 번역이 끝나 있어서 기다릴 일이 없습니다.

시험에서 그리는 순서

1. 가상 주소 → VPN | page offset (offset = log₂ 페이지 크기)
2. VPN → TLB tag | TLB index (index = log₂ TLB 칸 수, direct-mapped 기준)
3. TLB data = 물리 주소 − page offset
4. page offset → L1 index | block offset, L1 tag = 물리 주소 − index − offset
5. 물리 주소 = TLB data | page offset
6. 물리 주소 → L2 tag | L2 index | block offset
7. 비교기 3개: TLB tag, L1 tag, L2 tag
8. 마지막으로 합이 64 / 41인지 검산

시험에서 숫자가 바뀌어도 이 순서대로 log₂만 하면 됩니다. 예를 들어 TLB가 4-way 256칸이면 TLB index = log₂(256 ÷ 4) = 6, TLB tag = 51 − 6 = 45가 됩니다.

Consider the following code, which sums the elements of a product of two matrices:

register int i, k; 
// i, k are in the processor registers 
register float sum, a[8][8], b[8][8];

for(i = 0; i < 8; i++) { /* 1 */
    for(k = 0; k < 8; k++) { /* 2 */
        sum += a[i][k] * b[k][i]; /* 3 */
    }
 }

Assume the following:

• There is a perfect instruction cache; i.e., do not worry about the time for any instruction accesses.
• Both int and float are of size 4 bytes.
• Assume that only the accesses to the arrays a and b generate accesses to the data cache. The rest of the variables are all allocated in registers.
• Assume a fully associative, LRU data cache with 8 lines, where each line is 32 bytes.
• Initially, the data cache is empty.
• The arrays a and b are stored in row order.
• To keep things simple, we will assume that statements in the above code are executed sequentially. Lines (1), and (2) take 10 cycles for each invocation. Line (3) takes 10 cycles plus an additional 20 cycles per data cache miss to wait for the data. That is, if both array accesses in line (3) miss, it takes a total of 50 cycles.
• Assume that the arrays a and b both start at cache line boundaries

--

먼저 볼 것: 한 행(row) = 캐시 한 줄 float 하나 = 4 B, 한 행 = 8개 × 4 B = 32 B = 캐시 한 줄 배열은 행 우선(row order)으로 저장되고 줄 경계에서 시작하므로: a[i][0..7] → 줄 A_i 하나 b[k][0..7] → 줄 B_k 하나 a, b 각각 8줄씩 총 16줄인데, 캐시는 8줄뿐입니다.

접근 패턴 i를 하나 고정하고 k = 0..7을 돌면:

a[i][k] : a[i][0], a[i][1], ..., a[i][7]  → 전부 같은 줄 A_i (행 방향)
b[k][i] : b[0][i], b[1][i], ..., b[7][i]  → B0, B1, ..., B7 (열 방향 = 매번 다른 줄)

i 하나를 처리하는 데 필요한 줄은 A_i 1개 + B0~B7 8개 = 9줄인데, 캐시는 8줄입니다. 여기서 문제가 생깁니다. -> 문제에서 cache line = 8 lines 이라고 했음

(a)

How many accesses to arrays a and b will result in cache misses? Explain your answer.

답은 (a) 72번 미스 (a 8번 + b 64번).

(a) 미스 횟수 = 72 i = 0

접근 순서: A0, B0, A0, B1, A0, B2, …, A0, B7

A0: 처음 1번 미스, 나머지 7번 hit B0~B7: 처음이라 8번 모두 미스 B7이 들어올 때 캐시가 꽉 차 있으므로 LRU인 B0이 쫓겨남

i = 0이 끝난 뒤 캐시 (오래된 것 → 최근 것): B1 B2 B3 B4 B5 B6 A0 B7

B 줄들은 순서대로 돌아가며 쓰이는데, LRU는 ”가장 오래전에 쓴 줄"을 내보내고, 그게 바로 곧 다시 쓸 줄입니다. 9줄이 8칸 캐시를 순환하면 LRU에서는 b 접근이 전부 미스가 납니다. A_i는 매 반복 쓰이니 계속 남아 있습니다.

끝난 상태가 i = 0 뒤와 같은 모양이라, i = 2~7도 똑같이 반복됩니다

참고로 실행 시간은 10 × 8 (line 1) + 10 × 64 (line 2) + 10 × 64 (line 3) + 20 × 72 (미스) = 2800 cycles입니다.

(b)

Now assume there is a data prefetch instruction with the format prefetch (array[index1][index2]). This prefetches the entire block containing the word array[index1][index2] into the data cache.

It takes 1 cycle for the processor to execute this instruction and send it to the data cache. The processor can then go ahead and execute subsequent instructions. If the prefetched data is not in the cache, it takes 20 cycles for the data to get loaded into the cache.

Add prefetch instructions to minimize the execution time. Do not transform the code in any other way. How many cache misses for accessing a and b at line (3) in your modified code?

(Hint: since line 1, 2, and 3 each takes 10 cycles when there is no cache miss, you can consider using them to hide the 20-cycle latency for the data to get loaded into the cache when prefetching. If you insert the prefetch instructions appropriately, the cache misses can be totally eliminated.)

(b) Prefetch로 미스 0번 만들기 핵심: 데이터가 필요한 시점보다 20 cycles 이상 먼저 prefetch

prefetch는 발행에 1 cycle, 데이터 도착에 20 cycles가 걸립니다. 힌트대로 line 1, 2, 3이 각각 10 cycles이므로 두 줄(20 cycles)만큼 앞서 prefetch하면 지연이 다 숨겨집니다

prefetch(a[0][0]);                   /* A0: 첫 a 줄 */
prefetch(b[0][0]);                   /* B0: 첫 b 줄 */
for (i = 0; i < 8; i++) {            /* 1 */
    for (k = 0; k < 8; k++) {        /* 2 */
        prefetch(b[k+1][i]);         /* 다음 반복에 쓸 b 줄 B_(k+1) */
        sum += a[i][k] * b[k][i];    /* 3 */
    }
    prefetch(a[i+1][0]);             /* 다음 i의 a 줄 A_(i+1) */
    prefetch(b[0][i+1]);             /* 다음 i의 첫 b 줄 = B0 */
}

각 prefetch가 왜 그 위치인가

① 루프 전 prefetch 2개 prefetch 두 개(2 cycles)를 낸 뒤 line 1(10) + line 2(10) = 20 cycles가 지나고 첫 line 3이 실행되므로, 딱 맞게 도착합니다.

② 안쪽 루프의 prefetch(b[k+1][i]) 반복 k에서 발행하면, 그 뒤 line 3(10) + 다음 반복의 line 2(10) = 20 cycles 후에 b[k+1][i]를 씁니다. 한 반복 앞서 가져오면 충분합니다.

③ 바깥 루프 끝의 prefetch 2개 k = 7의 line 3이 끝나고 다음 i의 첫 line 3까지 line 1(10) + line 2(10) = 20 cycles입니다.

a[i+1][0]: 다음 행의 a 줄 b[0][i+1]: 줄 B0. b[0][어떤 열]이든 같은 줄이라, 다음 i의 첫 b 접근 b[0][i+1]이 미리 들어옵니다. a는 왜 한 행에 한 번만 prefetch하나

a[i][0..7]이 전부 한 줄(A_i)이라, 첫 접근만 미스입니다. 그 뒤로는 매 반복 쓰이니 LRU에서 쫓겨나지 않습니다. 그래서 행마다 한 번만 가져오면 됩니다.

주의: 너무 일찍 prefetch하면 안 됨

prefetch(a[i+1][0])을 바깥 루프 처음(안쪽 루프 전)에 두면, 실제로 쓰기 전까지 A_i와 B0~B7, 9개 줄이 쓰입니다. A_(i+1)은 그동안 한 번도 안 쓰여서 LRU가 내보냅니다. 그러면 다시 미스가 나므로, 쓰기 직전 20 cycles 시점에 가져와야 합니다.

(b) 답: line 3에서 a, b 접근 미스 0번

참고: 쓸모없는 prefetch 몇 개 k = 7일 때 b[8][i]는 배열 b 바깥 주소이고, 다음에 필요한 B0는 ③에서 이미 가져옵니다. i = 7일 때 a[8][0], b[0][8]도 더 이상 필요 없는 데이터입니다.

2

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

• Indexing the cache to access the data portion takes 12ns • 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 8KB. Calculate the amount of time it takes to get data from the cache on a hit, including any needed TLB access time. Please explain your answers in detail to get the full credits.

각 프로그램은 자기 혼자 메모리 전체를 쓰는 것처럼 보이는 가짜 주소(가상 주소)를 써요. 하드웨어와 OS가 이 주소를 실제 메모리 위치(물리 주소)로 바꿔 줘요.

비유하면 이래요. 프로그램은 "내 방 101호"라고만 알고 있고, 그 방이 건물 어디에 있는지는 관리인(OS)이 장부(페이지 테이블)를 보고 찾아 줘요. 다른 프로그램도 “101호”를 쓰지만, 실제로는 서로 다른 방이에요.

1. The Limits of Physical Addressing

물리 주소를 그대로 쓰면 생기는 문제

• 모든 프로그램이 같은 메모리 공간을 같이 써요. 그래서 다른 프로그램의 데이터를 덮어쓸 수 있어요.
• 프로그램이 컴퓨터의 메모리 구조를 알고 있어야 해요. 어느 주소가 비어 있는지 알아야 하니까요.
• 프로그램이 실제 메모리보다 클 수 없어요.

2. Evolution of Virtual Memory

1. Originally -- one computer; one program

① 컴퓨터 한 대에 프로그램 하나 한 프로그램이 컴퓨터를 통째로 써요. 남는 메모리는 낭비되고, I/O를 기다리는 동안 CPU는 놀아요.

2. one computer, several programs

컴퓨터 한 대에 프로그램 여러 개 -한 프로그램이 I/O를 기다리는 동안 다른 프로그램을 돌려서 CPU를 계속 일하게 해요. 새로운 문제는 단편화(fragmentation) 예요.

메모리:  [Job1][빈 10KB][Job2][빈 15KB][Job3][빈 10KB]
                ↑                ↑               ↑
         빈 공간 합계 = 35KB인데...

Job 5 (30KB 필요) → 연속된 30KB가 없어서 못 들어감!

빈 공간이 충분해도 여기저기 쪼개져 있으면 못 써요. 프로그램은 연속된 공간이 필요하니까요.

3. Base / Bound 레지스터

• Base: 프로그램이 쓰는 모든 주소에 base 값을 더해요. 그래서 프로그램은 항상 0번지부터 시작한다고 생각하면 되고, 실제 위치는 base만 바꾸면 옮길 수 있어요.
• Bound: 프로그램이 쓸 수 있는 크기예요. 이 범위를 넘으면 예외(exception)를 일으켜서 다른 프로그램을 보호해요.

  물리 주소 = Base + 프로그램이 쓴 주소
  조건:      프로그램이 쓴 주소 < Bound  (넘으면 예외)

  
• 단편화는 압축(compaction) 으로 해결해요. 프로그램들을 한쪽으로 밀어서 빈 공간을 하나로 모으는 거예요. base만 바꾸면 되니까 프로그램은 옮겨진 걸 몰라요.

4. 그래도 남는 문제

• 압축할 때 메모리를 통째로 복사해야 해서 느려요.
• 프로그램이 실제 메모리보다 크면, 프로그래머가 직접 쪼개서 필요할 때 넣었다 뺐다 해야 해요. 이걸 오버레이(overlay) 라고 해요. 엄청 귀찮고 실수하기 쉬워요.

3. Solution: Add a Layer of Indirection

해결책: 가상 메모리 = "중간에 한 단계 더 끼워 넣기" 프로그램은 가상 주소만 쓰고, 중간의 주소 변환(address translation) 이 실제 위치를 찾아 줘요.

• User programs run in an virtual address space
• Address Translation maps virtual address to physical memory

장점

Address Renaming in the Memory Hierarchy

Programmer sees address hierarchy:

• Registers
• “Memory”
• Files
• Messages

Machine hides hardware details:

• Virtual to physical memory mapping
• File / virtual address to disk sector # mapping
• Messaging destination to IP address/routing information

4. Page 고정크기로 자르기

메모리를 같은 크기의 조각(페이지, 보통 4KB) 으로 잘라요.

Virtual Memory uses Mapped Pages

• Memory space is treated as a set of pages that may be arbitrarily distributed among main memory and swap space
• Fixed size pages eliminate memory fragmentation
• No need for compacting and cost of copying memory blocks
• Base+Bound registers replaced with mapping tables (page tables)

가상 메모리 (프로그램이 보는 것)      물리 메모리 (실제)
  페이지 0  ──────────────┐         ┌── 프레임 0: 다른 프로그램
  페이지 1  ────────┐     │         │   프레임 1: 페이지 1 ◀─┘
  페이지 2  ──┐     │     └────────▶│   프레임 2: 페이지 0
  페이지 3  ─ │ ─ ─ │ ─ ─ ─ ─ ▶ 디스크 (swap)
              └─────│────────────▶│   프레임 3: 페이지 2

가상으로는 연속이지만, 실제로는 아무 데나 흩어져 있어도 돼요. 크기가 다 같으니까 빈 칸 아무 데나 넣으면 돼요. 그래서 단편화가 없고 압축도 필요 없어요. base/bound 레지스터 대신 페이지 테이블이 "페이지 몇 번이 어디 있나"를 기록해요.

5. Four Memory Hierarchy Question for Virtual Memory

6. Format of Page Table Entry

페이지 하나당 한 줄씩 있어요.

┌────────────────────┬───────┬───────┬────────────┬────────────┐
│ 주소 (물리 프레임      │ Valid │ Dirty │ Referenced │ Protection │
│  번호 or 디스크 주소)  │       │       │            │            │
└────────────────────┴───────┴───────┴────────────┴────────────┘

7.주소 변환 방법

• Pointer to location of page in memory
• Or, if page is swapped, can be disk address instead

가상 주소:  [  가상 페이지 번호 (VPN)  |  오프셋 (offset)  ]
                       │                      │
                 페이지 테이블에서              그대로 복사
                 찾아서 바꿈                     │
                       ▼                      ▼
물리 주소:  [  물리 프레임 번호 (PFN)  |  오프셋 (offset)  ]

• 오프셋: 페이지 안에서의 위치. 페이지 크기로 결정돼요. 4KB = 2^12 → 12비트
• VPN: 나머지 비트. 이걸 페이지 테이블에서 찾아서 물리 프레임 번호로 바꿔요.

Control bits

• Valid/Present bit » If set, page being pointed to is resident in memory
• Modified/dirty bit » Set if at least one word in page has been modified » If not, don’t need to write to disk when replaced
• Referenced bit » Set if page has been referenced (with either read or write) » Used to support software replacement policies
• Protection bits » Used to restrict access » For example, read-only access, or system-only access

1-Level Direct Page Table Translation

1-Level Table Simple, but Limited

For large virtual address spaces can grow very large

• lpha 21164 has 43-bit virtual address, how many page table entries? Assume each entry is 8B, the page size is 8KB.
• Impractical today -- that’s a substantial part of a disk drive just for the page table
• Multi-level page tables

계산 공식 (시험에 자주 나와요)

오프셋 비트 수   = log2(페이지 크기)
VPN 비트 수     = 가상 주소 비트 수 − 오프셋 비트 수
PTE 개수        = 2^(VPN 비트 수)
페이지 테이블 크기 = PTE 개수 × PTE 하나 크기

글에 있는 문제: Alpha 21164 (43비트 가상 주소, 8KB 페이지, PTE 8B)

오프셋 = log2(8KB) = 13비트
VPN   = 43 − 13 = 30비트
PTE 개수 = 2^30 ≈ 10억 개
테이블 크기 = 2^30 × 8B = 2^33 B = 8 GB  ← 프로그램 하나당!

프로그램 하나 돌리려고 페이지 테이블에만 8GB가 필요해요. 말이 안 되죠. 그래서 다음 방법이 필요해요.

8. 2-Level Page Table

다단계(Multi-level) 페이지 테이블

핵심 아이디어: 대부분의 프로그램은 가상 주소 공간의 아주 일부만 써요. 그러니까 쓰는 부분의 테이블만 만들어요.

32비트, 4KB 페이지, PTE 4B인 x86의 고전적인 방식이에요.

32비트 가상 주소:  [ 10비트 | 10비트 | 12비트 ]
                      │        │        └ 오프셋 (4KB 페이지 안 위치)
                      │        └ 2단계: 페이지 테이블 번호
                      └ 1단계: 페이지 디렉토리 번호

페이지 디렉토리 (1024칸)
 ┌─────┐
 │  0  │──▶ 페이지 테이블 A (1024칸) ──▶ 실제 페이지
 │  1  │    (없음: 이 4MB 영역은 안 씀 → 테이블 안 만듦!)
 │ ... │
 │1023 │──▶ 페이지 테이블 B (1024칸) ──▶ 실제 페이지 (스택)
 └─────┘

단계 테이블 한 칸이 4MB 영역을 담당해요 (1024개 페이지 × 4KB). 그 영역을 안 쓰면 2단계 테이블을 아예 안 만들어요.

절약 효과: 코드(아래쪽)와 스택(위쪽)만 쓰는 작은 프로그램이라면

1단계 방식: 2^20 × 4B = 4 MB 2단계 방식: 디렉토리 1개(4KB) + 테이블 2개(8KB) = 12 KB

단점: 주소 하나를 변환하려면 테이블을 두 번 읽어야 해요. 그래서 다음 내용으로 TLB(변환 결과를 저장하는 캐시)가 나올 거예요.

Only page directory & active page tables need to be in main memory

• Page tables can be one page in size – uniform paging mechanism for virtual memory management

Can scale up with 3-level scheme and keep page directory size small

Example -- Alpha: say an 8 KB page holds 1K directory entries

• 1 level: 1K page table = 8 MB
• 2 levels: 1K page directory * 1K page tables = 8 GB
• 3 levels: 1K page directory * 1K intermediate directories * 1K page tables= 8 TB = 2^43

+알파

32비트 머신 vs 64비트 머신

"몇 비트"가 뜻하는 것

CPU가 한 번에 다루는 데이터 크기예요. 주로 범용 레지스터의 폭을 말해요. 그리고 포인터(메모리 주소)의 크기도 정해요. 이게 가상 메모리와 직접 연결돼요.

주소가 n비트면, 가리킬 수 있는 주소는 2^n개

32 비트 머신

2^32 = 4,294,967,296 바이트 = 4 GB

• 프로그램 하나가 볼 수 있는 가상 주소 공간이 최대 4GB예요.
• 이 4GB도 OS 커널과 나눠 써요. 예를 들어 Linux는 사용자 3GB와 커널 1GB, Windows는 기본으로 2GB씩 나눠요. 그래서 프로그램이 실제로 쓸 수 있는 건 2~3GB예요.
• 물리 메모리를 4GB보다 많이 꽂아도 기본적으로는 못 써요. PAE라는 기술로 물리 메모리를 늘릴 수는 있지만, 프로그램 하나당 4GB 한계는 그대로예요.
• 포인터는 4바이트예요.
• 페이지 테이블은 위에서 본 2단계 (10 | 10 | 12) 로 충분해요.

64비트 머신

2^64 = 16 EB (엑사바이트) = 약 160억 GB

• 이론상 엄청나게 크지만, 실제로는 64비트를 다 쓰지 않아요.
  • x86-64 (Intel, AMD)와 ARM64 (Apple Silicon 포함)는 보통 48비트 → 2^48 = 256 TB
  • 최신 서버 CPU는 57비트까지 지원해요 (128 PB).
  • 글에 나온 Alpha 21164도 64비트 CPU인데 43비트만 썼어요 (8 TB).
• 왜 다 안 쓸까? 페이지 테이블 때문이에요. 비트가 많을수록 테이블 단계가 늘어나서 변환이 느려져요. 그리고 256TB면 아직 충분해요.
• 포인터는 8바이트예요.

64비트에서는 페이지 테이블이 더 큰 문제예요

48비트, 4KB 페이지, PTE 8B로 1단계 테이블을 만들면:

VPN = 48 − 12 = 36비트
테이블 크기 = 2^36 × 8B = 512 GB  ← 프로그램 하나당!

그래서 4단계 테이블을 써요.

48비트 가상 주소:  [ 9 | 9 | 9 | 9 | 12 ]
                    1단계 2단계 3단계 4단계  오프셋

각 단계 테이블 = 2^9 = 512칸 × 8B = 4KB = 딱 페이지 1개 크기

재밌는 공통점: 단계 수를 정하는 규칙이 같아요. 테이블 하나가 딱 페이지 하나 크기가 되도록 나눠요.

Will be on Exam

Ex 1

For the code below, (1) determine which accesses are likely to cause data cache misses. Assume we have an 8KB direct-mapped data cache with 16-byte blocks. The elements of a and b are 8 bytes long. There are 3 rows and 100 columns for a and 101 rows and 3 columns for b. They are not in the cache at the start of the program. Ignore the potential capacity and conflict misses. The array is stored in row order.

for(i=0; i<3; i++)
    for(j=0; j<100; j++)
        a[i][j] = b[j][0] * b[j+1][0];

Ex 2

Applying the software prefetching technique to reduce cache misses, assume the prefetching has no benefit until the eighth iteration. Calculate the number of prefetch instructions executed and the misses avoided by prefetching.

for(j=0; j<100; j++) {
    prefetch(b[j+7][0]);
    prefetch(a[0][j+7]);
    a[0][j]= b[j][0] * b [j+1][0]; }

for(i=1; i<3; i++)
    for(j=0; j<100; j++) {
        prefetch(a[i][j+7]);
        a[i][j] = b[j][0] * b[j+1][0];}

1. 문제에서 주는 가정

• 프리페치는 7칸 앞(j+7)의 데이터를 요청해요.
• “eighth iteration까지는 효과가 없다”는 말은, 1번째 반복(j=0)에 요청한 데이터가 8번째 반복(j=7)부터 쓸모 있다는 뜻이에요. 데이터가 도착하는 데 시간이 걸리기 때문이에요.
• 그래서 처음 7번의 반복(j = 0~6)에서 쓰는 데이터는 미리 못 가져와요. 이 데이터는 프리페치 대상(j+7 = 7부터 시작)에 한 번도 들어가지 않아서, 원래대로 미스가 나요.

2. 루프를 둘로 나눈 이유

Ex 1에서 b는 i = 0일 때 전부 캐시에 들어오고, i = 1, 2에서는 모두 히트였어요.

• 첫 번째 루프 (i = 0): b와 a 둘 다 처음 보는 데이터예요. 그래서 둘 다 프리페치해요.
• 두 번째 루프 (i = 1, 2): b는 이미 캐시에 있어요. b를 또 프리페치하면 명령어 비용만 들어서, a만 프리페치해요.

3. 프리페치 명령어 수

조건문이 없어서 블록이 이미 캐시에 있어도 매 반복 실행돼요. 그래서 반복 횟수 × 명령어 개수로 그대로 세면 돼요.

4. 남는 미스 계산

첫 번째 루프 (i = 0)

• b: b[0][0] ~ b[6][0], 원소 7개는 프리페치되지 않아요. b[j][0]마다 블록이 다르니까(Ex 1에서 본 24바이트 간격) 미스 7번이에요.
• a: a[0][0] ~ a[0][6], 원소 7개가 프리페치되지 않아요. 블록 하나에 2개씩 들어가니까 블록 수로 세요.

Ex 3

Calculate the time saved. Ignore I-cache misses and assume there are no conflict or capacity misses in D-cache. Assume that prefetches can overlap with each other and with cache misses. Here are the key loop times ignoring cache misses: the original loop takes 7 cycles per iteration, the first prefetch loop takes 9 cycles per iteration, and the second prefetch loop takes 8 cycles per iteration (including the overhead of the outer for loop). A miss takes 100 cycles.

계산 방법

전체 시간 = (반복 횟수 × 반복당 사이클) + (미스 횟수 × 100)

반복당 사이클은 미스가 없을 때의 시간이에요. 미스가 나면 100사이클씩 더해요.

가정이 뜻하는 것

• I-cache 미스 무시, 용량·충돌 미스 없음: Ex 1, Ex 2에서 센 미스(251, 19)를 그대로 쓰면 돼요.
• 프리페치끼리, 그리고 미스와도 겹칠 수 있음: 프리페치가 메모리에서 데이터를 가져오는 시간은 따로 더하지 않아요. 프리페치 명령어를 실행하는 비용은 이미 반복당 사이클(9, 8)에 들어 있어요. 원래 루프가 7사이클인데 9, 8사이클로 늘어난 게 바로 그 비용이에요.

프리페치 명령어 때문에 400사이클이 늘었지만, 미스가 줄어서 23,200사이클이 줄었어요. 앞에서 본 "비용 < 이득" 조건이 실제 숫자로 나온 거예요. 미스 한 번(100사이클)이 프리페치 명령어 하나(약 1사이클)보다 훨씬 비싸서 이득이 커요.

시험 팁: “time saved”를 물으면 22,800 사이클, “speedup”을 물으면 6.2배로 답하면 돼요. 미스 19번을 루프별로 11번과 8번으로 나누는 것이 가장 실수하기 쉬운 부분이에요.

No need for programmer or compiler intervention No changes to existing executables Take advantage of run-time information

앞 글의 프리페칭은 프로그래머나 컴파일러가 "이거 미리 가져와" 하고 코드에 넣는 방식이었어요. 하드웨어 프리페칭은 CPU가 실행 중에 메모리 접근 패턴을 지켜보다가 알아서 미리 가져오는 방식이에요.

프로그램을 고칠 필요가 없어요. 이미 만들어진 실행 파일도 그대로 빨라져요. 실행 중에 실제로 일어나는 일을 보고 예측해요.

Major design questions

• What to prefetch? » Next sequential cache line(s), strided patterns, …
• When to prefetch? » On an access (prefetch always), on a miss (prefetch on miss), when other prefetched data used (tagged prefetch)
• Where to place prefetched data » In the cache or in a special prefetch buffer
• How to handle VM exceptions? » Don’t prefetch beyond a page

Tagged prefetch: 미리 가져온 블록에 표시(tag)를 해 둬요. 그 블록이 처음 쓰이는 순간 "이 예측이 맞았네" 하고 다음 블록을 가져와요. 실제로 쓰이는 속도에 맞춰 한 발씩 앞서가는 방식이에요.

페이지를 넘지 않는 이유: 가상 메모리에서 바로 다음 페이지가 실제 메모리에서도 옆에 있다는 보장이 없어요. 아예 할당이 안 돼 있을 수도 있어요. 함부로 넘어가면 엉뚱한 데이터를 가져오거나 페이지 폴트를 일으킬 수 있어요.

1. Simple Sequential Prefetching

미스가 나면 그 다음 블록 하나도 같이 가져와요.

• On a cache miss, fetch one sequential memory block

    - Exploits spatial locality in both instructions & data

• Mimic behavior of larger cache line size without really do it
• Extend to fetching N sequential memory blocks
• Fixed vs. dynamic number of blocks for prefetching

블록 A에서 미스 → A를 가져오면서 A+1도 미리 가져옴
→ 프로그램이 A+1을 쓸 때 이미 와 있음 (미스 없음)

효과는 블록 크기를 키운 것과 비슷해요. 하지만 실제 블록 크기는 그대로라서, 큰 블록의 단점(블록 개수가 줄어드는 것)은 없어요.

인텔은 이걸 “Adjacent Cache Line Prefetch”라고 불러요. 한 번에 N개를 가져오도록 늘릴 수도 있어요. N은 고정일 수도 있고, 상황에 따라 바뀔 수도 있어요.

Pros:

• No changes to executables
• Simple hardware

Cons:

• Only applies for good spatial locality
• Works poorly for nonsequential accesses
• Unnecessary prefetches for array accesses with large stride

2. Stream Prefetching

문제: 미스가 났을 때 N개를 한꺼번에 가져오면, N개를 다 쓰고 나서 또 미스가 나요. N블록마다 한 번씩 멈추는 셈이에요.

해결: 미리 가져온 블록이 하나 쓰일 때마다 하나를 더 가져와서, 항상 N개 앞서 있게 해요. 이걸 위한 별도 공간이 스트림 버퍼예요.

Sequential prefetching problem

• Performance slows down once every N cache lines

Stream prefetching is a continuous version of prefetching

• Stream buffer can fit N cache lines
• On a miss, start fetching N sequential cache lines
• On a stream buffer hit: Move cache line to cache, start fetching line (N+1) In other words, stream buffer tries to stay N cache lines ahead

Design issues

• When is a stream buffer allocated
• When is a stream buffer released

동작 예시 (N = 4)

① A에서 캐시 미스
   → A는 캐시로, A+1 ~ A+4는 스트림 버퍼로 가져오기 시작
   스트림 버퍼: [A+1][A+2][A+3][A+4]   (도착 전엔 "아직 안 옴" 표시)

② 프로그램이 A+1 요청 → 캐시엔 없지만 스트림 버퍼에 있음!
   → 1사이클 만에 캐시로 옮김, 나머지 한 칸씩 앞으로, 빈자리에 A+5 가져오기
   스트림 버퍼: [A+2][A+3][A+4][A+5]

③ A+2 요청 → 또 버퍼에서 → [A+3][A+4][A+5][A+6]  ... 계속 4개 앞서감

④ 갑자기 전혀 다른 주소 Z에서 미스 (순서가 끊김)
   → 버퍼를 비우고 Z부터 다시 시작: [Z+1][Z+2][Z+3][Z+4]

왜 캐시가 아니라 별도 버퍼에 넣을까? 예측이 틀리면 쓸데없는 데이터가 캐시의 좋은 데이터를 밀어내요(캐시 오염). 버퍼에 두면 실제로 쓰일 때만 캐시로 들어가니 안전해요. 각 칸에는 "데이터 도착함/아직" 표시(available bit)가 있어요. 요청한 블록이 아직 오는 중이면 기다려요.

비유: 회전초밥 레일에 다음 접시 4개를 항상 올려 두는 것. 하나 집으면 하나를 새로 올려요. 손님이 갑자기 다른 메뉴를 시키면 레일을 비우고 새 메뉴로 채워요.

3. Prefetching with Arbitrary Strides

마지막 단점을 해결하는 방법이에요. 루프에서는 같은 명령어가 매번 일정한 간격으로 떨어진 주소를 읽는 경우가 많아요.

같은 명령어가 읽은 주소: 1000 → 1400 → 1800 → 2200 ...
                         (+400)  (+400)  (+400)   ← 간격 D = 400

• Employ special logic to monitor the processor’s address referencing pattern
• Detect constant stride array references originating from looping structures
• Compare successive addresses used by load or store instructions

동작 원리

명령어 mi가 반복할 때마다 주소 a1, a2, a3…를 읽는다고 해요.

1. a1, a2를 보고 간격 D = a2 − a1을 계산해요. D가 0이 아니면 프리페치를 시작해요.
2. 다음 주소를 a3 = a2 + D로 예측하고 미리 가져와요.
3. 예측이 계속 맞으면 a4 = a3 + D, … 이렇게 이어가요. 예측이 틀리면 멈춰요.

순차 프리페칭과의 차이: 순차는 "바로 옆"만 가져오지만, stride는 얼마나 건너뛰는지 학습해서 정확히 그 위치를 가져와요.

4. Reference Prediction Table (RPT)

stride 프리페칭을 실제로 구현하는 표예요. 명령어마다 한 줄씩, 그 명령어의 접근 패턴을 기록해요.

Hold information for the most recently used memory instructions to predict their access pattern

• Address of the memory instruction
• Previous address accessed by the instruction
• Stride value
• State field

Organization of RPT

it's not in the Final test but it's used alot in industry

Example

float a[100][100], b[100][100], c[100][100];
    for (i = 0; i < 100; i++)
        for (j = 0; j < 100; j++)
            for (k = 0; k < 100; k++)
                a[i][j] += b[i][k] * c[k][j]

예를 들어 b가 주소 50000, c가 90000, a가 10000에서 시작한다고 하면 RPT는 이렇게 변해요.

1회차: b: 이전=50000  stride=0    initial     (처음 봄)
       c: 이전=90000  stride=0    initial
       a: 이전=10000  stride=0    initial

2회차: b: 이전=50004  stride=4    transient   (간격 4 발견, 확인 중)
       c: 이전=90400  stride=400  transient   (간격 400 발견)
       a: 이전=10000  stride=0    steady      (같은 주소 → 간격 0이 맞음)

3회차: b: 이전=50008  stride=4    steady  → 50012 미리 가져옴
       c: 이전=90800  stride=400  steady  → 91200 미리 가져옴

핵심은 명령어(PC)별로 따로 기록한다는 점이에요. 그래서 b, c처럼 간격이 서로 다른 접근이 섞여 있어도 각각 정확히 예측할 수 있어요.

Software Prefetching

for (i=0; i<N; i++) {
    prefetch(a[i+8]); // 8번 뒤에 쓸 a를 지금 미리 요청
    prefetch(b[i+8]); // b도 마찬가지
    sum += a[i]*b[i]; // 지금 계산은 이미 와 있는 데이터로
}

Doesn’t have to be correct!
prefetch(N+8);

프로그래머나 컴파일러가 “8번 뒤에 쓸 데이터를 지금 가져와 둬” 라고 코드에 직접 넣는 방식이에요. 앞 글의 하드웨어 프리페칭과 반대예요.

왜 8번 뒤일까? 메모리에서 데이터가 오는 데 시간이 걸리니까, 그 시간 동안 루프가 몇 번 돌지 계산해서 정해요. 지금 요청하면 8번 돌고 나서 도착하는 셈이라, 그때 쓸 데이터를 지금 요청하는 거예요.

“Doesn’t have to be correct!”의 의미 루프 끝부분에서는 a[N+7]처럼 배열 범위를 벗어난 주소를 프리페치해요. 그래도 괜찮아요. 프리페치는 "가능하면 가져와 줘"라는 힌트일 뿐이라서, 틀려도 결과는 바뀌지 않고 대역폭만 조금 낭비돼요. 일반 load였다면 프로그램이 죽을 수도 있는 주소예요.

Data Prefetch

• Register Prefetch: load data int register
• Cache Prefetch: load into cache
• Special prefetching instructions cannot cause faults. The addr does not cause an exception (e.g. page fault)
• Requires nonblocking cache

Issuing Prefetch Instructions takes time

• Is cost of prefetch issues < savings in reduced misses?

프리페치 명령어가 갖춰야 할 조건

• 예외(fault)를 일으키면 안 돼요. 잘못된 주소나 아직 메모리에 없는 페이지를 가리켜도 페이지 폴트 없이 그냥 무시돼야 해요. 그래서 "틀려도 된다"가 가능한 거예요.
• 논블로킹 캐시(nonblocking cache)가 필요해요. 프리페치한 데이터가 오는 동안에도 캐시가 다른 load 요청을 계속 처리할 수 있어야 해요. 캐시가 프리페치를 기다리느라 멈춰 버리면, 미리 가져오는 의미가 없어요.

비용 문제

프리페치도 명령어라서 실행하는 데 시간이 걸려요. 그래서 따져봐야 해요.

프리페치 명령어 실행 비용 < 줄어든 미스로 아끼는 시간 이어야 이득

예를 들어 이미 캐시에 있는 데이터를 프리페치하면 시간만 날려요. 아래 Ex 1에서 이게 중요해져요.

Your computer's memory (RAM) is like a huge row of tiny boxes:

 box #:   1000  1001  1002  1003  1004  1005  1006  1007  ...
        ┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
        │     │     │    │     │    │     │    │     │ ...
        └─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘

• Each box holds 1 byte, a very small piece of data.
• Each box has a number called its address, like a house number on a street.

Everything in your program (numbers, arrays, text) is stored in these boxes.

Step 2: Variables and types

When you write

int a = 12;

you are telling the computer: "Reserve some boxes, call them a, and put the number 12 in them."

The type (int here) answers two questions:

1. How many boxes (bytes) to reserve
2. What kind of value is stored there

Use double when you need more accuracy, as in scientific computing. The cost is that it uses 8 bytes instead of 4.

int a = 12;     →  [ 4 boxes ]
double d = 3.14 →  [ 8 boxes ]

Step 3: sizeof, which asks how many bytes something takes

sizeof tells you the size of a type or variable in bytes:

sizeof(int)     // 4
sizeof(float)   // 4
sizeof(double)  // 8

Why not just type the number 8 yourself? Because sizes can differ between computers, and sizeof(double) is clearer than a bare 8. It says what you mean, and it is always correct for the machine you're on.

Step 4: Arrays are many boxes in a row

float x[9];

This reserves 9 floats side by side:

 index:    0    1    2    3    4    5    6    7    8
        ┌────┬────┬────┬────┬────┬────┬────┬────┬────┐
 x:     │    │    │   │    │   │    │    │    │   │
        └────┴────┴────┴────┴────┴────┴────┴────┴────┘
          4B   4B   4B   4B   4B   4B   4B   4B   4B    
        → total 9 × 4 = 36 bytes

Step 5: Pointers are variables that hold an address

A pointer doesn't hold a normal value. It holds the address of another piece of memory.

Think of a sticky note with a locker number written on it. The note isn't the locker; it just tells you where the locker is.

double* p;   // p is a pointer: it can hold the address of a double

The * after the type means "pointer to". So double* means "address of a double".

On a 64-bit computer, every pointer is 8 bytes, no matter what it points to, because an address is always the same size.

      p (8 bytes)                       somewhere else in memory
  ┌──────────────┐                     ┌────────────────────┐
  │  addr: 5000 │ ──── points to ───→ │   3.14  (double)  │ ← at box #5000
  └──────────────┘                     └────────────────────┘

Step 6: Stack and heap, the two places memory comes from

Memory for your program comes from two main areas:

Stack: your function's desk

• Ordinary variables declared inside a function go here: int a;, float x[9];
• Automatic. When the function ends, everything on its stack is cleaned up.
• The size must be known when you write the code (e.g. exactly 9 floats).
• Small (typically 1–8 MB total).

Heap: a big warehouse

• You ask for space while the program is running, using malloc.
• Stays until you return it with free. Nothing is cleaned up automatically.
• Can be very large, and the size can be decided at runtime.
• The warehouse gives you an address to the space, which you store in a pointer.

Step 7: malloc, which asks the heap for memory

malloc stands for memory allocate. You tell it how many bytes you want, and it:

1. Reserves that many bytes on the heap
2. Gives you back the address of the first byte

Here is the line from your homework, taken apart piece by piece:

double* y = (double*) malloc(sizeof(double) * 10);

The result looks like this:

   STACK                               HEAP
  ┌───────────────┐                   ┌────┬────┬────┬────┬────┬────┬────┬────┬────┬────┐
  │ y (8 bytes)  │ ───────────────→   │ d0 │ d1 │ d2│ d3 │ d4 │ d5│ d6 │ d7 │ d8│ d9 │
  │ holds address│                   └────┴────┴────┴────┴────┴────┴────┴────┴────┴────┘
  └───────────────┘                     10 doubles × 8 bytes = 80 bytes

When you're done, give the memory back:

free(y);

왜 x 칸이 2000개야? 앞에 코드는 n이 2000 이라 했고, malloc으로 heap이 16000인거잖아

맞아요, malloc이 heap에서 받아온 건 16,000 바이트예요. 그런데 x가 double*라서 그 공간을 8바이트씩 묶어서 한 칸으로 써요.

16,000 바이트 ÷ 8 바이트(double 한 개) = 2000 칸

Instructions

• Reorder procedures in memory so as to reduce conflict misses, without affecting correctness
• Profiling to look at conflicts(using tools they developed)
• Entry point of basic block at the beginning of a block
• Branch straightening

Data

1. Merging Arrays: improve spatial locality by single array of compound elements vs. 2 arrays
2. Loop Interchange: change nesting of loops to access data in order stored in memory
3. Loop Fusion: Combine 2 independent loops that have same looping and some variables overlap
4. Blocking: Improve temporal locality by accessing “blocks” of data repeatedly vs. going down whole columns or rows

1. Merging Arrays

// Before: 2 sequential arrays //
int val[SIZE];
int key[SIZE];

//After: 1 array of stuctures //
struct merge {
    int val;
    int key;
};

struct merge merged_array[SIZE];

Reducing conflicts between val & key (they might conflict for a single block in the cache); improve spatial locality when they are accessed in a interleaved fashion

Colum order:

store first colum, then second colum, then third….

Example:
– 6x6 array A
– Each element 1 word
– Block size: 4 word
– For i=1 to 6; X+= a[1,i]; how many blocks are loaded into cache

For final you need to know how many misses in this pic and prof will give the code

Row order:

store first row, then second row, then third….

Example:
– 6x6 array A
– Each element 1 word
– Block size: 4 word
– For i=1 to 6; X+= a[1,i]; how many blocks are loaded into cach

2. Loop Interchange Example

Assume the array storage is in row order

for (k = 0; k < 100; k = k+1)
    for (j = 0; j < 100; j = j+1)
        for (i = 0; i < 5000; i = i+1)
            x[i][j] = 2 * x[i][j];

/* After */
for (k = 0; k < 100; k = k+1)
    for (i = 0; i < 5000; i = i+1)
        for (j = 0; j < 100; j = j+1)
            x[i][j] = 2 * x[i][j];

• Sequential accesses instead of striding through memory every 100 words; improved spatial locality

3. Loop Fusion Example

/* Before */
for (i = 0; i < N; i = i+1)
    for (j = 0; j < N; j = j+1)
        a[i][j] = 1/b[i][j] * c[i][j];

for (i = 0; i < N; i = i+1)
    for (j = 0; j < N; j = j+1)
        d[i][j] = a[i][j] + c[i][j];

• Many programs have separate loops that operate on the same data
• Combining these loops allows a program to take advantage of temporal locality by grouping operations on the same (cached) data together.

 /* After */
for (i = 0; i < N; i = i+1)
    for (j = 0; j < N; j = j+1)
        { a[i][j] = 1/b[i][j] * c[i][j];
          d[i][j] = a[i][j] + c[i][j];}

• 2 misses per access to a & c vs. one miss per access; improve temporal locality

4. Blocking

행렬 곱셈처럼 큰 데이터를 쓰는 작업에서, 행이나 열을 끝까지 쭉 훑지 않고 캐시에 쏙 들어가는 작은 정사각형 조각(블록) 을 하나 정해요. 그 조각을 여러 번 다 쓴 다음에 다음 조각으로 넘어가요.

비유: 시험공부할 때 책 10권을 동시에 펴서 한 줄씩 왔다 갔다 하지 않고, 한 챕터를 책상에 펴 놓고 끝낸 뒤 다음 챕터로 가는 것.

Prefetching

Idea: fetch data into the cache before processors request them

• Can address cold misses
• Can be done by the programmer, compiler, or hardware

필요해지기 전에 미리 캐시로 가져오는 것이에요. 프로그래머, 컴파일러, 하드웨어 누구든 할 수 있어요. 처음 쓰는 데이터라서 어차피 나는 미스(cold miss)도 막을 수 있어요.

Characteristics of ideal prefetching

You only prefetch data that are truly needed
- Avoid bandwidth waste

You issue prefetch requests early enough
- To hide the memory latency

You don’t issue prefetch requests too early
- To avoid cache pollution

Prefetching relies on having extra memory bandwidth that can be used without penalty

Prefetching Terminology

• Prefetch Hit: Prefetched line that was hit in the cache before being replaced (miss avoided)
• Prefetch Miss: Prefetched line that was replaced before being accessed
• Prefetch Rate: Prefetches per instruction (or 1000inst.) Accuracy: Percentage of prefetch hits to all prefetches
• Coverage: Percentage of misses avoided due to prefetching 100 x (Prefetch Hits / (Prefetch Hits + Cache Misses))

Classification of Prefetched Lines

Useful Prefetch

• Prefetch hit before being replaced
• Results in avoiding a cache miss

Useless Prefetch

• Prefetch is replaced before being accessed (prefetch miss)
• Downside: Increases demand for cache bandwidth, power

Harmful Prefetch

• Prefetch is replaced before being accessed AND
• Prefetch replaces a line that is requested later (cache pollution)
• Results in an additional cache miss
• power

• CPU normally needs just one word of the block at a time. Don’t wait for full block before restarting CPU
• Early restart — As soon as the requested word of the block arrives, send it to the CPU and let the CPU continue execution
• Critical Word First —Request the missed word first from memory and send it to the CPU as soon as it arrives; let the CPU continue execution while filling the rest of the words in the block
• Long blocks more popular today -> Critical Word 1st Widely used

1-6 is not on EXAM

from now on it's in exame

2. Merging Write Buffers

A write buffer removes most of the time the CPU would otherwise spend waiting on writes. A merging write buffer (also called write merging) makes it more efficient still. The exercise at the end builds on both.

A. Why a write buffer?

With a write-through L1, every store must also be written to the next level (L2 or memory), which is slow. Without help, the CPU would wait on every store.

A write buffer is a small queue between L1 and the next level:

1. On a store, the address and data are placed in the write buffer.
2. From the CPU's point of view, the write is finished, so it continues right away.
3. The buffer sends its entries to the next level in the background, oldest first.

The CPU waits only when the buffer is full.

B. The three cases on your slide

C. Write merging: how it works

Write merging OFF

Write merging ON

Each buffer entry holds a whole block's worth of space, for example 4 words of 8 bytes, with a valid bit per word. When a new store arrives, the buffer checks: does a valid entry already cover this address?

• Yes: put the word into that entry and set its valid bit (merge).
• No: use a new entry.

Without merging, each store takes its own entry even when the stores are to neighboring addresses, so the buffer fills up quickly.

In the simulator below, the stores come faster than the buffer can drain. Run the same 9 stores with merging off, then on, and compare the stalls.

D. Why write merging helps (common exam question)

1. Fewer stalls. Neighboring stores share one entry, so the buffer fills up more slowly.
2. Fewer, more efficient writes to the next level. Sending one entry with 4 words uses the memory bus better than 4 separate one-word writes, since each transfer pays the setup cost only once.
3. Better use of buffer space. Without merging, each entry holds one word and the rest of its space is wasted.

Two more points worth knowing:

• Reads must check the write buffer. A load may want data that is still sitting in the buffer and not yet in L2. The cache either checks the buffer for a matching address or waits for the buffer to drain, so the load doesn't read a stale value.
• I/O addresses are not merged. Writes to device registers must each happen separately and in order.

Exercise: write time with a write-through L1

L1 is write-through. 95% of the time the store can go into the write buffer; 5% of the time the buffer is full. How do you compute the write time?

Step 1: Identify the two cases

Case A, buffer has space (95%): the store goes into L1 and the buffer, and the CPU continues. The time is just the L1 write time, the L1 hit time.

Case B, buffer is full (5%): the CPU must wait until an entry is written to L2 and freed. That wait is the time to write one entry into L2, including L2 misses:

T_L2write = hit time L2 + miss rate L2 × miss penalty L2

Step 2: Combine with the probabilities

Write time = 0.95 × T_L1  +  0.05 × (T_L1 + T_L2write)
           = T_L1 + 0.05 × T_L2write

Every store pays the L1 time, and 5% of stores also pay the full drain time.

If the question asks for stall time only (as in the earlier homework):

Write stall time = 0.95 × 0 + 0.05 × T_L2write

Step 3: Plug in numbers (from your earlier problem)

L1 hit time = 1 ns, L2 hit time = 15 ns, L2 local miss rate = 20%, L2 miss penalty = 150 ns.

T_L2write = 15 + 0.20 × 150 = 15 + 30 = 45 ns

Write time        = 1 + 0.05 × 45 = 1 + 2.25 = 3.25 ns
Write stall time  = 0.05 × 45     = 2.25 ns

Step 4: Exam traps

• Read the question for what to include. "Stall time only" → 2.25 ns. "Write time to L1" including the access → 3.25 ns. Show the formula so you get credit either way.

• The waiting time depends on the stated assumption. In your homework, the store arrives just as the buffer starts writing an entry to L2, so it waits the entire 45 ns. If a problem instead says a store arrives at a random point during the drain, the average wait would be about half of that. Use exactly what the problem states.

• The L1 miss rate is not used for writes when the L1 is write-through, no-write-allocate. Every store goes into the buffer whether it hits or misses in L1. If a problem says write-allocate, write misses would also pay an L1 miss penalty.

• Don't forget the L2 miss part of T_L2write. Using only the 15 ns L2 hit time (giving 0.05 × 15 = 0.75 ns) is a common mistake. L2 is write-allocate, so 20% of buffer writes miss in L2 and pay the 150 ns.

AMAT

The notes write miss_rate(RLL + %dirtyD), which means miss_rate × (RLL + %dirty × D).

The one idea behind every equation

AMAT = (time every access pays) + Σ (how often an extra event happens) × (how long it takes)

Every access pays its hit time (RH or WH). Then you ask which extra trips to the lower level this access can cause, and how often each one happens. There are only four possible trips:

1. Fetching a block (RLL). Happens when a miss brings the block into the cache. Reads always do this. Writes do it only with write-allocate. It happens only on misses, so it is multiplied by miss_rate.

2. Writing back a dirty victim (D). When a block is brought in, another is thrown out. Only write-back caches have dirty blocks, so D appears only for write-back, only inside the miss term, and only %dirty of the time.

3. Sending a write down (WLL).

• Write-through: every write goes down, hit or miss, so WLL is added without miss_rate.
• Write-back + no-write-allocate: hits stay in the cache, but a write miss goes straight down, so the term is miss_rate × WLL.

4. Write buffer → multiply each write-down cost by (1 − %wb). The buffer absorbs outgoing writes, so the CPU waits only when it is full. This applies to WLL and D only, never RLL. A buffer can hold data going out, but it can't make data come in faster.

Reads: only two versions

A read miss always brings the block in, whatever the write policy. Write-allocate vs. no-allocate decides what happens on write misses only, so it never changes the read formula. Only one thing matters for reads: can the replaced block be dirty?

Write-back + no-write-allocate still has the dirty term. No-allocate only means write misses don't bring blocks in. Write hits still mark blocks dirty, so a later read miss can evict a dirty block.

Writes: four versions, one at a time

Write-through + write-allocate: WH + WLL + miss_rate × RLL

• Every write goes to the cache (WH) and down to the lower level (WLL), hit or miss.
• On a write miss, the block is also fetched first (miss_rate × RLL), because of allocate.
• No D: write-through blocks are never dirty.

Write-through + no-write-allocate: WH + WLL

• Every write goes down (WLL), hit or miss.
• On a miss, the block is not fetched, and the write just goes down. That is the same WLL already counted, so a miss costs nothing extra and the formula has no miss_rate at all.

Write-back + write-allocate: WH + miss_rate × (RLL + %dirty × D)

• A write hit stays in the cache and marks the block dirty (just WH).
• A write miss behaves exactly like a read miss: fetch the block (RLL), possibly evicting a dirty victim (%dirty × D), then write into it.
• That's why it's identical to the write-back read formula, with WH in place of RH.

Write-back + no-write-allocate: WH + miss_rate × WLL

• A write hit stays in the cache (just WH).
• A write miss sends the write straight down (WLL) and does not fetch the block.
• No RLL (nothing fetched) and no D (nothing evicted).

Adding a write buffer: one rule

The write buffer only affects writes going down. Find every WLL and D term and multiply it by (1 − %wb). Leave RH, WH, and RLL alone.

That turns all 8 buffer formulas from your notes into the 8 non-buffer ones with one change each. For write-through reads nothing changes at all, since there is no WLL or D in them.

Where (1 − %wb) comes from: with probability %wb the write drops into the buffer and the CPU waits 0. With probability (1 − %wb) the buffer is full, and the CPU waits the whole write time:

%wb × 0 + (1 − %wb) × WLL = (1 − %wb) × WLL

Patterns to check your answer

*질문 ① *미스 때 블록을 가져오나? → miss_rate × RLL

• 읽기 미스는 항상 가져옴
• 쓰기 미스는 write-allocate일 때만 가져옴

*질문 ② *블록을 가져올 때, 밀려나는 블록이 dirty일 수 있나? → + %dirty × D (미스 항 안에)

• write-back일 때만 해당. write-through는 원본이 항상 최신이라 dirty가 없음

질문 ③ 쓰기가 아래로 내려가나? → WLL

• write-through: 쓰기마다 항상 → WLL (miss_rate를 곱하지 않음)
• write-back + no-allocate: 쓰기 미스일 때만 → miss_rate × WLL

*질문 ④ *쓰기 버퍼가 있나? → WLL과 D 앞에 (1 − %wb)

• 우편함에 자리가 있으면(%wb) 기다림 0, 꽉 차면(1 − %wb) 끝까지 기다림
• RLL에는 절대 붙이지 않음. 우편함은 "보내는 것"만 도와주고, "가져오는 것"은 빨라지게 못 함writes going down (WLL, D), never RLL.

Write through + write allocate
- Read AMAT = RH + miss_rate*RLL
- Write AMAT= WH + WLL + miss_rate*RLL

Write through + no write allocate
- Read AMAT = RH + miss_rate*RLL
- Write AMAT = WH + WLL

Write back + write allocate
- Read AMAT = RH + miss_rate*(RLL+%dirty*D)
- Write AMAT = WH + miss_rate*(RLL+%dirty*D)

Write back + no write allocate
- Read AMAT = RH + miss_rate*(RLL+%dirty*D)
- Write AMAT = WH + miss_rate*WLL

Write through + write allocate + write buffer
- Read AMAT = RH + miss_rate*RLL
- Write AMAT= WH + (1-%wb)*WLL + miss_rate*RLL

Write through + no write allocate + write buffer
- Read AMAT = RH + miss_rate*RLL
- Write AMAT = WH + (1-%wb)* WLL

Write back + write allocate + write buffer
- Read AMAT = RH + miss_rate*(RLL+%dirty* (1-%wb)* D)
- Write AMAT = WH + miss_rate*(RLL+%dirty* (1-%wb)* D)

Write back + no write allocate + write buffer
- Read AMAT = RH + miss_rate*(RLL+% dirty* (1-%wb)* D)
- Write AMAT = WH + miss_rate* (1-%wb)* WLL

The memory system for this computer has a split L1 cache. Both the I-cache and the D-cache are direct mapped and hold 32 KB each. The I-cache has a 2% miss rate and 64 byte blocks, and the D-cache is a write-through, no-write-allocate cache with a 5% miss rate and 64 byte blocks. The hit time for both the Icache and the D-cache is 1ns. The L1 cache has a write buffer. 95% of writes to L1 find a free entry in the write buffer immediately. The other 5% of the writes have to wait until an entry frees up in the write buffer (assume that such writes arrive just as the write buffer initiates a request to L2 to free up its entry and the entry is not freed up until the L2 is done with the request). The processor is stalled on a write until a free write buffer entry is available.

The L2 cache is a unified write-back, write-allocate cache with a total size of 512 KB and a block size of 64-bytes. The hit time of the L2 cache is 15ns. Note that this is also the time taken to write a word to the L2 cache. The local hit rate of the L2 cache is 80%. Also, 50% of all L2 cache blocks replaced are dirty. The 64-bit wide main memory has an access latency of 20ns (including the time for the request to reach from the L2 cache to the main memory, you can consider this is the initial setup time for a memory access), after which any number of bus words may be transferred at the rate of one bus word (64-bit) per bus cycle on the 64-bit wide 100 MHz main memory bus. Assume inclusion between the L1 and L2 caches and assume there is no write-back buffer at the L2 cache. Assume a write-back takes the same amount of time as an L2 read miss of the same size.

While calculating any time values (such as hit time, miss penalty, AMAT), please use ns (nanoseconds) as the unit of time. For miss rates below, give the local miss rate for that cache. By miss penaltyL2, we mean the time from the miss request issued by the L2 cache up to the time the data comes back to the L2 cache from main memory.

1. Computing the AMAT (average memory access time) for instruction accesses.

a. Give the values of the following terms for instruction accesses. hit timeL1, miss rateL1, hit timeL2, miss rateL2

only asked instruction accesss so doesn't need to care D-cache

b. Give the formula for calculating miss penaltyL2, and compute the value of miss penaltyL2.

1 + 0.02 (15+0.2 x 150) = 1.9ns 

step 1
Read the new block from memory (always).
Write back the old block that is being replaced, if it is dirty (sometimes).

step 2
Access latency = 20
Bus is 64 bits wide -> 8 bytes
Bus runs at 100 MHz -> 10ns CCT

How many transfers for one block?
Block size ÷ bus width = 64 bytes ÷ 8 bytes = 8 bus words

How long do those 8 transfers take?
8 bus words × 10 ns = 80 ns

Total to read one block:

Read time = latency + transfer time
          = 20 ns + 80 ns
          = 100 ns

MP L2 = [latency + (block size ÷ bus width) × bus cycle time] × (1 + fraction dirty)
                = [20 + (64 ÷ 8) × 10] × (1 + 0.5)
                = 100 × 1.5
                = 150 ns

c. Give the formula for calculating the AMAT for this system using the five terms whose values you computed above and any other values you need.

AMAT = hit time L1 + miss rate L1 × (hit time L2 + miss rate L2 × miss penalty L2)

d. Plug in the values into the AMAT formula above, and compute a numerical value for AMAT for instruction accesses.

AMAT = hit time L1 + miss rate L1 × (hit time L2 + miss rate L2 × miss penalty L2)

2. Computing the AMAT for data reads

a. Give the value of miss rate L1 for data reads.

miss rate L1 = 0.05 (5%), the D-cache's miss rate.

b. Calculate the value of the AMAT for data reads using the above value, and other values you need.

AMAT(data read) = 1 + 0.05 × (15 + 0.20 × 150)
                = 1 + 0.05 × 45
                = 1 + 2.25
                = 3.25 ns

3. Computing the AMAT for data writes.

First, look at the path a write takes. The D-cache is write-through and no-write-allocate, so every store, hit or miss, is placed in the write buffer. The buffer then writes it to L2 in the background. The 5% D-cache miss rate therefore does not affect writes: a write never waits for a block to be brought into L1.

a. Give the value of miss penaltyL2 for data writes.

A write reaching L2 that misses is handled the same way as a read miss. L2 is write-allocate, so it fetches the whole block from memory, and it is write-back, so the replaced block is dirty 50% of the time and must be written out first, with no write-back buffer.

miss penalty L2 (writes) = 150 ns, the same as for reads.

b. Give the value of write timeL2Buff for a write buffer entry being written to the L2 cache.

This is the time for one write-buffer entry to be written into L2, including the L2 misses:

write time L2Buff = hit time L2 + miss rate L2 × miss penalty L2
                  = 15 + 0.20 × 150
                  = 15 + 30
                  = 45 ns

write time L2Buff = 45 ns (15 ns is the given time to write a word into L2).

c. Calculate the value of the AMAT for data writes using the above two values, and any other values that you need. Only include the time that the processor will be stalled. Hint: There are two cases to be considered here depending upon whether the write buffer is full or not.

There are two cases:

Case 1: buffer has a free entry (95% of writes). The store goes into the buffer immediately and the processor continues. Stall = 0 ns.

Case 2: buffer is full (5% of writes). The problem says the write arrives just as the buffer starts sending an entry to L2, and that entry isn't free until L2 finishes. The processor waits the entire L2 write. Stall = 45 ns.

AMAT(data write) = 0.95 × 0 + 0.05 × 45
                 = 2.25 ns

AMAT for data writes = 2.25 ns

(Some instructors also count the 1 ns L1 write access in every case. That gives 0.95 × 1 + 0.05 × (1 + 45) = 3.25 ns. The problem says to include only stall time, so 2.25 ns is the intended answer.)

1. Pipelined caches

A. Pipelining

A processor's clock cycle can be no shorter than its slowest single step (the critical path). A cache access is one of the slowest steps: decode the index, read the arrays, compare tags, select the data. If the whole access has to fit in one cycle, it limits the clock speed of the entire CPU.

The idea: split the cache access into stages

Pipelining the cache works like an assembly line. The access is cut into stages, for example index → read → tag compare → data out, with latches between them. Each stage is short, so the clock can be faster. A new access can enter the cache every cycle, while earlier ones are still in later stages.

Two things change, and it's important to keep them apart:

• Bandwidth goes up: more accesses finish per nanosecond, one per (shorter) cycle.
• Latency does not improve: each access still takes about the same real time, a little more because of latch overhead. Measured in cycles, a hit now takes k cycles instead of 1.

1stage

2stages

3stages

4stages

What to notice as you go from 1 to 4 stages:

The clock cycle shrinks, from about 2.1 ns to 0.6 ns, so the whole CPU can run faster. Bandwidth more than triples, because a new load starts every cycle. Hit latency in real time rises slightly, from 2.1 ns to 2.4 ns, because each latch adds overhead. Pipelining never makes a single access faster. Hit latency in cycles grows from 1 to 4, which is where the costs come from.

Each step allowed a much higher clock rate. The Pentium 4 was designed for very high GHz, which is why it pipelined the cache (and everything else) so deeply.

The two costs in your notes

1. More cycles between issuing a load and using its data (load-use delay) With a 4-cycle hit, an instruction that needs the loaded value must wait extra cycles, the yellow "wait" boxes in the widget:

   lw   r1, 0(r2)     # load, takes k cycles
   add  r3, r1, r4    # needs r1, so it stalls k-1 cycles

   The processor hides this by doing independent work in the gap. The compiler schedules other instructions between the load and its use, or out-of-order execution (which the Pentium Pro introduced) runs later instructions that don't depend on the load. If there's nothing independent to run, the stall shows up.

2. Greater penalty on mispredicted branches The instruction cache is pipelined too, so fetching instructions takes more stages, and the whole CPU pipeline gets longer. When a branch is mispredicted, every instruction fetched after it is wrong and must be thrown away, and the pipeline must refill from the correct address. More stages mean more wasted cycles per mistake. On a very deep pipeline like the Pentium 4's, this penalty is large, so good branch prediction becomes essential.

Pipelining the cache trades latency in cycles for higher clock rate and bandwidth. It pays off when the processor can keep the pipeline full with independent instructions and correct branch predictions, and it hurts when it can't.

B. Miss Status Handling Register (MSHR)

The bookkeeping hardware: MSHRs

A Miss Status Handling Register (MSHR) records one outstanding miss. There is one MSHR per cache block being fetched, and inside it a small list of every load and store waiting for that block.

Fields of one MSHR:

Fields of each load/store entry:

Two kinds of misses use these:

Primary miss: the first miss to a block. A new MSHR is allocated and a memory request is sent. Secondary miss: a later miss to a block that is already being fetched. No new request is sent; an entry is added to the existing MSHR. How it operates, step by step

Use Next to walk through a sequence of accesses. The cache has 2 MSHRs, each with room for 3 waiting loads or stores, and 64-byte blocks.

The operation rules from your slide, matched to the walkthrough On a cache miss:

1. Search the MSHRs for the same block address.

   • Found (secondary miss, step 3): just add a new load/store entry to that MSHR. No new memory request is sent.
   • Not found (primary miss, steps 1 and 4): allocate a free MSHR, write the block address and the first load/store entry, and send the request to memory (Issued = 1).

2. If no MSHR is free, or the MSHR's entries are full, stall (step 5). The number of MSHRs sets how many misses can overlap.

When one word (or sub-block) of the line arrives (steps 6 and 7):

1. Check which entries are waiting for that word, using their block offsets.
2. Forward the data to the CPU. A load writes its destination register; a store merges its store-buffer data into the block.
3. Mark those entries invalid.
4. Write the word into the cache.

When the last word of the line arrives (step 8):

• Mark the MSHR invalid, so it is free for the next miss.

2. Nonblocking caches

A non-blocking cache (also called lockup-free) keeps working while it waits for a miss. The idea starts with what the CPU can do during a miss.

Why it's useful: out-of-order execution

An in-order CPU must stop when a load misses, because the next instruction may need that data. An out-of-order CPU can look ahead and run later instructions that don't depend on the missing data. Many of those are also loads and stores, so they need the data cache.

With a normal blocking cache, the cache refuses all requests until the miss is resolved. The CPU has independent work ready, but the cache won't serve it, so the CPU sits idle anyway.

A non-blocking cache keeps serving requests during a miss. The timeline below shows four loads: A (miss), B (hit), C (miss), D (hit). A hit takes 1 cycle, and a miss takes 10.

Three levels of non-blocking

Blocking: while A is missing, the cache ignores every request. B and D are hits, but they still have to wait.

Hit under miss: the cache serves hits while one miss is pending. B and D no longer wait for A. A second miss (C) still stalls the cache until A finishes, because only one miss can be tracked at a time.

Miss under miss (hit under multiple miss): the cache tracks several misses at once, so C's memory request is sent while A's is still in progress. Their waiting times overlap, and that gives the biggest saving.

The miss penalty for each individual miss doesn't change; A still takes 10 cycles. What drops is the effective miss penalty, the time the CPU actually loses, because useful work and other misses fill the waiting time.

The costs (from your notes):

• More complex cache controller. It must track many outstanding misses at once, remember which loads and stores are waiting for each one, and deliver data to the right place when it returns.

• The lower level must accept several requests at once. If memory can handle only one request at a time, the second miss waits anyway. That's why memory is split into multiple banks, so different misses can be served by different banks in parallel.

3. Multibanked caches

A banked cache is split into several independent pieces (banks), and each bank can serve its own access in the same cycle. Here is what that means and how addresses are spread across the banks.

The problem: one cache, one access at a time A cache built as a single block of memory can handle one access per cycle. That becomes a bottleneck when many requests arrive together:

• An out-of-order CPU may issue several loads and stores per cycle.
• A non-blocking cache (the previous topic) has misses returning while new hits are being served.
• A multicore/multithreaded chip has many cores sharing one L2.

The solution: split the cache into independent banks Divide the cache into several banks. Each bank has its own decoder and data array, so it can do its own access. If four requests go to four different banks, all four are served in the same cycle, giving four times the bandwidth.

Example: Sun T1 ("Niagara"). This chip has 8 cores running 32 threads, all sharing one L2. A single-ported L2 would be swamped, so it is split into 4 banks that work in parallel.

Which address goes to which bank? Sequential interleaving Banking helps only if requests spread out across the banks. If they all land in the same bank, they must wait in line, which is called a bank conflict.

The simple mapping from your notes spreads consecutive blocks across banks in rotation:

bank number      = block address mod (number of banks)
position in bank = block address ÷ (number of banks)

With 4 banks, blocks 0, 1, 2, 3 go to banks 0, 1, 2, 3, then block 4 wraps back to bank 0, and so on. Since programs often access neighboring blocks (arrays, instruction streams), consecutive requests naturally hit different banks.

To get the block address from a byte address, divide by the block size first. For example, with 64-byte blocks, byte address 448 → block 448 ÷ 64 = 7 → bank 7 mod 4 = bank 3.

Pick an access pattern below (or click blocks to choose your own) and see how many cycles it takes to serve the requests.

The patterns show the point from your notes, that the address-to-bank mapping decides how well banking works. Sequential accesses spread out perfectly. Strides that are a multiple of the number of banks (like stride 4 with 4 banks) all pile into one bank and lose the whole benefit. That's why some designs use a hashed mapping (for example, XOR-ing some address bits) to break up such patterns.

Don't confuse ways and banks

Both split a cache into parts, but for different reasons:

Reducing Hit Time

Hit time is the time to find data that is in the cache: use the index to pick a set, read its tag(s) and data, compare tags, then choose the right block and send it to the CPU. Both techniques here make that path shorter.

1. Small and Simple Caches

Small helps because a smaller memory array has shorter wires and fewer rows to decode, so indexing and reading are faster. This is why L1 size often stays flat across processor generations (as in the AMD K6, Athlon, Opteron example). Making L1 bigger would slow every access, and hit time sets the clock cycle.

Simple (direct-mapped) helps because each address has only one possible location. The cache can send the data to the CPU right away, while the tag check runs in parallel. If the tag turns out not to match, the data is thrown away. A set-associative cache can't do this. It must finish all its tag comparisons before the multiplexer knows which way's data to send.

2. Way Prediction

The problem it solves

There are two options, and each has a weakness:

Direct-mapped: fast hit, because there is one possible location and the data can be sent before the tag check finishes. But it has more conflict misses. 4-way set-associative: fewer conflict misses, but slower hit, because it must compare 4 tags and then use the mux to choose the data.

Way prediction keeps the set-associative cache, and its low miss rate, but guesses which way holds the data. If the guess is right, the access behaves like a direct-mapped one.

"Use load PC or XOR the load src reg and load offset to index the prediction table" The prediction table is a small memory that remembers which way each load found its data in last time. It has to give an answer before the cache access starts, but the real memory address (base register + offset) isn't finished computing yet. So the table is indexed by something available earlier:

• the PC of the load instruction. The same load instruction tends to hit the same way again, for example inside a loop.
• or base register XOR offset, a quick stand-in for the address. XOR has no carry chain, so it's much faster than the full addition.

correct prediction

Wrong way, hit elsewhere

Miss in all ways

Random access(85% accurate)

With 85% accuracy, most hits run at direct-mapped speed. You can estimate the average hit time like this:

Average hit time ≈ 0.85 × 1 cycle + 0.15 × 2 cycles = 1.15 cycles

The miss rate stays that of a 4-way cache, because every way is still checked before declaring a miss. Only the order of checking changes.

"Any other benefit of way prediction?" — power savings

If you click random a few times, the average tag compares per access drops far below 4. A normal 4-way cache powers up all 4 tag comparators and reads all 4 data blocks on every access, then throws away 3 of them. With way prediction, a correct guess needs only 1 tag compare and 1 data array read. That is roughly a quarter of the dynamic energy per access in a 4-way cache. The saving matters a lot in L1 caches, which are accessed almost every cycle, and in battery-powered chips. Some designs go further with way selection: they read the data array of only the predicted way.

Example

just read, not in the exame

(a) For a 1024 KB L2 cache with 64-byte blocks and 8-way set associativity, how many way prediction table entries are needed?

1024 KB, 64-byte blocks, 8-way
Blocks = 1024 KB ÷ 64 B = 2²⁰ ÷ 2⁶ = 2¹⁴ = 16,384 blocks
Sets = 16,384 ÷ 8 = 2¹¹ = 2,048 sets
Bits per entry = log₂ 8 = 3 bits
Answer: 2,048 entries, each 3 bits, for a total of 2,048 × 3 = 6,144 bits (6 Kb).

(b) For an 8 MB L2 cache with 128-byte blocks and 2-way set associativity, how many way prediction table entries are needed?

(b) 8 MB, 128-byte blocks, 2-way
Blocks = 8 MB ÷ 128 B = 2²³ ÷ 2⁷ = 2¹⁶ = 65,536 blocks
Sets = 65,536 ÷ 2 = 2¹⁵ = 32,768 sets
Bits per entry = log₂ 2 = 1 bit

Answer: 32,768 entries, each 1 bit, for a total of 32,768 bits (32 Kb).

(c) What is the difference in the way that the processor with only 8Kb way prediction table will support the cache in part (a) versus the cache in part (b)?

Cache (a) is fully supported. 6,144 bits fits in 8,192, so every one of the 2,048 sets gets its own 3-bit predictor, with about 2 Kb left unused. Prediction accuracy is as good as the predictor allows.

Cache (b) is only partially supported. The table can hold only 8,192 one-bit entries, but there are 32,768 sets. The table is indexed with only the low 13 bits of the 15-bit set index, so 4 different sets share each entry (aliasing). When those sets are used in the same period and their blocks sit in different ways, they overwrite each other's prediction. This causes more mispredictions, and each one costs an extra cycle to check the other way, so the average hit time rises.

The cache still works correctly in (b). A prediction is only a hint, and the tag comparison always checks it. A wrong guess costs time, not correctness.

If your course means "8K entries" rather than 8K bits, the conclusion is the same. Cache (a) needs only 2,048 of the 8,192 entries (with 3-bit entries), so it fits. Cache (b) needs 32,768 entries, so each entry is still shared by 4 sets.

• Victim cache holds data that has been deleted from the cache, in case it is needed again
• This is fully associative cache and can help to reduce misses with direct-mapped or set associative caches

A victim cache is a small buffer that sits between a cache and the next level of the memory hierarchy. It catches blocks the main cache has just evicted, so that if the processor asks for one of them again soon, it can be recovered quickly instead of fetched from the slower level below.

How it works

1. On a cache miss, the CPU looks in the main cache and, at the same time (or on the very next step), in the victim cache.

2. If the block is in the victim cache (a victim hit), it is swapped with the block currently occupying that line in the main cache. The evicted block goes into the victim cache, and the requested block moves into the main cache. The penalty is only a cycle or two, far less than going to L2 or memory.

3. If it misses in both, the block is fetched from the next level and placed in the main cache. Whatever it displaces is moved into the victim cache, pushing out the oldest entry (typically FIFO or LRU replacement).

So blocks flow one way in the normal case: main cache → victim cache → discarded. The swap on a victim hit is the exception.

Key properties

• Small: typically 4 to 16 entries, each holding a full cache block.
• Fully associative: any evicted block can go in any entry, and lookups compare against all tags in parallel. That is only affordable because it is so small.
• Holds only evicted blocks: it is not filled directly from memory, so it complements the main cache rather than duplicating it.
• Exclusive in spirit: a block lives in either the main cache or the victim cache, not both, thanks to the swap.

The three cases to remember:

• Main cache hit: normal fast path, nothing else happens.
• Main miss, victim hit: swap the two blocks, so the requested block moves into the main cache and the evicted one takes its place in the victim cache.
• Miss in both: fetch from the next level into the main cache, and the displaced block goes into the victim cache (the oldest victim entry is dropped if it's full).

only after update victim cache evict

RLL = Read from Lower Level (fetching a block from memory) and WLL = Write to Lower Level (sending data down to memory). These are the two kinds of memory traffic that write policies and victim caches change. If your course defines them differently, tell me and I'll adjust.

The four policy terms

Two separate questions decide how a cache handles writes:

1. On a write hit, when does memory get updated?

• Write-back (WB): only the cache is updated, and the block is marked dirty. Memory is updated later, when the dirty block is evicted.
• Write-through (WT): the cache and memory are both updated on every write. Blocks are never dirty.

2. On a write miss, do we bring the block into the cache?

• Write-allocate (WA): yes. Read the block from memory (an RLL), then write it in the cache.
• No-write-allocate (NWA): no. Send the write straight to memory (a WLL) and leave the cache unchanged.

These are usually paired. Write-back and write-allocate go together because both try to do writes in the cache instead of in memory, and allocating means a later write to the same block will be a hit. Write-through works naturally with no-write-allocate: every write goes to memory anyway, so loading the block on a write miss gains little

Where the victim cache fits

The victim cache sits between the main cache and memory and catches evicted blocks. Whether those blocks are dirty depends on the write policy:

With WB-WA: evicted blocks may be dirty, so each victim-cache entry needs its own dirty bit. The victim cache becomes a waiting area for dirty data. A dirty block goes to memory (WLL) only when it is pushed out of the victim cache. If it is reused first, the write-back never happens. With WT-NWA: every block is clean, because memory is always up to date. A block leaving the victim cache is simply discarded, with no WLL. The victim cache saves only reads (RLLs).

In both policies, a victim-cache hit is a swap. It saves an RLL, and in WB it can also save a WLL.

Pick a policy and a situation below to see which paths are used and how many RLLs and WLLs happen.

Takeaways for exams

• WB-WA pays for writes lazily. Repeated writes to one block cost zero WLL until that block finally leaves the victim cache. The victim cache gives dirty blocks a second chance, so it can save both RLLs and WLLs.

• WT-NWA pays one WLL on every write, hit or miss, and its victim cache can only save RLLs. In return, memory is always up to date and evictions are free. Real designs add a write buffer so the CPU doesn't stall waiting for each WLL.

• In both policies, a WB-WA write miss costs an RLL (allocate), while a WT-NWA write miss costs a WLL (bypass).

• Large last-level caches are often managed the same way. L3 is sometimes run as a victim cache, filled only with lines displaced from L2 (for example, AMD Barcelona and Apple A9). Handling dirty lines is a key design issue there too.

Vdd -> Capacitor -> Gnd

Dynamic power

• capacitance swithcing
• crowbar current

Static power

• Leakage current

relation with energy and delay

Low swing circuit idea: let's change unitil vdd/3 so that we can save power cons:

• we can not use normal gate
• weak at noise, can not tolerate noise, noise sensitive

Gated clocks

• stop the clock and put the logic to sleep
• put the and gate with enable signal

Increase length of transistors

• but sacrifice speed

Two NMOS are connected as shown here. What mode of operation (cutoff, linear, saturation) is M2 in? Vt for both MOS is 0.6V. Useful info: The side with the arrow is the source side, Cutoff: Vgs<Vt, Linear: Vgs>Vt & Vds<Vgs-Vt, Saturation: Vgs>Vt & Vds>Vgs-Vt)

2.

For some application, it is desired that the high-to-low transition must be high speed while the low-to high transition is of little consequence. What change(s) will you make to your inverter to account for this requirement?

3.

Implement the Pull-down-network (PDN) only, for the function:

No need to size.

4.

For a new Technology, it was determined that 1:2 sizing is optimal(Not 2:1). with this new information. size your design from Q3.

5.

Given the following PDN (Assume that there is also a complementary PUN, that is not showed here), what will be the output(0 or 1) when inputs are

a. (A,B,C,D,E) = (1,1,0,0,0): Output:0 b. (A,B,C,D,E) = (1,0,1,0,1): Output:0 c. (A,B,C,D,E) = (1,0,1,1,0): Output:1

6.

Between a 2-input NAND and 2-input NOR, which will consume more dynamic power and why (voltage, and frequency are equal in both cases, the output of both gates is connected to 2:1 inverters)? (Useful info: Paynamic = aCV'f, a: Switching factor, C: load capacitance, V: Voltage, f; frequency)

The NOR gate requires larger PMOS transistors because its PMOS devices are connected in series, which increases the switched capacitance and therefore increases dynamic power.

7.

What is the logical (LE) for a 2-input NAND and 2 input NOR gate if 3:1 sizing is followd in a new technology. Useful info: LE is the ratio of the input capacitance of a given gate to that of an inverter after sizing.

8.

Fill up the truth table for the following circuit. What function is being implemented?

differently. $\boxed{\text{L1: optimize for speed}}$

$\boxed{\text{L2: optimize for capacity + lower miss rate}}$

That one idea explains most of the differences in your slide.

1. Cache Size

L1 is normally small because it must be accessed very quickly. Example: $L1=32KB$ $L2=512KB$

$\text{Small cache} \rightarrow \text{faster}$

$\text{Large cache} \rightarrow \text{lower miss rate, but slower}$

2. Number of Sets

Remember:

$\boxed{#Sets= \frac{CacheSize}{BlockSize\times Associativity}}$

Example: L1:

$32KB,\ 64B,\ 4\text{-way}$

$Sets= \frac{32768}{64\times4} = 128$

L2:

$512KB,\ 64B,\ 8\text{-way}$

$Sets= \frac{524288}{64\times8} = 1024$

So L2 usually has many more sets. The number of sets affects the address:

$\boxed{IndexBits=\log_2(Sets)}$

3. Associativity

Associativity tells us how many cache lines are inside each set.

• Direct mapped = 1-way
• 2-way = 2 cache lines per set
• 4-way = 4 cache lines per set
• 8-way = 8 cache lines per set

Higher associativity usually reduces conflict misses because a memory block has more possible locations inside its set.

However, higher associativity also means:

• more tag comparisons
• more hardware
• potentially longer hit time So L1 often uses relatively modest associativity because hit time is very important. L2 can often use higher associativity because reducing misses is more important there.

4. Block Size

A block is the amount of data transferred between memory levels at one time. Typical examples:

• 32B
• 64B
• 128B A larger block can help because of spatial locality. If the CPU accesses one address, it may soon access nearby addresses, so bringing nearby data together can reduce compulsory misses. However, a larger block also has disadvantages:
• larger miss penalty
• more transfer time
• fewer cache lines for the same cache capacity
• possibly more capacity or conflict misses if the block becomes too large So block size is a trade-off.

5. Split Cache vs Unified Cache

L1 is commonly split into:

• L1 instruction cache
• L1 data cache

The instruction cache stores instructions. The data cache stores data used by loads and stores. The reason for splitting them is bandwidth.

The CPU may need to do both of these in the same cycle:

• fetch an instruction
• access data With separate caches, both accesses can happen at the same time. So:
• instruction fetch → L1 I-cache
• load/store → L1 D-cache L2 is commonly unified. That means instructions and data share the same L2 capacity. This allows the space to be used more flexibly. In general:
• L1 → often split
• L2 → usually unified
• L3 → usually unified

6. Multiple Ports

A cache port is an access path into the cache. A single-port cache can usually handle only one access at a time. If a unified cache must handle both:

• instruction fetch
• data access in the same cycle, one access may have to wait. This is why some problems say a load/store requires one extra cycle in a single-port unified cache. A split L1 cache naturally reduces this conflict because instruction and data accesses use different caches.

7. Which Usually Has a Higher Miss Rate: I-cache or D-cache?

Usually:

$\text{D-cache miss rate} > \text{I-cache miss rate}$

Instruction accesses often have strong spatial and temporal locality. For example, instructions are frequently executed sequentially:

• instruction 100
• instruction 101
• instruction 102
• instruction 103 Loops also repeatedly execute the same instructions. Data accesses can be much more irregular. Examples:
• pointer chasing
• linked lists
• hash tables
• random array accesses So D-cache often has a higher miss rate. This is workload-dependent, though.

8. Write-Through vs Write-Back

This mainly matters for data caches. Write-Through When the CPU writes data, both the cache and the next memory level are updated immediately. Advantages:

• simpler consistency
• memory is always up to date Disadvantages:
• more memory traffic
• potentially slower writes Write-Back The CPU writes only to the cache first. The cache line is marked dirty. When that line is later evicted, the modified data is written to the next memory level. Advantages:
• less lower-level memory traffic
• usually better performance Disadvantages:
• more complex
• requires dirty-bit management Modern high-performance data caches commonly use write-back.

9. Replacement Policy

In a set-associative cache, a set may become full. Suppose a 4-way set already contains four blocks. If a new block must enter that set, one old block must be removed. The replacement policy decides which one. Common policies include:

• LRU
• Pseudo-LRU
• FIFO
• Random L1 often prefers simpler policies because access speed is critical. L2 may use more sophisticated policies because reducing misses is more important.

10. Inclusive Cache

In an inclusive hierarchy, every block in L1 must also exist in L2. Conceptually:

$L1 \subseteq L2$

Example:
L1 contains:
- A
- B
- C
L2 contains:
- A
- B
- C
- D
- E

Advantages:

• can simplify some coherence and tracking mechanisms Disadvantages:
• duplicate copies use cache capacity

11. Exclusive Cache

In an exclusive hierarchy, the same block is generally kept in only one cache level at a time.

Example:
L1 contains:
- A
- B
- C
L2 contains:
- D
- E
- F
- G

Advantage:

• better effective total cache capacity Disadvantage:
• more complicated movement of blocks between levels

12. Non-Inclusive / Non-Exclusive

Some processors use neither a strictly inclusive nor strictly exclusive policy. A block may exist in multiple cache levels, but it is not required to. This gives the cache hierarchy more flexibility.

13. L3 Cache

Modern processors often also include L3 cache. The hierarchy becomes: CPU → L1 → L2 → L3 → DRAM Typical trend:

• L1: smallest and fastest
• L2: larger and slower
• L3: much larger and slower
• DRAM: largest but much slower The main purpose of L3 is to reduce expensive DRAM accesses. In multicore processors, L3 is often shared by multiple cores.

L1 vs L2 Summary

The main design principle is:

$\text{L1: optimize for speed}$

$\text{L2/L3: optimize more for capacity and miss-rate reduction}$

1. Multi-Level Caches
2. Victim Caches

1. Multi-level Caches

There is a trade-off between the size of the cache and the access time

• Small caches are faster but cannot hold much data, therefore having larger miss rate

• Large caches can hold enough data but are slower, thus increasing hit time

• We can add another, smaller cache (L1) between the current cache (L2) and the CPU

• Since everything that is in L1 is also in L2, it only makes sense to add L2 if it is much bigger than L1

The CPU checks L1 first. If L1 misses, it checks L2. If L2 also misses, it accesses main memory.

We now have local and global miss rate

• Local miss rate is number of misses in the given cache level divided by number of accesses to this level and it is equal to Miss_RateL1 for L1 and Miss_RateL2 for L2

• Global miss rate is the number of misses in the given cache level divided by total number of accesses generated by the CPU. It is equal to Miss_RateL1 for L1, but it is Miss_RateL1*Miss_RateL2 for L2

Average Memory Stalls/Instruction

$\boxed{\frac{Average Memory Stalls}{Instruction}=(\text{Misses/Inst}{L1})(HT{L2}) + (\text{Misses/Inst}{L2})(MP{L2})}$

Example 1

Assume that in 1000 memory references there are 40 misses in L1 cache and 20 misses in L2 cache. Assume the miss penalty for L2 is 200 clock cycles, hit time of L2 is 10 clock cycles, hit time of L1 is 1 clock cycle and there are 1.5 memory references per instruction. What are the average memory access time and the average memory stalls per instruction?

Example 2

Given the data below, what is the impact of second-level cache associativity on its miss penalty:

• Hit time for direct mapped L2 is 10 clock cycles
• Two-way associativity increases hit time by 0.1 clock cycles to 10.1 clock cycles
• Local miss rate in L2 for direct mapped is 25%
• Local miss rate in L2 for two-way set associative is 20%
• Miss penalty for L2 is 200 clock cycles

Block: 1 cache line stores 1 block Cache line = one cell Block = the data stored inside that cell Block size = how many bytes that cell stores

1.

Assume we are using 32-bit address. L1 cache is direct mapped and size is 16KB, block size is 32B. L2 cache is 8-way set associative and size is 4MB, block size is 64B. Draw the cache access diagram for L1 and L2 cache respectively, and indicate the size of all fields (in bits) and the size of L1 and L2 caches (in number of blocks they can hold). You may use the Lec5-slide8 as a reference.

2.

You have split caches (a 32KB instruction cache and a 32KB data cache) with the following specifications:

• Hit time is 1 clock cycle and miss penalty is 100 cycles
• There are 38.4 misses per 1000 instructions for 32KB data cache, and 1.36 misses per 1000 instructions for 32KB instruction cache.

Assume 40% of instructions are data transfer instructions, CPI is 1 when all memory accesses hit in the cache.

(a) What is the overall average memory access time for the split caches?

(b) What is the overall average memory stalls per instruction for the split caches?

(c) What is the overall CPUtime (expressed as function of IC - instruction count)?

3.

You have a two-level cache with the following specifications:

• L1 is 64KB direct-mapped with 32B blocks. Hit time is 1ns and local miss rate L1 is 5%
• L2 is 1MB 4-way set-associative with 128B blocks. Hit time is 20ns and global miss rateL2 is 2%
• Penalty to fetch block from memory to L2 is 60ns

What is the average memory access time?