Caches III: Direct Mapped

Assistant

Teaching Professor

Lisa Yan

CS61C

Great Ideas

in

Computer Architecture

(a.k.a. Machine Structures)

cs61c.org

Head TA

Nicolas Reed

Yan, SP26

28-Caches III: Direct Mapped (1)

​

Great Idea #3: Principle of Locality / Memory Hierarchy

Storage Latency Analogy: How Far Away is the Data?

Jim Gray�1998 Turing Award

B.S. Cal 1966

Ph.D. Cal 1969

On-chip cache

Yan, SP26

28-Caches III: Direct Mapped (2)

​

Line Replacement Policies

Agenda

• Line Replacement Policies
• Write Policies
• Direct Mapped Cache
• Direct Mapped Cache Analysis

—

• Types of Misses

Yan, SP26

28-Caches III: Direct Mapped (3)

​

Fully Associative Cache with LRU policy

• By the end of instr 5, cache is warm.
• Load byte 0x43F 0x10F,0x3
• Load byte 0x5E2 0x178,0x2
• Load word 0x824 0x209,0x0
• Load word 0x5E0 0x178,0x0
• Load word 0x524 0x149,0x0
• Load byte 0x972 0x25C,0x2

Suppose that LRU = 0 means most recently used, and 3 means least recently used.

After the end of instruction 5, what are the LRU tags on each row?

Yan, SP26

28-Caches III: Direct Mapped (4)

​

A Warmed up Cache Can Still Miss

• By the end of instr 5, cache is warm.
• Load byte 0x43F 0x10F,0x3
• Load byte 0x5E2 0x178,0x2
• Load word 0x824 0x209,0x0
• Load word 0x5E0 0x178,0x0
• Load word 0x524 0x149,0x0
• Load byte 0x972 0x25C,0x2

1. Cache miss!
2. Load into cache the 4-byte line from 0x970 to 0x973. Mark valid bit. Update line replacement policy fields (e.g., LRU).

c. Read byte at 0x2 offset, return to processor.

Yan, SP26

28-Caches III: Direct Mapped (5)

​

Line Replacement Policies

• Least Recently Used (LRU)
• Replace the entry that has not been�used for the longest time,�i.e., has the oldest previous access.
• Pro: Temporal locality!
• recent past use implies likely future use
• Con: Complicated hardware to keep track of access history
• In practice: First In, First Out (FIFO)
• Replace the oldest line in the set (“queue”).

​

• Other policies (see in notes):
• Most Recently Used (MRU)
• Random
• Last In, First Out (LIFO) - “stack”

LRU is ideal for temporal locality but in practice, FIFO is good enough.

Yan, SP26

28-Caches III: Direct Mapped (6)

​

Cache Design: Placement Policies, Soon

Yan, SP26

28-Caches III: Direct Mapped (7)

​

Write Policies

Agenda

• Line Replacement Policies
• Write Policies
• Direct Mapped Cache
• Direct Mapped Cache Analysis

—

• Types of Misses

Yan, SP26

28-Caches III: Direct Mapped (8)

​

Stores: How to write back to memory?

• By the end of instr 5, cache is warm.
• Load byte 0x43F 0x10F,0x3
• Load byte 0x5E2 0x178,0x2
• Load word 0x824 0x209,0x0
• Load word 0x5E0 0x178,0x0
• Load word 0x524 0x149,0x0
• Load byte 0x972 0x25C,0x2
• Store byte 0x524 0x149,0x0

Cache hit! …and then?

How to handle stores?

Yan, SP26

28-Caches III: Direct Mapped (9)

​

Write-through vs. Write-back Policies

• Store instructions write to memory, which changes values.
• Hardware needs to ensure that cache and memory “sync” their data.

• Write-through:
• Write to the cache and memory at the same time.�
• Write-back:
• Write data in cache for now.
• When this line gets replaced from the cache�(and “back” to memory), write to memory.

Store byte 0x524(0x149,0x0)

Yan, SP26

28-Caches III: Direct Mapped (10)

​

What does Write-Back Look Like? Dirty Bit

• Write-back:
• Write data in cache and set a dirty bit to 1.
• When this line gets replaced from the cache�(and “back” to memory), write to memory.
• Fully Associative Cache w/ LRU, Write-Back

Cache hit w/write-back:

update cache line, and wait until this line is replaced before writing back to memory

​

Store byte 0x524(0x149,0x0)

Yan, SP26

28-Caches III: Direct Mapped (11)

​

Write-through vs. Write-back Policies

• Write-through:
• Write to the cache and memory at the same time.
• (more writes to memory → longer AMAT)
• Write-back:
• Write data in cache and set a dirty bit to 1.
• When this line gets replaced from the cache�(and “back” to memory), write to memory.

Store byte 0x524(0x149,0x0)

