MEMORY SYSTEM

 Basic Concepts
 Processor reads data from the memory by
loading the address of the required memory
location into the MAR register and setting the
R/W line to 1.
 The memory responds by placing the data from
the addressed location onto the data lines and
confirms this action by asserting the MFC signal.
 Upon receipt of the MFC signal, the processor
loads the data on the data lines into the MDR
register.

1
MEMORY SYSTEM

2
 MEMORY SYSTEM
 Basic Concepts

 Processor writes data into a memory location by

loading the address of this location into MAR and
loading the data into MDR.

 It indicates that a write operation is

______

involved by setting the R/W line to 0.

 If read or write operations involve consecutive address

locations in the main memory. Then a “block transfer”
operation can be performed in which the only address
sent to the memory is the one that identifies the first
location.

3
 MEMORY SYSTEM
 Basic Concepts
 Memory Access Time
 Time that elapses between the initiation of an operation and the
completion of that operation
• For example, the time between the Read and the MFC signals

 Memory Cycle Time

 Minimum Time delay required between the initiation of two
successive memory operations
• For example, the time between two successive Read operations

4
 MAIN MEMORY
TECHNOLOGIES

5
Main Memory Technologies
Semiconductor Memory Devices

Non-volatile Volatile

Read-only Random Access

Memory Memory
(ROMs) (RAMs)

6
 Main Memory Technologies

 Read Only Memories (ROMs)

 Random Access Memories (RAMs)

7
 ROMs
Mask-Programmable ROMs
- Diode ROMs

Field Programmable ROMs

- One-Time Programmable (OTP) ROMs or PROMs

- Erasable Programmable ROMs (EPROMs)
- Electrically Erasable Programmable ROMs (EEPROM)
- Flash Memory

8
 ROMs

Mask-Programmable Field-Programmable
ROMs ROMs

Diode ROMs

OTP ROMs EPROMs EEPROM Flash

(One-Time (Erasable (Electrically Memory
Programmable Programmable Erasable
ROMs) ROMs) Programmable
ROMs)

9
RANDOM ACCESS MEMORIES

10
 RAMs
RAM

stands for Random Access Memory

 Also known as Read/Write memory

(to differentiate it from ROM, which is read-only)

11
 RAMs

SRAMs DRAMs
(Static RAMs) (Dynamic RAMs)

Asynchronous Synchronous

Fast Page Extended Synchronous Rambus

Mode Data Out DRAM DRAM
(FPM) (EDO) (SDRAM) (RDRAM)
DDRAM
12
Static RAM

Static RAM, or SRAM, is a type of

RAM that uses a flip-flop as the basic
storage element.

13
 DRAM Storage Cell
One of the goals of main-memory technology is
to produce a high-bit density component
A part that requires six transistors per cell may
not be the best choice.
This drawback of static RAM has led designers
to dynamic RAM (DRAM) technology.

In a DRAM, the memory cell has been shrunk to a single bit-
select transistor and storage capacitor.

14
 Semiconductor RAM Memories
 Internal Organization of Memory Chips
 Memory cells are usually organized in the form of an array, in
which each cell is capable of storing one bit of information.
 Each row of cells constitutes a memory word and all cells of a row
are connected to a common line referred to as the word line,
which is driven by the address decoder on the chip.
 The cells in each column are connected to a Sense/Write circuit
by two bit lines.
 The sense/write circuits are connected to the data input/output
lines of the chip.

 During a Read operation, these circuits sense, or read, the

information stored in the cells selected by a word line and
transmit this information to the output data lines.

 During a write operation, the Sense/write circuits receive input

information and store it in the cells of the selected word.
15
Semiconductor RAM Memories

Memory
Cells

R/W
CS

16
Semiconductor RAM Memories

10-bit
address

17
 Static RAM Memories
 Memories that consist of circuits capable of
retaining their state as long as power is applied
are known as static memories.
 A static RAM cell implementation
 Two inverters are cross-connected to form a latch.
 The latch is connected to two bit lines by transistors
T1 and T2 .
 These transistors act as switches that can be
opened or closed under control of the word line.
 When the word line is at ground level, the
transistors are turned off and the latch retains its
state.

18
Static RAM

19
 Static RAM
 Read Operation
 In order to read the state of the SRAM cell, the word
line is activated to close switches T1 and T2.
 If the cell is in state 1, the signal on bit line b is high
and the signal on bit line b’ is low.
 The opposite is true if the cell is in state 0.
 Thus, b and b’ are complements of each other.
 Sense/Write circuits at the end of the bit lines
monitor the state of b and b’ and set the output
accordingly.

20
 Static RAM
 Write Operation

 The state of the cell is set by placing the appropriate

