JavaScript isn't enabled in your browser, so this file can't be opened. Enable and reload.

1 of 24

�Caches II

CS61C

UC Berkeley�Teaching Professor �Dan Garcia

cs61c.org

Great Ideas

in�Computer Architecture

(a.k.a. Machine Structures)

Garcia

Caches II (1)

Garcia

2 of 24

Direct Mapped Caches

Caches II (2)

Garcia

3 of 24

Direct-Mapped Cache (1/4)

In a direct-mapped cache, each memory address is associated with one possible block within the cache

Therefore, we only need to look in a single location in the cache for the data if it exists in the cache
Block is the unit of transfer between cache and memory

Caches II (3)

Garcia

4 of 24

Direct-Mapped Cache (2/4)

Cache Location 0 can be�occupied by data from:

Memory location 0, 4, 8, ...
4 blocks ⇒ any memory location that is multiple of 4

Memory

Memory �Address

0

1

2

3

4

5

6

7

8

9

A

B

C

D

E

F

4 Byte Direct

Mapped Cache

Cache

Index

0

1

2

3

What if we wanted a block�to be bigger than one byte?

Block size = 1 byte

Caches II (4)

Garcia

Let’s look at the simplest cache one can build. A direct mapped cache that only has 4 bytes.

In this direct mapped cache with only 4 bytes, location 0 of the cache can be occupied by data form memory location 0, 4, 8, C, ... and so on.

While location 1 of the cache can be occupied by data from memory location 1, 5, 9, ... etc.

So in general, the cache location where a memory location can map to is uniquely determined by the 2 least significant bits of the address (Cache Index).

For example here, any memory location whose two least significant bits of the address are 0s can go to cache location zero.

With so many memory locations to chose from, which one should we place in the cache?

Of course, the one we have read or write most recently because by the principle of temporal locality, the one we just touch is most likely to be the one we will need again soon.

Of all the possible memory locations that can be placed in cache Location 0, how can we tell which one is in the cache?

+2 = 22 min. (Y:02)

5 of 24

Direct-Mapped Cache (3/4)

When we ask for a byte, the controller finds out the right block, and loads it all!

How does it know right block?
How do we select the byte?

E.g., Mem address 11101?
How does it know WHICH colored block it originated from?

What do you do at baggage claim?

Memory

Memory �Address

0

2

4

6

8

A

C

E

10

12

14

16

18

1A

1C

1E

8-Byte Direct

Mapped Cache

Cache

Index

0

1

2

3

Block size = 2 bytes

0

1

2

3

4

5

6

7

8

9

etc.

Caches II (5)

Garcia

Let’s look at the simplest cache one can build. A direct mapped cache that only has 4 bytes.

In this direct mapped cache with only 4 bytes, location 0 of the cache can be occupied by data form memory location 0, 4, 8, C, ... and so on.

While location 1 of the cache can be occupied by data from memory location 1, 5, 9, ... etc.

So in general, the cache location where a memory location can map to is uniquely determined by the 2 least significant bits of the address (Cache Index).

For example here, any memory location whose two least significant bits of the address are 0s can go to cache location zero.

With so many memory locations to chose from, which one should we place in the cache?

Of course, the one we have read or write most recently because by the principle of temporal locality, the one we just touch is most likely to be the one we will need again soon.

Of all the possible memory locations that can be placed in cache Location 0, how can we tell which one is in the cache?

+2 = 22 min. (Y:02)

6 of 24

Direct-Mapped Cache (4/4)

What should go in the tag?

Do we need the entire address?

What do all these tags have in common?

What did we do with the immediate when we were branch addressing, always count by bytes?

Why not count by cache #?

It’s useful to draw memory with the same width as the block size

Memory

Memory �Address

0

2

4

6

8

A

C

E

10

12

14

16

18

1A

1C

1E

8-Byte Direct

Mapped Cache with Tag

Cache

Index

0

1

2

3

Block size = 2 bytes

0

1

2

3

4

5

6

7

8

9

etc.

0

1

2

3

Cache#

1

0

3

2

8

2

1E

14

Caches II (6)

Garcia

Let’s look at the simplest cache one can build. A direct mapped cache that only has 4 bytes.

In this direct mapped cache with only 4 bytes, location 0 of the cache can be occupied by data form memory location 0, 4, 8, C, ... and so on.

While location 1 of the cache can be occupied by data from memory location 1, 5, 9, ... etc.

So in general, the cache location where a memory location can map to is uniquely determined by the 2 least significant bits of the address (Cache Index).

For example here, any memory location whose two least significant bits of the address are 0s can go to cache location zero.

With so many memory locations to chose from, which one should we place in the cache?

Of course, the one we have read or write most recently because by the principle of temporal locality, the one we just touch is most likely to be the one we will need again soon.

Of all the possible memory locations that can be placed in cache Location 0, how can we tell which one is in the cache?

+2 = 22 min. (Y:02)

7 of 24

Issues with Direct-Mapped

Since multiple memory addresses map to same cache index, how do we tell which one is in there?
What if we have a block size > 1 byte?
Answer: divide memory address into three fields

ttttttttttttttttt iiiiiiiiii oooo

tag index byte�to check to offset�if have select within�correct block block block

Caches II (7)

Garcia

8 of 24

Direct-Mapped Cache Terminology

All fields are read as unsigned integers.
Index

specifies the cache index (which “row”/block of the cache we should look in)

Offset

once we’ve found correct block, specifies which byte within the block we want

Tag

