Computer Organization

and Architecture
(EET 2211)

1 Computer Organization and Architecture

 Chapter 4
CACHE MEMORY

2 Computer Organization and Architecture

 4.1. COMPUTER MEMORY SYSTEM OVERVIEW
Characteristics
Location
Capacity
Unit of transfer
Access method
Performance
Physical type
Physical characteristics
Organisation

3 Computer Organization and Architecture

 Location :
 Refers to whether memory is internal and
external to the computer

CPU requires its own local memory, in the

form of registers
Internal memory referred as
main memory, cache memory.
External memory consists of peripheral
storage devices that are accessible to the
processor via I/O controllers such as
peripheral devices, disk, tape.
4 Computer Organization and Architecture
 Capacity
For internal memory-
Bytes or Words
For external memory-
Bytes

5 Computer Organization and Architecture

 Unit of Transfer :
Internal Memory :the unit of transfer is
equal to the number of electrical lines into
and out of the memory module.

Usually governed by data bus width

 Word
o The natural unit of organisation

o The size of a word is typically equal to the

number of bits used to represent an
integer and to the instruction length.

6 Computer Organization and Architecture

 Unit of Transfer
 Internal Memory
 Addressable unit is
o Smallest location which can be uniquely
addressed

o addressable unit is the word

o Addressable units is 2A=N.

A is length in bits in an address, N is
addressable units.
 Unit of transfer
o this is the number of bits read out of or
Computer Organization and Architecture
7
written into memory at a time.
 Access Methods: Method of Accessing Units of
Data

Sequent Random
Direct Associa
ial access
access tive
access

8 Computer Organization and Architecture

 Access Methods: Method of Accessing Units of
Data
Sequent
Direct Random Associat
ial
access access ive
access Each
A word is
Involves a addressable
retrieved
shared read- location in
based on a
write memory has
Memory is portion of its
mechanism a unique,
organized contents
physically
into units of rather than its
wired-in
data called address
addressing
records mechanism
Individual The time to
blocks or access a given Each location
records have location is has its own
a unique independent addressing
Access must address based of the mechanism
be made in on physical sequence of and retrieval
a specific location prior accesses time is
linear and is constant
sequence Any location
constant independent
can be of location or
selected at prior access
Access time random and patterns
is variable directly
Access time addressed
is variable and accessed
Main memory Cache
and some memories may
cache systems employ
are random associative
access access

9 Computer Organization and Architecture

 Access Methods: Method of Accessing Units of
Data
Sequential
Start at the beginning and read through in
order
Access time depends on the location of data
and the previous location
e.g. magnetic tape, magnetic disk, optical
memory

10 Computer Organization and Architecture

 Access Methods
Direct
Individual blocks/records have unique
address
Access is by jumping to vicinity plus
sequential search
Access time depends on location and
previous location
e.g. disk

11 Computer Organization and Architecture

 Cont.
Random
Individual addresses identify locations
exactly
Access time is independent of location or
previous access
e.g. RAM

12 Computer Organization and Architecture

 Cont.
Associative
Data is located by a comparison with
contents of a portion of the store
Access time is independent of location or
previous access
e.g. cache

13 Computer Organization and Architecture

 Capacity and Performance
Access time
Time between presenting the address and
getting the valid data

Memory Cycle time

Time may be required for the memory to
“recover” before next access
Cycle time is access + recovery

14 Computer Organization and Architecture

 Capacity and Performance:
Transfer Rate :This is the rate at which data
can be transferred into or out of a memory
unit.
Rate at which data can be moved
Tn = TA + n /R
where Tn = Average time to read or write n
bits
TA = Average access time
n = Number of bits
R = Transfer rate, in bits per second
(bps)
15 Computer Organization and Architecture
 Physical Memory Types:
Semiconductor
RAM
Magnetic
Disk & Tape
Optical
CD & DVD
Others
Bubble
Hologram

16 Computer Organization and Architecture

 Physical Characteristics
Volatility
Information lost when power is switch
off.
Non-volatility
Information not lost when power is switch
off.
e.g. magnetics-surface memory.
Non-Erasable
e.g. ROM.

17 Computer Organization and Architecture

 Organisation
Organization refers to the physical
arrangement of bits to form words

For random-access memory, the

organization is a key design issue.

18 Computer Organization and Architecture

 The Memory Hierarchy
How much?

How fast?

How expensive?

19 Computer Organization and Architecture

 The Memory Hierarchy
The constraints for designing a memory
system leads to three question:

20 Computer Organization and Architecture

 The Memory Hierarchy
How much?

How fast?

How expensive?

21 Computer Organization and Architecture

 The Memory Hierarchy
Refers to
How much?
Capacity of
the memory
How fast?

How expensive?

22 Computer Organization and Architecture

 The Memory Hierarchy
Refers to
How much?
Capacity of
the memory
How fast?