value on bit line b and its complement on b’, and
then activating the word line.

 This forces the cell into the corresponding state.

 The required signals on the bit lines are generated

by the Sense/Write circuit.

21

Static RAM
CMOS Cell
 Transistor pairs (T3 , T5) and (T4 , T6) form the inverters in the
latch.
 In state 1, the voltage at point X is maintained high by having
transistors T3 and T6 on, while T4 and T5 are off.
 Thus, if T1 and T2 are turned on (closed), but lines b and b’
will have high and low signals, respectively.
 The power supply voltage, Vsupply is 5V in older CMOS SRAMs or
3.3V in new low-voltage versions.
 SRAMs are said to be volatile memories because their contents
are lost when power is interrupted.
 A major advantage of CMOS SRAMs is their very low power
consumption because current flows in the cell only when the
cell is being accessed.
 Static RAMs can be accessed very quickly. Access times of just
few nanoseconds are found in commercially available chips.
 SRAMs are used in applications where speed is of critical
concern.

22
Static RAM

23
 Asynchronous DRAMs
 Static RAMs are fast, but they come at a high cost
because their cells require several transistors.

 Dynamic RAMS (DRAMs)

 Information is stored in a dynamic memory cell in
the form of a charge on a capacitor, and this charge
can be maintained for only tens of milliseconds.
 Since the cell is required to store information for a
much longer time, its contents must be periodically
refreshed by restoring the capacitor charge to its
full value.

24
 A Dynamic Memory Cell
 A dynamic memory cell consists of a capacitor, C, and a transistor
T
 In order to store information in this cell, transistor T is turned on
and an appropriate voltage is applied to the bit line.
 This causes a known amount of charge to be stored in the
capacitor.
 After the transistor is turned off, the capacitor begins to discharge.
 This is caused by the capacitor’s own leakage resistance and by
the fact that the transistor continues to conduct a tiny amount of
current, measured in pico-amperes, after it is turned off.
 Hence, the information stored in the cell can be retrieved correctly
only if it is read before the charge on the capacitor drops below
some threshold value.

25
Dynamic RAM Cell

26
 A Dynamic Memory Cell
 During a Read operation, the transistor in a selected cell is turned
on.

 A sense amplifier connected to the bit line detects whether the

charge stored on the capacitor is above the threshold value.

 If so, it drives the bit line to a full voltage that represents logic
value 1.
 This voltage recharges the capacitor to the full voltage that
represents logic value 1.
 If the sense amplifier detects that the charge on the capacitor is
below the threshold value, it pulls the bit line to ground level,
which ensures that the capacitor will have no charge,
representing logic value 0.
 Thus, reading the contents of the cell automatically refreshes its
contents.
 All cells in a selected row are read at the same time, which
refreshes the contents of the entire row.

27
A DRAM Memory System

R/W
CS

28
 A DRAM Memory System
 To reduce the number of pins needed for external connections, the
row and column addresses are multiplexed
 During a read or a Write operation, the row address is applied first.
 It is loaded into the row address latch, in response to a signal pulse on the
Row Address Strobe (RAS) input of the chip.
 Then a read operation is initiated, in which all cells on the selected row are
read and refreshed.
 Shortly after the row address is loaded, the column address is applied to the
address pins and loaded into the column address latch under control of the
Column Address Strobe (CAS) signal.
 The information in this latch is decoded and the appropriate group of 8
Sense/Write circuits are selected. If the R/W control signal indicates a Read
operation, the output values of the selected circuits are transferred to the
data lines , D7-0

 For a write operation, the information on the D7-0 lines is transferred to the
selected circuits
 This information is then used to overwrite the contents of the selected cells in
the corresponding 8 columns.

29
 Synchronous DRAMs
 More recent developments in memory technology have resulted
in DRAMs whose operation is directly synchronized with a clock
signal

 Such memories are known as Synchronous DRAMs (SDRAMs)

 SDRAMs have several different modes of operation which can be

selected by writing control information into a mode register

 For example, burst operations of different lengths can be specified.

 SDRAMs have built-in refresh circuitry. A part of this circuitry is a

refresh counter, which provides the addresses of the rows that are
selected for refreshing.

 In a typical SDRAM, each row must be refreshed at least every 64

ms.

30
Synchronous DRAMs

31
 Synchronous DRAMs
 Memory latency
 Refers to the amount of time it takes to transfer a word of
data to or from the memory
 In the case of reading or writing a single word of data, the
latency provides a complete indication of memory
performance.

 Memory Bandwidth
 Number of bits or bytes that can be transferred in one second
is referred to as Memory Bandwidth.
 The bandwidth of a memory unit depends on the speed of
access to the stored data and on the number of bits that can
be accessed in parallel.
 The bandwidth is the product of the rate at which data are