Write policies have tradeoffs:

simple to implement

(typically) lower traffic to memory

Yan, SP26

28-Caches III: Direct Mapped (12)

​

Direct Mapped Cache

Agenda

• Line Replacement Policies
• Write Policies
• Direct Mapped Cache
• Direct Mapped Cache Analysis

—

• Types of Misses

Yan, SP26

28-Caches III: Direct Mapped (13)

​

Cache Design: Placement Policies

Fully associative caches need expensive hardware.

Yan, SP26

28-Caches III: Direct Mapped (14)

​

Direct Mapped Cache

• Placement policy: The data at a memory address can be stored at exactly one possible line in the cache.

How do we identify this location from the memory address?

Yan, SP26

28-Caches III: Direct Mapped (15)

​

Direct Mapped Cache

• Placement policy: The data at a memory address can be stored at exactly one possible line in the cache.

tag to connect line to memory address

index to select line in cache

byte offset within line

Example: 0x61B

0

1

2

3

indices

Yan, SP26

28-Caches III: Direct Mapped (16)

​

Direct Mapped Caches: 4B Cache

• 4B Direct Mapped Cache�(line size 1B)

Line starting… maps to… has tag…

• @ 0x0 index 0 000000
• @ 0x1 index 1 000000
• @ 0x2 index 2 000000
• @ 0x3 index 3 000000

0x

(assume 8 bit address)

Yan, SP26

28-Caches III: Direct Mapped (17)

​

Direct Mapped Caches: 4B Cache

• 4B Direct Mapped Cache�(line size 1B)

Line starting… maps to… has tag…

• @ 0x0 index 0 000000
• @ 0x1 index 1 000000
• @ 0x2 index 2 000000
• @ 0x3 index 3 000000
• @ 0x4 index 0 000001
• @ 0x8 index 0 000010
• @ 0xC index 0 000011
• etc.

0x

Lines with same line index replace each other.

Yan, SP26

28-Caches III: Direct Mapped (18)

​

Direct Mapped Caches: 8B Cache

• 8B Direct Mapped Cache�(line size 2B)

Line starting… maps to… has tag…

• @ 0x0 index 0 00000
• @ 0x2 index 1 00000
• @ 0x4 index 2 00000
• @ 0x6 index 3 00000
• @ 0x8 index 0 00001
• @ 0x10 index 0 00010
• @ 0x18 index 0 00011
• etc.

0x

Tag: 00000

Yan, SP26

28-Caches III: Direct Mapped (19)

​

Direct Mapped Caches: 16B Cache

• 16B Direct Mapped Cache�(line size 4B)

Line starting… maps to… has tag…

• @ 0x0 index 0 0000
• @ 0x4 index 1 0000
• @ 0x8 index 2 0000
• @ 0xC index 3 0000
• @ 0x10 index 0 0001
• etc.

0x

Tag: 0000

Yan, SP26

28-Caches III: Direct Mapped (20)

​

Direct Mapped Cache

• Placement policy: Each memory address is associated with exactly one possible line in the cache.

Unlike FA caches, DM caches have an index to identify the only cache line for this memory address.

tag to connect line to memory address

index to select line in cache

byte offset within line

Yan, SP26

28-Caches III: Direct Mapped (21)

​

Fill in the blank: Direct Mapped, 12 bit addresses

Suppose we have the below direct mapped cache for 12 bit addresses.

1. What is the line size / block size, in bytes?
2. What is the capacity, �in bytes?
3. For a 12b address, how many bits is the byte offset?
4. For a 12b address, how many bits is the index?
5. For a 12b address, how many bits is the tag?

​

​

A. B. C. D. E. F.

2 4 8 10 16 Other

​

2 4 8 10 16 Other

​

2 4 8 10 16 Other

​

​

2 4 8 10 16 Other

Yan, SP26

28-Caches III: Direct Mapped (22)

​

Yan, SP26

28-Caches III: Direct Mapped (23)

​

Terminology for Direct Mapped, 12b addresses

1. Line size / block size:

• # bytes per cache line

2. Capacity

• Total # data bytes that can be stored in a cache

3. Offset

• Identifies byte address of data stored at a given cache line

4. Index

• Selects cache line

5. Tag

• Identifies data stored at a given cache line to a given memory address

offset

tag

memory address

4 bytes

4 x 4 bytes

= 16 bytes

log₂(line size) = 2 bits

# address bits - # offset bits - # index bits = 8 bits

