Chapter 8: Cache Memory

Computer Architecture
and Organization

Department of Electrical and Computer Engineering

 Characteristics of memory system

• Speed – How fast can data be accessed from memory

• Defined by memory access time (latency)
• Access time is the time from the instant that an address
is presented to the memory to the instant that data have
been stored or made available for use.
• Cost per bit
• Capacity

Computer Architecture and Organization 2

Memory Hierarchy - Diagram

Computer Architecture and Organization 3

 Memory Hierarchy
• As we go down the hierarchy, one find decreasing cost per
bit, increasing capacity and slower access time.
• It would be nice to use only the fastest memory unit but it is
expensive.
• We trade off access time for cost by using more of slower
memory unit.
• The design challenge is to organize the data and program
in memory so that the required memory words are usually
in the fastest memory.
• If the cache is design properly, then most of the time the
processor will request memory word that are already in the
cache.

Computer Architecture and Organization 4

 Cache memory

• Cache holds a copy of portion of main memory most

recently accessed by the processor.
• Small amount of fast memory relative to main memory
• Logically located between CPU and normal main
memory.
• Physically it is usually embedded inside the CPU
• A processor may have a single cache or multilevel of
cache.

Computer Architecture and Organization 5

 Locality of Reference

• Principle of locality of reference states that if a

data location is referenced, then the same
location with nearby address will tend to
referenced soon.
• This arises from the natural program structure
• e.g. most program contain loop, so instructions
and data are likely to be accessed repeatedly.

Computer Architecture and Organization 6

Cache and Main Memory

Computer Architecture and Organization 7

Cache/Main Memory Structure

Computer Architecture and Organization 8

 Cache operation – overview

• CPU requests a word to read from memory

• Check cache if the word is in the cache
• If present, get from cache (is called a hit).
• If not present, read required block consisting that data
from main memory to cache (is called miss).
• Then deliver a word from cache to CPU
• Cache includes tags to identify which block of main
memory is in each cache slot
• The number of line in the cache is considerable less than
the number of main memory blocks ( m << M)

Computer Architecture and Organization 9

Cache Read Operation - Flowchart

Computer Architecture and Organization 10

Typical Cache Organization

Computer Architecture and Organization 11

 Elements of Cache Design

• Addressing
• Size
• Mapping Function
• Replacement Algorithm
• Write Policy
• Block Size
• Number of Caches

Computer Architecture and Organization 12

 Cache Addressing
• Almost all non-embedded processors and many embedded
processors support virtual memory
• Virtual memory
• Allows programs to access memory from a logical point
of view, without regarding the amount of physical
memory available.
• When virtual memory is used, the address field of
machine instruction contains virtual address.
• Memory management unit (MMU) translates each virtual
address into a physical address in main memory.

Computer Architecture and Organization 13

 Cache Addressing

• When virtual address is used a system designer may

place the cache
— Between processor and virtual memory management unit
— Between MMU and main memory
• Logical cache (virtual cache) stores data using virtual
addresses
— Processor accesses cache directly, not MMU
— Cache access faster, because not MMU address translation
• Physical cache stores data using main memory physical
addresses

Computer Architecture and Organization 14

Cache Addressing …

Computer Architecture and Organization 15

 Cache Size

• Cost
—More cache is expensive
• Speed
—More cache is faster (up to a point)
— if the cache larger checking cache (addressing) for
data takes time

Computer Architecture and Organization 16

 Comparison of Cache Sizes
Year of
Processor Type L1 cache L2 cache L3 cache
Introduction
IBM 360/85 Mainframe 1968 16 to 32 KB — —
PDP-11/70 Minicomputer 1975 1 KB — —
VAX 11/780 Minicomputer 1978 16 KB — —
IBM 3033 Mainframe 1978 64 KB — —
IBM 3090 Mainframe 1985 128 to 256 KB — —
Intel 80486 PC 1989 8 KB — —
Pentium PC 1993 8 KB/8 KB 256 to 512 KB —
PowerPC 601 PC 1993 32 KB — —
PowerPC 620 PC 1996 32 KB/32 KB — —
PowerPC G4 PC/server 1999 32 KB/32 KB 256 KB to 1 MB 2 MB
IBM S/390 G4 Mainframe 1997 32 KB 256 KB 2 MB
IBM S/390 G6 Mainframe 1999 256 KB 8 MB —
Pentium 4 PC/server 2000 8 KB/8 KB 256 KB —
High-end server/
IBM SP 2000 64 KB/32 KB 8 MB —
supercomputer
CRAY MTAb Supercomputer 2000 8 KB 2 MB —
Itanium PC/server 2001 16 KB/16 KB 96 KB 4 MB
SGI Origin 2001 High-end server 2001 32 KB/32 KB 4 MB —
Itanium 2 PC/server 2002 32 KB 256 KB 6 MB
IBM POWER5 High-end server 2003 64 KB 1.9 MB 36 MB
CRAY XD-1 Supercomputer 2004 64 KB/64 KB 1MB —