transferred and the width of the data bus.

32
Synchronous DRAMs

33
Large Memory Systems

R/W
CS

34
Large Memory Systems

D24-31 D16-23 D8-15 D0-7

35
READ-ONLY MEMORIES
 ROM
 A logic value 0 is stored in the cell if the transistor is
connected to ground at point P, otherwise, a 1 is stored.
 The bit line is connected through a resistor to the power
supply.
 To read the state of the cell, the word line is activated.
 Thus, the transistor switch is closed and the voltage on the
bit line drops to near zero if there is connection between the
transistor and ground.
 If there is no connection to ground, the bit line remains at the
high voltage, indicating a 1.
 A sense circuit at the end of the bit line generates the proper
output value.
 Data are written into a ROM when it is manufactured.

36
ROM

37
READ-ONLY MEMORIES
 PROM (One-Time Programmable ROM)

 Allows data to be loaded by the user

 Programmability is achieved by inserting a fuse at
point P. (fuse-programmable)
 Before it is programmed, the memory contains all
0s.
 The user can insert 1’s at the required locations by
burning out the fuses at these locations using high-
current pulses
 Cannot be reprogrammed
 PROMs provide a faster and considerably less
expensive approach because they can be
programmed directly by the user.

38
READ-ONLY MEMORIES
 EPROM (Erasable Programmable ROM)
 Allows the stored data to be erased and new data to
be loaded.
 It provides considerable flexibility during the
development phase of digital systems
 Since EPROMs are capable of retaining stored
information for a long time, they can be used in
place of ROMs while software is being developed.
 In this way, memory changes and updates can be
easily made.

39
READ-ONLY MEMORIES
 EPROM (Erasable Programmable ROM)

 In an EPROM cell, the connection to ground is made at point P

and a special transistor is used, which has the ability to
function either as a normal transistor or as a disabled
transistor that is always turned off.
 This transistor can be programmed to behave as a
permanently open switch, by injecting charge into it that
becomes trapped inside.
 The important advantage of EPROM chips is that their
contents can be erased and reprogrammed.
 Erasure requires dissipating the charges trapped in the
transistors of memory cells; this can be done by exposing the
chip to ultraviolet light.
 For this reason, EPROM chips are mounted in packages that
have transparent windows.

40
READ-ONLY MEMORIES
 EEPROM (Electrical Erasable Programmable ROM)

 A significant disadvantage of EPROMs is that a chip must be

physically removed from the circuit for reprogramming and
that its entire contents are erased by the ultraviolet light.
 It is possible to implement another version of erasable PROMs
that can be both programmed and erased electrically.
 Such chips, called EEPROMs, do not have to be removed for
erasure.
 Moreover, it is possible to erase the cell contents selectively.
 The only disadvantage of EEPROMs is that different voltages
are needed for erasing, writing, and reading the stored data.

41
READ-ONLY MEMORIES
 FLASH MEMORY
 An approach similar to EEPROM technology has more recently
given rise to flash memory devices.
 A flash cell is based on a single transistor controlled by
trapped charge, just like an EEPROM cell.
 In EEPROM, it is possible to read and write the contents of a
single cell.
 In a flash device, it is possible to read the contents of a single
cell, but it is only possible to write an entire block of cells.
 Prior to writing, the previous contents of the block are erased.
 Flash devices have greater density, which leads to higher
capacity and a lower cost per bit.
 They require a single power supply voltage, and consume less
power in their operation.

42
READ-ONLY MEMORIES
 FLASH CARDS

 One way of constructing a larger module is to mount

flash chips on a small card.
 Such flash cards have a standard interface that
makes them usable in a variety of products.
 A card is simply plugged into a conveniently
accessible slot.
 Flash cards come in a variety of memory sizes.
 Typical sizes are 8, 32, and 64 Mbytes.
 A 64-MB flash card can store an hour of music

43
READ-ONLY MEMORIES
 FLASH DRIVES

 Larger flash memory modules have been developed

to replace hard disk drives.
 These flash drives are designed to fully emulate the
hard disks, to the point that they can be fitted into
standard disk drive bays.
 The fact that flash drives are solid state electronic
devices that have no movable parts provides some
important advantages.
 They have shorter seek and access times, which
result in faster response.
 They have lower power consumption, which makes
them attractive for battery driven applications and
they are insensitive to vibration.
44
 Data Transfer Rate
The quantity of data that a processor can transfer in one second is called the
data transfer rate. Typically measured in MB/s
In some literature that data transfer is expressed in MHz and described as the
memory bandwidth.

The two terms are interchangeable, that is, 10 MB/s = 10 MHz.

Data Transfer rate = Number of bytes transferred per cycle

time for one bus cycle

The time for one bus cycle can be written as