log₂(# lines) = 2 bits

index

Yan, SP26

28-Caches III: Direct Mapped (24)

​

Direct Mapped Cache Analysis

Agenda

• Line Replacement Policies
• Write Policies
• Direct Mapped Cache
• Direct Mapped Cache Analysis

—

• Types of Misses

Yan, SP26

28-Caches III: Direct Mapped (25)

​

Example: Direct Mapped Cache

Suppose we have the following direct mapped cache, for 12 bit addresses.

� Load byte 0xFE2

​

offset

tag

memory address

index

index

0x0

Compute T/I/O

Yan, SP26

28-Caches III: Direct Mapped (26)

​

Warming up the Direct Mapped Cache

• Suppose we have the following direct mapped cache, for 12b addresses.

Load byte 0xFE2 �

• Cache miss! Tag 0xFE is not valid at index 0.

0b1111 1110 0000 ← 0xFE0

0b1111 1110 0011 ← 0xFE3

b. Load into cache the 4-byte line � from 0xFE0 to 0xFE3.� Mark valid bit.

c. Read byte at 0x2 offset� and return to processor.

0xFE,0x0,0x2

Yan, SP26

28-Caches III: Direct Mapped (27)

​

Warming up the Direct Mapped Cache

• Suppose we have the following direct mapped cache, for 12b addresses.

Store byte 0x61C �

0x61,0x3,0x0

• Cache miss! Tag 0x61 is not valid at index 3.

b. Load into cache the 4-byte line.� Mark valid bit.

c. Write byte at 0x0 offset.� Mark dirty bit.

Yan, SP26

28-Caches III: Direct Mapped (28)

​

Warming up the Direct Mapped Cache

• Suppose we have the following direct mapped cache, for 12b addresses.

Load byte 0x61B �

0x61,0x2,0x3

• Cache miss! Tag 0x61 is not valid at index 2.

b. Load into cache the 4-byte line.� Mark valid bit.

c. Read byte at 0x3 offset� and return to processor.

Yan, SP26

28-Caches III: Direct Mapped (29)

​

Warming up the Direct Mapped Cache

• Suppose we have the following direct mapped cache, for 12b addresses.

Load byte 0xCAD �

0xCA,0x3,0x1

• Cache miss! Tag 0xCA is not valid at index 3.

b. Evict current line at index 3. � Write back data.

c. Load into cache the 4-byte line.� Mark valid bit.

d. Read byte at 0x1 offset� and return to processor.

Yan, SP26

28-Caches III: Direct Mapped (30)

​

Direct Mapped Cache

• Placement policy: The data at a memory address can be stored at exactly one possible line in the cache.

tag to connect line to memory address

index to select line in cache

byte offset within line

Example: 0x61B

Yan, SP26

28-Caches III: Direct Mapped (31)

​

Direct Mapped: Policies

1. Write Policy

​

A. Write-through� (memory access per write)

B. Write-back� (dirty bit, write to memory � on replacement)

What policies can be implemented for a direct-mapped cache?

Select all that apply.

2. Line Replacement Policy

A. Least Recently Used

B. Most Recently Used

C. FIFO

D. Random

E. None of the Above

Yan, SP26

28-Caches III: Direct Mapped (32)

​

Direct Mapped: Policies Solution

1. Write Policy

​

A. Write-through� (memory access per write)

B. Write-back� (dirty bit, write to memory � on replacement)

What policies can be implemented for a direct-mapped cache?

Select all that apply.

2. Line Replacement Policy

A. Least Recently Used

B. Most Recently Used

C. FIFO

D. Random

E. None of the Above

In direct mapped caches, there is only ever one line to replace—the existing line with matching index.

Yan, SP26

28-Caches III: Direct Mapped (33)

​

Cache Design: Placement Policies, Summary

• Direct Mapped
• Placement policy: Each memory address is associated with exactly one possible line in the cache.
• Simpler hardware: check one line
• Write policies: write-back, write-through
• No replacement policy, because we know which line to replace
• Has conflict misses (see soon)

• Fully Associative
• Placement policy: Data at any memory address can be associated with any cache line
• Expensive hardware: check all lines
• Write policies: write-back, write-through
• Must decide replacement policy (LRU, MRU, FIFO, etc.)

For the above reasons, smaller caches are generally fully associative.

Yan, SP26

28-Caches III: Direct Mapped (34)

​

(pause)

Yan, SP26

28-Caches III: Direct Mapped (35)

​

Looking Ahead

• CS 61C: Lectures 26-29, Caches I-IV
• EECS 151 (Digital/IC Design): Reveals the circuitry behind caches
• EECS 151LA (ASIC Lab): Design your own cache in SystemVerilog
• CS 152 (Comp Arch): Explores advanced cache implementations
• CS 162 (OS): Introduces software and hardware caches

Yan, SP26

28-Caches III: Direct Mapped (36)

​

Types of Misses

Agenda

• Line Replacement Policies
• Write Policies
• Direct Mapped Cache
• Direct Mapped Cache Analysis

—

• Types of Misses

Yan, SP26

28-Caches III: Direct Mapped (37)

​

Types of Misses

• Compulsory Miss
• Caused by the first access to data that has never been in the cache.
• Capacity Miss
• Caused when the cache cannot contain all the lines needed during the execution of a program.
• Occur when lines were in the cache, replaced, and later retrieved.
• Conflict Miss
• Multiple lines compete for the same location in the cache, even when the cache has not reached full capacity.

In this class, we will only distinguish between compulsory and non-compulsory misses.

“Non-compulsory” miss

Yan, SP26

28-Caches III: Direct Mapped (38)

​

Types of Misses

• Compulsory Miss
• Caused by the first access to data that has never been in the cache.
• Capacity Miss
• Caused when the cache cannot contain all the lines needed during the execution of a program.
• Occur when lines were in the cache, replaced, and later retrieved.
• Conflict Miss
• Multiple lines compete for the same location in the cache, even when the cache has not reached full capacity.

A. FA: Compulsory

B. DM: Compulsory

C. FA: Capacity

D. DM: Capacity

E. FA: Conflict

F. DM: Conflict

G. None of the above

​

Which types of misses can occur for Fully Associative caches (FA)? For Direct Mapped caches (DM)?

Select all that apply.

Yan, SP26

28-Caches III: Direct Mapped (39)

​

Yan, SP26

28-Caches III: Direct Mapped (40)

​

Types of Misses

• Compulsory Miss
• Caused by the first access to data that has never been in the cache.
• Capacity Miss
• Caused when the cache cannot contain all the lines needed during the execution of a program.
• Occur when lines were in the cache, replaced, and later retrieved.
• Conflict Miss
• Multiple lines compete for the same location in the cache, even when the cache has not reached full capacity.

A. FA: Compulsory

B. DM: Compulsory

C. FA: Capacity

D. DM: Capacity

E. FA: Conflict

F. DM: Conflict

G. None of the above

​

Which types of misses can occur for Fully Associative caches (FA)? For Direct Mapped caches (DM)?

Select all that apply.

Yan, SP26

28-Caches III: Direct Mapped (41)

​

Types of Misses

• Compulsory Miss
• Caused by the first access to data that has never been in the cache.
• Capacity Miss
• Caused when the cache cannot contain all the lines needed during the execution of a program.
• Occur when lines were in the cache, replaced, and later retrieved.
• Conflict Miss
• Multiple lines compete for the same location in the cache, even when the cache has not reached full capacity.

• Occurs in direct mapped caches, as well as set associative caches (more later).
• Misses of this type would not occur in a fully associative cache with similar specs.

In this class, we will only distinguish between compulsory and non-compulsory misses.

Yan, SP26

28-Caches III: Direct Mapped (42)

​

How to categorize misses

• Run an address trace against a set of caches.
• (thanks Prof. Kubiatowicz for the algorithm).

​

1. First, consider an infinite-size, fully-associative cache. For every miss that occurs now, consider it a compulsory miss.

​

• Next, consider a finite-sized cache (of the size you want to examine) with full-associativity. Every miss that is not in #1 is a capacity miss.

​

• Finally, consider a finite-size cache with finite-associativity. All of the remaining misses that are not #1 or #2 are conflict misses.

[reference]

In this class, we will only distinguish between compulsory and non-compulsory misses.

Yan, SP26

28-Caches III: Direct Mapped (43)

​

[Extra] Practice

Agenda

• Line Replacement Policies
• Write Policies
• Direct Mapped Cache
• Direct Mapped Cache Analysis

—

• Types of Misses

Yan, SP26

28-Caches III: Direct Mapped (44)

​

Direct Mapped Cache (write-back)

Suppose the 4-line, 4B line size cache below starts cold.

1. Load byte 0xFE2
2. Load byte 0xFE8
3. Load word 0xFE9
4. Load word 0xDF9
5. Load byte 0xFE8

​

​

1. What is the resulting state of the cache?
2. What misses occur, and are they compulsory or non-compulsory?

Yan, SP26

28-Caches III: Direct Mapped (45)

​

Direct Mapped Cache (write-back)

Suppose the 4-line, 4B line size cache below starts cold.

• Load byte 0xFE2 0b1111 1110 0010 0xFE, 0x0, 0x2
• Load byte 0xFE8 0b1111 1110 1000 0xFE, 0x2, 0x0
• Load word 0xFE9 0b1111 1110 1001 0xFE, 0x2, 0x1
• Load word 0xDF9 0b1101 1111 1001 0xDF, 0x2, 0x1
• Load byte 0xFE8 0b1111 1110 1000 0xFE, 0x2, 0x0

​

​

• What is the resulting state of the cache?
• What misses occur, and are they compulsory or non-compulsory?

Yan, SP26

28-Caches III: Direct Mapped (46)

​