Computer Architecture and Organization 17

 Mapping function
• Because there are fewer cache lines than main memory
blocks an algorithm is needed for mapping blocks into
cache line
• A means is need to for determining which main memory
block currently occupies a cache line
• The mapping function dictates how the cache is organized
• Three techniques can used – Direct, Associative and
Set-associative

Computer Architecture and Organization 18

 Mapping Function
• Example
• Cache of 64kByte
• Cache block of 4 bytes
—i.e. cache is 16k (214) lines of 4 bytes
• 16MBytes main memory
• 24 bit address
—(224=16M).
• For mapping purpose we can consider main
memory consist of 4Mbyte blocks of 4 byte each.

Computer Architecture and Organization 19

 Mapping Function
Cache Main Memory
1 byte word
Tag 4 byte Line /Block
1 byte
4 byte Block
1 byte
1 byte

16Mbyte
16M = 224
24 bit to address
4 byte x 16k = 64Kbyte
16𝐾 = 214
14 bit to address

Computer Architecture and Organization 20

 Direct Mapping

• Each block of main memory maps to only one cache line

• i.e. if a block is in cache, it must be in one specific
place
• The mapping expressed as i = j modulo m
• Where i = cache line number
• j = main memory block number
• m = number of lines in the cache
• The mapping function is easily implemented using the
main memory address
• For the purpose of cache access, each main memory
address can be viewed as consisting three field

Computer Architecture and Organization 21

 Direct Mapping Address Structure
Memory address

Tag s-r Line or Slot r Word w

S (block)

• Least Significant w bits identify unique word with in a block.

• The remaining s bit specify one of the 2𝑠 block of main
memory.
• The Tag field (s-r bit) identify a unique block with a line.
• The line field r identify one of the m= 2𝑟 line of the cache.

Computer Architecture and Organization 22

Direct Mapping from Cache to Main Memory

Computer Architecture and Organization 23

 Direct Mapping Cache Line Table

Cache line Main Memory blocks held

0 0, m, 2m, 3m…2s-m

1 1,m+1, 2m+1…2s-m+1

…
m-1 m-1, 2m-1,3m-1…2s-1

Computer Architecture and Organization 24

Direct Mapping Cache Organization

Computer Architecture and Organization 25

 Direct Mapping Example
• Given 24 bit address of main memory byte addressable
and 64Kbyte of cache block of 4 byte
• block size = 2𝑤 = 22 = 4 byte.
• Cache size = 2𝑟+𝑊 = 214+2 = 64kbyte words or bytes
• 14 bit slot or line r ( number of line in cache 2𝑟 = 214 )
• 8 bit tag (=22-14)
• To check contents of cache first finding Line ,then
compare the Tag.
• No two blocks map in to the same line that have the same
Tag field
Tag s-r Line or Slot r Word w
8 14 2
Memory address
Computer Architecture and Organization 26
Direct
Mapping
Example

Computer Architecture and Organization 27

 Direct Mapping Summary

• Address length = (s + w) bits

• Number of addressable units = 2s+w words or
bytes
• Block size = line size = 2w words or bytes
• Number of blocks in main memory
= 2s+w/2w = 2s
• Number of lines in cache = m = 2r
• Size of tag = (s – r) bits
• Size of the cache = 2r+w

Computer Architecture and Organization 28

 Direct Mapping pros & cons

• Simple
• Inexpensive
• Fixed location for given block
• If a program accesses 2 blocks that map to the same
line repeatedly, cache misses are very high

Computer Architecture and Organization 29

 Victim Cache

• One approach to lower penalty is to remember

what was discarded in case it’s needed again
• Remember what was discarded
—Already fetched so used again at small cost
—Use again with little penalty
• Such recycling is possible using victim cache.
• Fully associative
• 4 to 16 cache lines
• Between direct mapped L1 cache and next
memory level

Computer Architecture and Organization 30

 Associative Mapping