n x TCLK = n/f

where n represents the number of system clock pulses per bus cycle,
TCLK is the period of external bus clock, and f is the frequency of the bus
clock.

Data Transfer Rate = Number of bytes transferred per bus cycle x f

n
45
 Cache Memory
Critical factor in System design
- the speed at which locations can be accessed in
memory

Main Memory speed

- Semiconductor memory speeds are characterized by the
memory access time and memory cycle time.
 Memory access time
- time between the submission of a memory request and the
completion of transfer of information into or from the addressed
location.

 Memory cycle time

- minimum time that must elapse between two successive
operations to access locations in the memory (i.e., Memory
Read/write cycle time)

46
47
 Cache Memory
Processor Speed
- Processors are generally able to perform operations on
operands faster than the access time of large capacity main
memory.

- Semiconductor memory which can operate at speeds

comparable with the operation of the processor exists

- It is not economical to provide all the main memory with

very high speed semiconductor memory ( Cost of the system
increases)

Solution
- Introduce a very high speed random access memory
called the cache operating at the speed required by the
processor between the main memory and the processor.
- Program instructions and data are transferred to the
cache, which are then accessed by the processor.

48
49
 Cache Memory
Cache

- a relatively small capacity but high speed

memory inserted between the processor and
the main memory

Purpose

- The cache is introduced into the system

 to decrease the effective memory access time
 to increase the operational speed of the system.

50
 Cache Memory
Program Characteristics

- Program (code) is generally executed sequentially

- Virtually all programs repeat sections of code

(i.e., contain loops) and repeatedly access the same or
nearby data.

- Analysis of programs shows that most of their

execution time is spent on routines in which any
instructions are executed repeatedly.
Example: simple loops, nested loops, procedures that
repeatedly call each other
-This characteristic is embodied in the Principle of Locality

51
 Cache Memory
The effectiveness of the cache mechanism is based on
the property of computer programs called Locality of
reference

Principle of Locality (Locality of Reference)

 states that programs access a relatively small portion
of their address space at any instant of time.
 obeyed by most programs

There are two different types of locality:

• Temporal Locality
• Spatial Locality

Locality in programs arises from simple and natural

program structures.

52
 Cache Memory
Temporal Locality (Locality in time)

 Individual locations, once referenced, are likely to be

referenced again in the near future
 If an item is referenced, it will tend to be referenced
again soon.
 Found in instruction loops, data stacks and variable
accesses.
 For example, most programs contain loops, so
instructions and data are likely to be accessed
repeatedly, showing high amounts of temporal locality.

 Temporal locality is essential for effective cache

53
 Cache Memory
Spatial Locality (Locality in space)
 References, including the next location, are likely to be near the
last reference.
 If an item is referenced, items whose addresses are close by will
tend to be referenced soon.
 References to the next locations are sometimes separated into a
third aspect, known as sequential locality
 Spatial locality describes the characteristic that programs access a
number of distinct regions.
 Sequential locality describes the sequential locations being
referenced and is a main attribute of program construction.
 Since instructions are normally accessed sequentially, programs
show high spatial locality.
 Accesses to data also exhibit a natural spatial locality.
 For example, accesses to elements of an array or a record will
naturally have high degrees of spatial locality.

54
 Cache Memory
Taking advantage of Temporal locality
 Programs consist of loops of instructions which are
executed many times.
 Usually length of a loop is quite small.
 These loops of instructions are loaded into the cache
from main memory
 Once these loops of instructions are in cache, processor
can access them several times before new instructions
are required from the main memory thereby reducing
the effective memory access time
 The same situation applies to data; if data is
repeatedly accessed.

55
 Cache Memory
Taking advantage of Spatial locality
To take advantage of spatial locality, instead of
transferring a byte or word from the main memory to
cache, a series of sequential locations called a cache line
or a cache block is transferred from main memory to
cache

For best performance, the line should be transferred

simultaneously across a wide data bus to the cache, with
one byte or word being transferred from each memory
module.

This also enables the access time of the main memory to

be matched to the cache.

56
 Cache Memory
Taking advantage of Spatial locality

Eight memory modules together create an 8 byte line of the cache.

The addresses are distributed across the memory modules so that successive bytes
are in successive memory modules.
The most significant part of the memory address is sent to all memory modules to
access one location from each memory module simultaneously.
The three least significant bits of the memory address identify the byte.
Hence eight consecutive memory locations can be read into the cache or written57from
the cache back to the main memory simultaneously
 Memory Hierarchy
The take advantage of the principle of locality, computer’s
 To
memory system is organized as a hierarchy
 A memory hierarchy consists of multiple levels of memory
with different speeds and sizes
 The fastest memories are more expensive per bit than the
slower memories and thus are usually smaller.