Refers to
How expensive? Access Time
of the memory

23 Computer Organization and Architecture

 The Memory Hierarchy
Refers to
How much?
Capacity of
the memory
How fast?

Refers to
How expensive? Access Time
of the memory

Refers to Cost
of the memory

24 Computer Organization and Architecture

 The Memory Hierarchy
The dilemma associated with most of the
memory technologies are:
 Faster access time, but greater cost per
bit;

 Greater capacity, but smaller cost per bit;

 Greater capacity, but slower access time

25 Computer Organization and Architecture

 The Memory Hierarchy
The way out of this dilemma is not to rely on a
single memory component or technology, but to
employ a memory hierarchy.
As we go down the hierarchy
Decreasing cost per bit;
Increasing capacity;
Increasing access time;
Decreasing frequency of access of the
memory by the processor

26 Computer Organization and Architecture

 The Memory Hierarchy
The way out of this dilemma is not to rely on a
single memory component or technology, but to
employ a memory hierarchy.

Decreasing cost per bit;

Increasing capacity;
Increasing access time;
Decreasing frequency of access of the
memory by the processor

27 Computer Organization and Architecture

 Memory Hierarchy - Diagram
 The Key to success to organization is:
Decreasing frequency of access of the
memory by the processor

 The Validity of Decreasing frequency of

access of the memory by the processor is
based on principle called as Locality of
References.

1. Temporal Locality 2. Spatial

Locality
28 Computer Organization and Architecture
Ex: Program contains Ex:
 Memory Hierarchy - Diagram

Principle of Locality:
A computer program will require access to a
relatively small portion of the address space at any instant
of time during execution.
1. Temporal Locality :
If an item (Memory) is accessed, will tend to be
referenced/accessed again soon.
Ex: Program contains iterative loops and
subroutine

2. Spatial Locality:
If an item is referenced, items whose addresses are
close by tend to be referenced soon.
29 Ex: Operations
Computer Organizationbased on the array and table
and Architecture
 Memory Hierarchy - Diagram

30 Computer Organization and Architecture

 Memory Hierarchy
Registers
In CPU
Internal or Main memory
May include one or more levels of cache
“RAM”
External memory
Backing store

31 Computer Organization and Architecture

 Hierarchy List
Registers
L1 Cache
L2 Cache
Main memory
Disk cache
Disk
Optical
Tape

32 Computer Organization and Architecture

 So you want fast?
It is possible to build a computer that uses
only static RAM
This would be very fast
This would need no-cache
How can you cache?
This would cost a very large amount

33 Computer Organization and Architecture

 4.2 CACHE MEMORY PRINCIPLES

Cache memory is designed to combine the

memory access time of expensive, high
speed memory combined with large memory
size of less expensive, lower speed memory.
• Small amount of fast memory
• Expensive
• Sits between normal main memory and
CPU
• May be located on CPU chip or module

34 Computer Organization and Architecture

 Cache and Main Memory

35 Computer Organization and Architecture

 Cache/Main Memory Structure

The length of line(line size) not include tag and control bits.

C<<M
M-1

36 Computer Organization and Architecture

 Cache Read Operation - Flowchart

37 Cache
Computer Organization and Architecture Read Operation
 Cache Operation – Overview
CPU requests contents of memory location
Check cache for this data
If present, get from cache (fast)
If not present, read required block from
main memory to cache(Cache
Organization)
Then deliver from cache to CPU
Cache includes tags to identify which block
of main memory is in each cache slot

38 Computer Organization and Architecture

 Typical Cache Organization

39 Computer Organization and Architecture

 Cache Organization – Overview
The cache connects to the processor via data,
control and address lines
The data and address lines attach to data and
address buffers through system bus to reach
main memory
Hit occurs-communication only between
processor and cache(disable data and address
buffer)
Miss occurs-the data are return through the
data buffer to both cache and the
processor(desired address is loaded onto the
system bus)

40 Computer Organization and Architecture

 4.3 Elements of Cache Design
Basic Design Elements For Cache
Architecture:
• Cache Addressing
• Cache Size
• Mapping Function
• Replacement Algorithm
• Write Policy
• Line Size
• Number of Caches

41 Computer Organization and Architecture

 Cache Addressing
 Where does cache sit?
 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 thorough
physical cache
 Cache access faster, before MMU address translation
 Virtual addresses use same address space for different
applications
 Must flush cache on each context switch

 Physical cache stores data using main memory

42
physical addresses
Computer Organization and Architecture
 Logical and Physical Caches
43 Computer Organization and Architecture
 Cache Size

Minimizing cache size(small)

Cost
More cache is expensive
Speed
More cache is faster (up to a point)
Checking cache for data takes time
Larger the cache ,larger number of gates
involved for addressing

44 Computer Organization and Architecture

 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 —