• A main memory block can load into any

line of cache
• Memory address is interpreted as tag and
word
• Tag uniquely identifies block of memory
• To determine whether the block is in the
cache, every line’s tag is examined for a
match
• Cache searching gets expensive

Computer Architecture and Organization 31

 Associative Mapping Address Structure

Tag Word

Memory address

• Compare tag field with tag entry in cache to check for hit
• Least significant bits (word) of address identify a unique
word
• No field in the address corresponding to the line number
• The number of line in the cache is not determined by the
address format.

Computer Architecture and Organization 32

Associative Mapping from
Cache to Main Memory

Computer Architecture and Organization 33

Fully Associative Cache Organization

Computer Architecture and Organization 34

 Associative Mapping Example
• Given 24 bit address of main memory byte addressable
and 64Kbyte of cache block of 4 byte
• Block size = 2w =22 word or byte
• 22 bit tag stored with each 32 bit block of data.
• Compare tag field with tag entry in cache to check for hit.
• Least significant 2 bits of address identify which 8 bit (1
byte ) of word is required from 32 bit data block.

Tag 22 bit Word

2 bit
Memory address

Computer Architecture and Organization 35

Associative
Mapping
Example

Computer Architecture and Organization 36

 Associative Mapping Summary

• Address length = (s + w) bits

• Number of addressable units = 2s+w words or
bytes
• Block size = line size = 2w words or bytes
• Number of blocks in main memory
= 2s+ w/ 2w = 2s
• Number of lines in cache = undetermined
• Size of tag = s bits

Computer Architecture and Organization 37

 Associative Mapping

• Is flexible as which block to replace when a new

block is read into the cache line
• Replacement algorithm is designed to maximize
the hit ratio.
• The principal disadvantage of associative mapping
is the complex circuitry required to examine the
tag of all cache lines in parallel.

Computer Architecture and Organization 38

 Set-Associative Mapping

• Cache is divided into a number of sets

• Each set contains a number of lines
• A given block maps to any line in a given set
—e.g. Block B can be in any line of set i
• e.g. 2 lines per set
—2 way associative mapping
—A given block can be in one of 2 lines in only one set
• Set-associative mapping is combination of
associate and direct mapping implementation.

Computer Architecture and Organization 39

 Set Associative Mapping
Address Structure
Memory address

Word
Tag ( s-d bit) Set (d bit) bit
S (block)
• For set-associative mapping the cache control unit
interprets the memory address as three fields.
• The d set bit specify one of v = 2d sets.
• The s bit specify one of the 2s blocks of main memory.
• Tag bit specify a unique block of memory
• Word bit specify a unique word with a block of memory
• Use set (d bit) field to determine cache set to look in
• Then compare tag field to see if we have a hit in a single
set
Computer Architecture and Organization 40
Set Associative Mapping

Computer Architecture and Organization 41

K-Way Set Associative Mapping Example

Computer Architecture and Organization 42

 Two way set Associative Mapping Example
• Given 24 bit address of main memory byte addressable and
64Kbyte of cache block of 4 byte
• The number of line per set k = 2 (two way set)
• The block size = 4 byte = 22 = 2w
• Cache size = k x 2d+w = 216 = 64kbyte
• The number of set is 2d = 213
• The number of block in memory 2s+w / 2w = 2s = 222
• For read operation the 13 bit set number is used to determine
which set of two lines is to be examined
• Then, Both lines in the set examined for a match with a tag
number of the address to be accessed.
Word
Tag 9 bit Set 13 bit 2 bit
Memory address
Computer Architecture and Organization 43
Two Way Set Associative Mapping Example

Computer Architecture and Organization 44

 Set Associative Mapping summery
• Address length = (s + w) bits
• Number of addressable unit = 2s+w words or bytes
• Block size = line size = 2w words or bytes
• Number of block in main memory = 2s+w / 2w = 2s
• Number of lines in each set = k
• Number of sets = v = 2d
• Total number of line in cache m = k x v = k x 2d
• Size of the cache = k x 2d+w words or bytes
• Size of tag = s-d bits
• In extreme case of when v=m, k=1, the set associate
reduce to direct mapping and for v=1 k=m, it reduce to full
associative mapping.

Computer Architecture and Organization 45

 Set Associative Mapping