58
Memory Hierarchy

59
Memory Hierarchy

60
 Memory Hierarchy
 Today, there are primary technologies used in building
memory hierarchies.
 Main memory is implemented from DRAM (dynamic
random access memory),
 while levels closer to the processor (caches) use SRAM
(static random access memory).
 DRAM is less costly per bit than SRAM, although it is
substantially slower.
 The price difference arises because DRAM uses
significantly less area per bit of memory, and DRAMs thus
have larger capacity for the same amount of silicon.
 The third technology, used to implement the largest and
slowest level in the hierarchy, is magnetic disk.

61
62
 Cache Memory
 The processor simply issues Read and
Write requests using addresses that refer
to locations in the main memory.

 The cache controller determines

whether the requested word currently
exists in the cache.

 If it does, the Read or write operation

is performed on the appropriate cache
location.
63
 Cache Memory
Cache Hit
 If the data requested by the processor
appears in some block in the cache, this is
called a cache hit.

 Cache Miss
 If the data is not found in the cache, the
request is called a cache miss.
 The lower level in the hierarchy is then
accessed to retrieve the block containing
the requested data.

64
 Cache Memory
Hit Ratio
The probability that the required word is already in
the cache depends upon the program and on the
size and organization of the cache
Typically 70-90 percent of references will find their
words in the cache.
A hit occurs when a location in the cache is found
immediately,
A miss occurs when a location in the cache is not
found and a reference to the main memory is
necessary.

65
 Cache Memory
Hit Ratio

The cache hit ratio, h, is defined as :

h = Number of times required word found in cache

Total number of references

The cache hit ratio ( or hit rate ) h is also the probability that
a word will be found in the cache.

The miss ratio ( or miss rate) is given by 1 – h.

66
 Cache Read Operation
Cache Read Hit
When the addressed word in a Read operation is in the
cache, a read hit occurs.
Reading the word in the cache does not affect the cache
contents

Cache Read Miss

When the addressed word in a Read operation is not in

the cache, a read miss occurs.
The block of words that contains the requested word is
copied from the main memory into the cache.
After a memory Read instruction, there is no
discrepancy between the cache word and the copy held
in the main memory
67
 Cache Read Policy upon a cache miss
 Two possible strategies for Cache Read Miss

 First strategy

- Missed block is brought from Main memory to the

cache, at the same time the required word is forwarded
immediately to the CPU as soon as it is available.

- This approach is called load-through or early

restart which reduces the processor’s waiting period

Second strategy
- Missed block is brought from the main memory
and entirely stored in the cache and then the required
word is forwarded to the CPU.

68
Cache Write Operation

69
 Cache Write Operation

After a write operation to the cache, it is possible

that the cache word and copy held in the main
memory may be different.
Cache Coherence
It is necessary to keep the cache and the main memory
copy identical if input/output transfers operate on the
main memory contents, or if multiple processors
operate on the main memory, as in a shared memory
multiple processor system.
Coherence between a cache word and its copy in the
main memory should be maintained at all times, if at all
possible.

70
 Cache Write Policies

Determine the degree of coherence that can be

maintained between cache words and their
counterparts in the main memory

 Two main Cases

 Cache write policies upon a Cache Hit

Cache write policies upon a Cache Miss

71
 Cache Write Policies upon a Cache Hit

 Basically two possible write policies upon a cache

Hit

 Write-Through Policy

 Write-back Policy

72
Cache Write Policies upon a Cache Hit

 Write-Through Policy
 Every write operation to the cache is repeated to the
main memory at the same time.
i.e., the cache location and the main memory location
are updated simultaneously.
The additional write operation to the main memory will
take much longer than to the cache and will dominate
the access time for write operations
It maintains coherence between the cache blocks and
their counterparts in the main memory at the expense of
the extra time needed to write to the main memory
This leads to an increase in the average access time

73
Cache Write Policies upon a Cache Hit
 Write-back Mechanism

All writes are made only to the cache.

Write to the main memory is postponed until a
replacement is needed.
i.e., the write operation to the main memory is
only done at line or block replacement time.
At this time, the block displaced by the incoming
block might be written back to the main memory.

74
 Cache Write Policies upon a Cache Hit
 Write-back Policy
Every cache block is assigned a bit, called the dirty
bit, to indicate that atleast one write operation
has been made to the block while residing in the
cache.
At replacement time, the dirty bit is checked, if it
is set, then the block is written back to the main
memory, otherwise it is simply overwritten by the
incoming block.
This policy eliminates the increase in the average
access time, however, coherence is only
guaranteed at the time of replacement.
75
Cache Write Policies upon a cache miss

 Two main Schemes

 Allocate on write (Fetch on write)

 Non-allocate on write (No fetch on write)