45 Computer Organization and Architecture

 Mapping Function
 Algorithm needed for mapping main
memory blocks to cache lines
 A means is needed to determining which
main memory block currently occupies a
cache line
 Three Techniques:
1. Direct
2. Associative
3. Set Associative

46 Computer Organization and Architecture

 For all three cases, the example includes the
following elements
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)

47 Computer Organization and Architecture

 Direct Mapping
Simplest technique
 Map each block of main memory into only
one possible cache line.
It is expressed as:
i=j modulo m
Where
i=cache line number
j= main memory block number
m= number of lines in the cache

48 Computer Organization and Architecture

 Direct Mapping from Cache to Main Memory

49 Computer Organization and Architecture

 Direct Mapping Cache Organization

50 Computer Organization and Architecture

 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
Address is in two parts
Least Significant w bits identify unique word
Most Significant s bits specify one memory block
The MSBs are split into a cache line field r and a
tag of s-r (most significant) and a line field of r bits
 m=2^r lines of the cache

51 Computer Organization and Architecture

 Direct Mapping Summary

Address length = (s + w) bits

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

52 Computer Organization and Architecture

 Direct Mapping Example

53 Computer Organization and Architecture

Tag s-r Line or Slot r Word w
8 14 2

 24 bit address
 2 bit word identifier (4 byte block)
 22 bit block identifier
 8 bit tag (=22-14)
 14 bit slot or line
 No two blocks in the same line have the same Tag field
 Check contents of cache by finding line and checking Tag
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
 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

56 Computer Organization and Architecture

 Victim Cache

Lower miss penalty

Remember what was discarded
Already fetched
Use again with little penalty
Fully associative
4 to 16 cache lines
Between direct mapped L1 cache and next
memory level of memory

57 Computer Organization and Architecture

 Associative mapping

 Associative mapping overcomes the disadvantage of

direct mapping by
 permitting each main memory block to be loaded into any
line of the cache.
 In this case, the cache control logic interprets a memory
address simply as a Tag and a Word field.
 The Tag field uniquely identifies a block of main memory.

To determine whether a block is in the cache, the cache

control logic must simultaneously examine every line’s
tag for a match.

58 Computer Organization and Architecture

59 Computer Organization and Architecture
60 Computer Organization and Architecture
 A main memory address consists of a 22-bit tag and a 2-bit byte number. The 22-bit tag must
be stored with the 32-bit block of data for each line in the cache. Note that it is the leftmost
(most significant) 22 bits of the address that form the tag. Thus, the 24-bit hexadecimal
address 16339C has the 22-bit tag 058CE7. This is easily seen in binary notation:

memory address 0001 0110 0011 0011 1001 1100 (binary)

1 6 3 3 9 C (hex)
tag (leftmost 22 bits) 00 0101 1000 1100 1110 0111
(binary)
0 5 8 C E 7 (hex)

61 Computer Organization and Architecture

 Associative mapping

 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

62 Computer Organization and Architecture

 Set Associative Mapping

 Compromise that exhibits the strengths of both the direct and

associative approaches while reducing their disadvantages
 Cache consists of a number of sets
 Each set contains a number of lines
 A given block maps to any line in a given set
 e.g. 2 lines per set
 2-way associative mapping
 A given block can be in one of 2 lines in only one set

63 Computer Organization and Architecture

© 2016 Pearson Education, Inc., Hoboken
, NJ. All rights reserved.
© 2016 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
 Set 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 set = k
 Number of sets = v = 2d
 Number of lines in cache = m=kv = k * 2d
 Size of cache = k * 2d+w words or bytes
 Size of tag = (s – d) bits

© 2016 Pearson Education, Inc., Hoboken

, NJ. All rights reserved.
 Problems :
Chapter-4
4. Consider a memory system that uses a 32-
bit address to address at the byte level, plus
a cache that uses a 64-byte line size. Assume
a direct mapped cache with a tag field in the
address of 20 bits. Show the address format
and determine the following parameters:
number of addressable units, number of
blocks in main memory, number of lines in
cache, size of tag.

67 Computer Organization and Architecture

 Problems :
Chapter-4
5. Consider a machine with a byte addressable main memory of 216
bytes and block size of 8 bytes. Assume that a direct mapped cache
consisting of 32 lines is used with this machine.

a. How is a 16-bit memory address divided into tag, line number, and
byte number?
b. Into what line would bytes with each of the following addresses be
stored?
0001 0001 0001 1011
1100 0011 0011 0100
1101 0000 0001 1101
1010 1010 1010 1010
c. Suppose the byte with address 0001 1010 0001 1010 is stored in the
cache. What are the addresses of the other bytes stored along with it?
d. How many total bytes of memory can be stored in the cache?
e. Why is the tag also stored in the cache?

68 Computer Organization and Architecture

 Thank You !

69 Computer Organization and Architecture