• Example: A set-associative cache consists of 64 lines, or
slots, divided into four-line sets. Main memory
contains 4K blocks of 128 words each. Show the format of
main memory addresses.
• Answer:
• M= k x v, m= 64, k=4 , v= 16
• V= 2d = 16 , d = 4 bit
• Main memory consists of 4K = 212 blocks.
• Number of block in main memory = 2s = 212
• Tag s-d = 12 – 4 = 8
• Each block contains 128 words. Block size 2w = 128 = 27 word

Computer Architecture and Organization 46

 Replacement Algorithms (1) Direct mapping

• Once the cache has been filled, when a new

block brought into the cache, one of the existing
blocks must be replaced.
• For Direct Mapping
• There is only one possible line for any particular
block
• No choice
• Each block only maps to one line
• Replace that line

Computer Architecture and Organization 47

 Replacement Algorithms (2)
Associative & Set Associative
• To achieve high speed, Hardware implemented algorithm
• Least Recently Used (LRU)
• Replace the block in the set that has been in the cache longest
with no reference.
• e.g. in 2 way set associative
• Which of the 2 block is LRU?
• First in First Out (FIFO)
• Replace block that has been in cache longest
• Least Frequently Used (LRU)
• Replace block which has had fewest hits
• Can be implemented by associated a counter with each line.
• Random replacement
• Pick a line at random from among a candidate line

Computer Architecture and Organization 48

 Write Policy

• When a block that is resident in the cache is to be

replaced, there are things to consider.
• Must not overwrite a cache block unless main memory is
up to date
• There are two problems to deal with
• First, more than one device may have access to main
memory
• E.g. I/O may be read-write directly to memory
• Second, when multiple Processors are attached to the
same bus and each processor has its own local cache.
• If a word is altered in one cache, it could invalidates a
word in other caches.

Computer Architecture and Organization 49

 Write through

• All writes operations are made to main memory as well

as to the cache, ensuring main memory is valid.
• Multiple CPUs can monitor main memory traffic to keep
local (to CPU) cache up to date
• The main disadvantage of this techniques is it generates
lots of memory traffic
• Slows down writes

Computer Architecture and Organization 50

 Write back

• Minimize memory write

• Updates initially made in cache only
• Update bit for cache line is set when update occurs
• If block is to be replaced, write to main memory only if
update bit is set
• The problem with technique is
• Other caches get out of sync
• Portion of main memory are invalid
• Hence, I/O must access main memory through cache
• This makes complex circuitry

Computer Architecture and Organization 51

 Cache Coherency
• When more than one device has a separate cache and
main memory is shared
• If data in one cache altered, this invalidates the same word
in other cache as well as in main memory.
• Approaches to maintain this problem ( cache coherency)
• Bus watching with write through
• Each cache controllers monitors the address lines to detect write
operations to memory by others.
• Hardware transparency
• Additional hardware is used to ensure that all updates to main
memory via cache are reflected in all caches.
• Noncacheable memory
• Only noncacheable portion of the memory is shared
• The shared portions never copied into a cache
Computer Architecture and Organization 52
 Line Size
• Another design element is the line size
• Retrieve not only desired word but a number of adjacent
words as well i.e. block
• Increased block size will increase hit ratio at first
• the principle of locality
• Hit ratio will decreases as block becomes even bigger
• Probability of using newly fetched information becomes less
than probability of reusing replaced
• Larger blocks
• Reduce number of blocks that fit in cache
• Each additional word is less local so less likely to be needed
• No definitive optimum value has been found
• 8 to 64 bytes seems reasonable
• For HPC systems, 64- and 128-byte most common

Computer Architecture and Organization 53

 Multilevel Caches

• High logic density enables caches on-chip

• The on-chip cache
• Faster than caches reachable via an external bus
• Reduce processor's external bus activity – speedup
• Free the bus for other transfers.
• Common to use both on and off chip cache
• L1 on chip, L2 off chip in static RAM
• L2 access much faster than DRAM or ROM
• L2 often uses separate data path not system bus
• L2 may now be on chip
• Resulting in L3 cache
• Originally, via external bus access but now on chip L3

Computer Architecture and Organization 54

 Unified v Split Caches

• One cache for both data and instructions ( unified)

• or two, one dedicated for data and one dedicated for
instructions (split).
• Advantages of unified cache
• Higher hit rate
• Balances load of instruction and data fetch automatically
• Only one cache to design & implement
• Advantages of split cache
• Eliminates cache contention between instruction fetch unit and
execution unit
• Important in pipelining

Computer Architecture and Organization 55

 End of Chapter 8

Computer Architecture
and Organization

Department of Electrical and Computer Engineering