76
 Cache Write Policies upon a cache miss

 Allocate on write (Fetch on write)

The requested word/line is brought from the

main memory into the cache for a write operation
on a cache miss and then updated

 Non-Allocate on write (No Fetch on write)

The word/line is written back to the main memory

(i.e., updated) and not brought to the cache for a
write operation on a cache miss

77
Cache Write Policies

 Write-through mechanism uses

no fetch on write (Non-allocate on write) policy

 Write-back mechanism uses

fetch on write (Allocate on write) policy

78
Cache Memory
Organizations

79
 Cache Memory Organizations
There are three important ways that a cache can be
arranged internally to store the cached data

 Fully Associative Mapping

 Direct Mapping
 Set-Associative Mapping
In all these cases, processor references the cache with
the main memory address of the data it wants.
Hence, each cache organization must use this address to
find the data in the cache if it is stored there, or to
indicate to the processor when a miss has occurred.
The problem of mapping the information held in the main
memory into the cache must be totally implemented in
hardware to achieve improvements in the system
operation.

80
 Full Associative Mapped Cache
 Fully Associative Mapping Approach

A simple way of relating cached data to the main memory

address is by storing both the memory address and the
corresponding data together in the cache
A fully associative cache requires the cache to be
composed of
- Associative memory (Content Addressable Memory,
CAM) holding both the memory address and the data for
each cached line. Each cache location requires a separate
comparator.
The incoming memory address is simultaneously compared
with all stored addresses using the internal logic of the
associative memory
If a match is found, the corresponding data is read out.

81
 Full Associative Mapped Cache
 The data associated with each address in the cache can be more
than one word, i.e., a block of consecutive locations, or line, to
take advantage of spatial locality.

TAG

82
 Fully Associative Mapped Cache
The address from the processor is divided into fields - Tag, Word, Byte

TAG WORD BYTE

Memory Address from Processor

The Tag field consists of the higher significant bits of the address, which
is used to identify the line or block in the cache

The Word field bits are used to access a word within the selected line

The Byte field bits are used to access a byte within the selected word.

83
Fully Associative Mapped Cache

84
 Full Associative Mapped Cache

Question

A byte-addressable computer has a 16 MB main memory

with a word size of 32 bits and a cache of 8 KB.
Determine the number of bits in each field of the
memory address in the following organization :

Fully Associative mapping with a line or block size of

eight words

85
 Full Associative Mapped Cache
Solution
Given : Size of Main Memory = 16 MB = 224 bytes
Size of cache = 8 KB = 213 bytes
Word size = 32 bits = 22 bytes
Line or block size = 8 words = 23 words

# of bits in Main memory address = 24 bits

# of words in cache = cache size / word size
= 213 / 22 = 211 words
# of blocks in cache = cache size / line size
= 211 / 23 = 28 lines
Hence, # of WORD field bits = 3 bits
# of BYTE field bits = 2 bits
# of TAG field bits = 24 – (3+2) = 19 bits
86
 TAG WORD BYTE
Main Memory
1111001101011100011 101 10 Address

TAG Memory Block Memory

=
0
ABCD12F34AB789AB
1111001101011100011
= DEF23CD45DEAB12B
1 DACB456C789E38FB

789E38FB
CA4B5CAE896723AD

38
=
0
Full Associative Mapped Cache 87
 Full Associative Mapped Cache
 Advantages

Provides greatest flexibility of holding combinations of lines in the cache

Minimum conflict for a given sized cache
Higher hit ratio
High Utilization of cache

 Disadvantages

Complex approach
Most Expensive due to the cost of the associative memory
Requires a Replacement algorithm to select a line to remove upon a miss
Algorithm must be implemented in hardware to maintain a high speed of
operation

88
 Valid Bit in Cache
 If the cache line size is equal to the size of the external
data path between the main memory and cache
- the whole line can be transferred to and from the cache in one
transaction (i.e., one bus cycle required)
 If the line size is greater than the size of the external
data path to the main memory,
- multiple transfers will be necessary to fill the line from the
main memory and to transfer altered lines back to the main
memory (i.e., multiple bus cycles required)
 It is possible for the line not to hold all the words
associated with the line at the time that words are being
transferred into the cache one after the other; some
words might be from a previous line
 To handle this situation, each word in the cache is
provided with a valid bit which is set when the word
forms part of a line having the same address as the
stored address.
89
 When a word is loaded, the corresponding valid bit is set
 Valid Bit in Cache
 When the processor accesses the cache, the
address tag from the processor is compared with all
the address tags stored in the cache.
 If a match is found, the valid bit associated with the
required word is checked to see whether the
stored word is a valid part of the line
 If it is valid, the word is accessed, otherwise the