the remaining bits after offset and index are determined; these are used to distinguish between all the memory addresses that map to the same location

Caches II (8)

Garcia

9 of 24

AREA (cache size, B)�= HEIGHT (# of blocks) � * WIDTH (size of one block, B/block)

WIDTH �(size of one block, B/block)

HEIGHT�(# of blocks)

2^(H+W) = 2^H * 2^W

Tag Index Offset

TIO Cache Mnemonic (Thanks Uncle Dan!)

AREA�(cache size, B)

🗹

Caches II (9)

Garcia

10 of 24

Direct Mapped Example

Caches II (10)

Garcia

11 of 24

Direct-Mapped Cache Example (1/3)

Suppose we have a 8B of data in a direct-mapped cache with 2-byte blocks

Sound familiar?

Determine the size of the tag, index and offset fields if using a 32-bit arch (RV32)
Offset

need to specify correct byte within a block
block contains 2 bytes

= 2¹ bytes

need 1 bit to specify correct byte

Caches II (11)

Garcia

12 of 24

Direct-Mapped Cache Example (2/3)

Index: (~index into an “array of blocks”)

need to specify correct block in cache
cache contains 8 B = 2³ bytes
block contains 2 B = 2¹ bytes
# blocks/cache

= bytes/cache� bytes/block

= 2³ bytes/cache� 2¹ bytes/block

= 2² blocks/cache

need 2 bits to specify this many blocks

Caches II (12)

Garcia

13 of 24

Direct-Mapped Cache Example (3/3)

Tag: use remaining bits as tag

tag length = addr length – offset - index � = 32 - 1 - 2 bits� = 29 bits
so tag is leftmost 29 bits of memory address
Tag can be thought of as “cache number”

Why not full 32-bit address as tag?

All bytes within block need same address
Index must be same for every address within a block, so it’s redundant in tag check, thus can leave off to save memory

Caches II (13)

Garcia

14 of 24

Memory Access without Cache

Load word instruction: lw t0, 0(t1)
t1 contains 1022_ten,Memory[1022] = 99

Processor issues address 1022_tento Memory
Memory reads word at address 1022_ten(99)
Memory sends 99 to Processor
Processor loads 99 into register t0

Caches II (14)

Garcia

15 of 24

Memory Access with Cache

Load word instruction: lw t0, 0(t1)
t1 contains 1022_ten,Memory[1022] = 99
With cache (similar to a hash)

Processor issues address 1022_tento Cache
Cache checks to see if has copy of data at address 1022_ten

2a. If finds a match (Hit): cache reads 99, sends to processor

2b. No match (Miss): cache sends address 1022 to Memory

Memory reads 99 at address 1022_ten
Memory sends 99 to Cache
Cache replaces word with new 99
Cache sends 99 to processor

Processor loads 99 into register t0

Caches II (15)

Garcia

16 of 24

Solving Cache problems

Draw memory a block wide given T I O bits,�dashed word boundary lines

WIDTH �(size of one block, B/block)

HEIGHT�(# of blocks)

Tag Index Offset

CACHE

WIDTH �(size of one block, B/block)

Tag = 0

Tag = 1

Tag = 2

Tag = max

00…00 00…00 00…00

00…00 00…00 00…01

00…00 00…00 11…11

00…00 00…01 00…00

00…00 11…11 11…11

00…01 00…00 00…00

11…11 11…11 11…11

Tag Index Offset

MEMORY

🗹

Caches II (16)

Garcia

17 of 24

Cache Terminology

Caches II (17)

Garcia

18 of 24

Caching Terminology

When reading memory, 3 things can happen:

cache hit: �cache block is valid and contains proper address, so read desired word
cache miss: �nothing in cache in appropriate block, so fetch from memory
cache miss, block replacement: �wrong data is in cache at appropriate block, so discard it and fetch desired data from memory (cache always copy)

Caches II (18)

Garcia

19 of 24

Cache Temperatures

Cold

Cache empty

Warming

Cache filling with values you’ll hopefully be accessing again soon

Warm

Cache is doing its job, fair % of hits

Hot

Cache is doing very well, high % of hits

Caches II (19)

Garcia

20 of 24

Cache Terms

Hit rate: fraction of access that hit in the cache
Miss rate: 1 – Hit rate
Miss penalty: time to replace a block from lower level in memory hierarchy to cache
Hit time: time to access cache memory (including tag comparison)

Caches II (20)

Garcia

21 of 24

One More Detail: Valid Bit

When start a new program, cache does not have valid information for this program
Need an indicator whether this tag entry is valid for this program
Add a “valid bit” to the cache tag entry

0 🡪 cache miss, even if by chance, address = tag

1 🡪 cache hit, if processor address = tag

Caches II (21)

Garcia

22 of 24

Example: 16 KB Direct-Mapped Cache, 16B blocks

Valid bit: determines whether anything is stored in that row (when computer initially powered up, all entries invalid)

...

Valid

Tag

0xc-f

0x8-b

0x4-7

0x0-3

0

1

2

3

4

5

6

7

1022

1023

...

Index

0

0

0

0

0

0

0

0

0

0

Looks like a real cache, will investigate it some more!

Caches II (22)

Garcia

23 of 24

Caches II (23)

Garcia

24 of 24

“And in Conclusion…”

We have learned the operation of a direct-mapped cache
Mechanism for transparent movement of data among levels of a memory hierarchy

set of address/value bindings
address 🡪 index to set of candidates
compare desired address with tag
service hit or miss

load new block and binding on miss

🗹

Caches II (24)

Garcia