main memory is accessed and the cache is loaded
with the word.
 Even if a complete line can be transferred in one
bus transaction, valid bits are usually required in all
cache organizations to handle the start-up situation
when a cache will hold random pattern of bits.

90
 TAG WORD BYTE
Main Memory
1111001101011100011 101 10 Address

TAG Memory VB Block Memory

0
= 0
0
1 ABCD12F34AB789AB
1111001101011100011 1
= DEF23CD45DEAB12B
1 DACB456C789E38FB

789E38FB
CA4B5CAE896723AD

38
0
= 0
0
Full Associative Mapped Cache
91
 Direct Mapped Cache
 Direct Mapping Approach
 In direct mapping, the cache consists of normal high speed
random access memory

Each location in the cache holds the data, at an address in

the cache given by the lower significant bits (i.e., Index bits)
of the main memory address

This enables the line to be selected directly from the lower

significant bits of the memory address

The remaining higher significant bits of the address (i.e. tag

bits) are stored in the cache with the data to complete the
identification of the cached data.

92
 Direct Mapped Cache
The address from the processor is divided into fields - Tag, Index,
Word, Byte

TAG INDEX WORD BYTE

Memory Address from Processor

The Tag field consists of the higher significant bits of the address, which
is used to identify the line or block in the cache

The Index field is the next higher significant bits of the address which is
used to address the line or block in the cache.

The Word field bits are used to access a word within the selected line or
block
The Byte field bits are used to access a byte within the selected word.

93
Direct Mapped Cache

94
 Direct Mapped Cache
When the memory is referenced, the index is first used to access a
line (or block) in the cache.
Then the tag stored in the accessed line is read and compared with the
tag in the address.
If the two tags are the same, indicating that the line is the one
required, access is made to the addressed cache line.

- Word field bits are then used to select the required word within the selected
line

- Byte field bits are then used to select the byte within the selected word

If the tags are not the same, indicating that the required word is not in
the cache, reference is made to the main memory to find it

- For a memory read operation, the line is then transferred from main memory
to the cache where it is accessed. It is possible to pass the information to the cache
and the processor simultaneously ( known as read-through the cache, on a miss)

- For a write operation, cache location is to be altered. The main memory may be
altered at the same time (known as write-through the cache) or later

95
Direct Mapped Cache

INDEX

96
 Direct Mapped Cache
 Direct Mapping Approach

The corresponding lines with the same index in the main

memory will map into the same line in the cache

Hence only lines with different indices can be in the cache

at the same time.

A Replacement algorithm is not necessary, since there is

only one allowable location for each incoming line.

97
Direct Mapped Cache

98
 Direct Mapped Cache

Question

A byte-addressable computer has a 16 MB main memory

with a word size of 32 bits and a cache of 8 KB.
Determine the number of bits in each field of the
memory address in the following organization :

Direct mapping with a line or block size of one word

99
 Direct Mapped Cache
Solution
Given : Size of Main Memory = 16 MB = 224 bytes
Size of cache = 8 KB = 213 bytes
Word size = 32 bits = 22 bytes
Line size = 1 word

# of bits in Main memory address = 24 bits

# of words in cache = cache size / word size
= 213 / 22 = 211 words
# of lines in cache = cache size / line size
= 211 / 1 = 211 lines
Hence, # of INDEX field bits = 11 bits
# of BYTE field bits = 2 bits
# of TAG field bits = 24 – (11+2)
= 11 bits

100
 TAG INDEX BYTE
11110011010 00000000110 10 Main Memory
Address

0 6 2047

TAG Memory VB Block Memory

12
11110011010 1 ABCD12F3
comparator
=
1

Cache Hit 101

Direct Mapped Cache 1
 Direct Mapped Cache
 Advantages
Simple Hardware and Low cost
High speed of operation
No replacement algorithm necessary

 Disadvantages

Performance drops significantly if accesses are

made to locations with the same index.
Hit ratio lower than the associative mapping
methods.
Poor utilization of cache

102
 Set-Associative Mapped Cache
 Set-Associative Mapping Approach

Set-associative mapping allows a limited number of lines, with the

same index and different tags, in the cache

It can be considered as a compromise between a fully associative

cache and a direct mapped cache

The cache is divided into “sets” of lines

A four-way set associative cache would have four lines in each set.

The number of lines in a set is known as the associativity or setsize

Each line in each set has a stored tag which, together with the index
(set number), completes the identification of the line.

103
 Set-Associative Mapped Cache
The address from the processor is divided into fields - Tag, Index or
set , Word, Byte

TAG SET WORD BYTE

Memory Address from Processor

The Tag field consists of the higher significant bits of the address, which
is used to identify the line in the selected set in the cache

The Set or Index field is the next higher significant bits of the address
which is used to address the set in the cache.

The Word field bits are used to access a word within the selected line
The Byte field bits are used to access a byte within the selected word.

104
Set-Associative Mapped Cache

105
 Set-Associative Mapped Cache
 Set-Associative Mapping Approach

 First, the index (or Set field bits) of the address from the processor is
used to access the set.

Then, comparators are used to compare all tags of the selected set
with the incoming tag.

If a match is found, the corresponding location is accessed, otherwise,

an access to the main memory is made.

The number of comparators required in the set-associative cache is

given by the number of lines in a set.

The replacement algorithm for set-associative mapping need only

consider the lines in one set, as the choice of set is predetermined by
the Set field bits in the address.

106
Set Associative Mapped Cache

107
 Set-Associative Mapped Cache

Question

A byte-addressable computer has a 16 MB main memory

with a word size of 32 bits and a cache of 8 KB.
Determine the number of bits in each field of the
memory address in the following organization :

Set-associative mapping with a set size of two lines or

blocks and block size of one word

108
 Set-Associative Mapped Cache
Solution
Given : Size of Main Memory = 16 MB = 224 bytes
Size of cache = 8 KB = 213 bytes
Word size = 32 bits = 22 bytes
Line size = 1 word
Set size = 2 lines

# of bits in Main memory address = 24 bits

# of words in cache = cache size / word size
= 213 / 22 = 211 words
# of lines in cache = cache size / line size
= 211 / 1 = 211 lines
# of sets in cache = # of lines in cache / set size
= 211 / 2 = 210 sets
Hence, # of SET field bits = 10 bits
# of BYTE field bits = 2 bits
# of TAG field bits = 24 – (10+2)
= 12 bits

109
 Set-associative Mapped Cache
 Advantages

Moderate hardware cost as the number of comparators required is

equal to number of lines in the set.

Moderate speed of operation

Moderate utilization of cache

Replacement algorithm necessary but need to consider only the lines

in one set.

Hit ratio better than the direct mapping method

110
 Cache Performance
 Impact of the cache on the overall performance of the
computer

Let h be the hit rate

M - Miss Penalty, that is, the time to
access information in the main memory
C - the time to access information in the
cache
The average access time experienced by
the processor is
tave = h C + (1 - h) M
where (1 – h) is the miss rate

111
 Cache Performance
Question 1 :
If the computer has no cache, then using a fast processor and a typical
DRAM main memory, it takes 10 clock cycles for each memory read
access
Suppose the computer has a cache that holds 8-word blocks and an
interleaved main memory.
Time to access information in the cache = 1 cycle
17 cycles are needed to load a block into the cache.
Assume that 30 percent of the instructions in a typical program
perform a read or a write operation, which means that there are 130
memory accesses for every 100 instructions executed.
Assume that the hit rates in the cache are 0.95 for instructions and 0.9
for data.
Assume that the miss penalty is the same for both read and write
accesses.
Determine the improvement in performance that results from using
the cache
112
 Cache Performance
Answer :
Given -
- Miss penalty M = 17 cycles
- hIM = 0.95
- hDM = 0.9
- C = 1 cycle
- Clock cycle for each main memory access = 10
- Instruction Memory accesses = 100
- Data Memory Accesses = 30
Average Instruction memory access time,
tave(IM) = hIM C + (1 - hIM ) M
= 0.95x 1 + (1 - 0.95) x 17
= 0.95 + 0.05x 17 = 1.8 cycles

113
 Cache Performance
Answer (continued):
Average Data memory access time,
tave(DM) = hDM C + (1 - hDM ) M
= 0.9 x 1 + (1 - 0.9) x 17
= 0.9 + 0.1x 17 = 2.6 cycles
Time without cache = Memory accesses x clock
cycles for each memory access
= 130 x 10 = 1300 cycles
Time with cache =
Instruction Memory accesses x average Instruction
memory access time + Data Memory accesses x average
memory access time
= 100 x 1.8 + 30 x 2.6
= 180 + 78 = 258 cycles
114
 Cache Performance
Answer (continued):
Improvement in performance that results from using the
cache
= Time without cache
Time with cache
= 1300 = 5.04
258
This result suggests that the computer with the cache
performs five times better.

115
 Cache Performance
Answer (continued):

• Consider how effective this cache is compared to an ideal

cache that has a hit rate of 100 percent (in which case, all
memory references take one cycle)
Average Access time for ideal case = 1

Time with ideal cache = 130 x 1 = 130

One rough estimate of relative performance for these caches

= Time with actual cache
Time with ideal cache
= 258 = 1.98
130

This means that the actual cache provides an environment in which

the processor effectively works with a large DRAM-based main
memory that appears to be only two times slower than the cache.

116