CHAPTER-3

Computer Memory System and

Cache memory

1
 Computer Memory System and Cache
memory
 Computer Memory System Overview
 Key Characteristics of Computer Memory
Systems
 Memory hierarchy
 Cache Memory
 Cache Memory Principals
 Cache/Main Memory Structure
 Elements of cache design
 Cache Address-Logical cache address or
Physical cache address,
 Cache Size
 Cache Memory Mapping
 Replacement Algorithm.
2
COMPUTER MEMORY SYSTEM
OVERVIEW
 Computer memory is organized into a hierarchy.
 At the highest level (closest to the processor) are the processor
registers.
 Next comes one or more levels of cache, When multiple levels are
used, they are denoted L1, L2, and so on.
 Next comes main memory, which is usually made out of dynamic
random-access memory (DRAM).
All of these are considered internal to the computer system.
 The hierarchy continues with external memory
 with the next level typically being a fixed hard disk
 and one or more levels below that consisting of removable media
such as optical disks and tape.

3
Key Characteristics of Computer Memory
Systems.
The topic computer memory system can be understood by the study
of Key Characteristics of Computer Memory Systems.

• Location

• Capacity

• Unit of Transfer

• Access Method

• Performance

• Physical Type

• Physical Characteristics and Organization

4
KEY CHARACTERISTICS OF MEMORY

1. LOCATION
refers to whether memory is internal and external to the
computer
a. Internal: Registers, main memory, cache
b. External: Disk, Tape, flash drive

2. CAPACITY
• Number of words, Number of bytes:
For internal memory, this is typically expressed in terms of bytes
(1 byte 8 bits) or words. Common word lengths are 8, 16, and 32
bits.
3. UNIT OF TRANSFER
Is number of bits read out or written into memory.
Expressed in word or block of data 5
4. ACCESS METHODS

1. Sequential Access:
In this access method data is retrieved in same order in which thy have been
stored.
Memory is organized into units of data, called records. Access must be made in
a specific linear sequence. Stored addressing information is used to separate
records and assist in the retrieval process. A shared read–write mechanism is
used, and this must be moved from its current location to the desired location,
passing and rejecting each intermediate record. Thus, the time to access an
arbitrary record is highly variable.

2. Direct Access:
As with sequential access, direct access involves a shared read–write
mechanism. However, individual blocks or records have a unique address
based on physical location. Access is accomplished by direct access to reach a
general vicinity plus sequential searching, counting, or waiting to reach the final
location.
3. Random Access:
Each addressable location in memory has a unique, physically wired-in
addressing mechanism. The time to access a given location is independent of
the sequence of prior accesses and is constant. Thus, any location can be
selected at random and directly addressed and accessed. Main memory and
some cache systems are random access.
6
Sequential and Random Access

7
Direct access

8
5. Performance
1. Access time((latency)
Time it takes to perform a read or write operation.
For random-access memory, this is the time it takes to perform a read
or write operation, that 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.
For non-random-access memory, access time is the time it takes to
position the read–write mechanism at the desired location.

2. Memory cycle time: Access time + Additional time

This concept is primarily applied to random-access memory and consists
of the access time plus any additional time required before a second
access can commence.

9
[Link] Rate:
This is the rate at which data can be transferred into or out of a memory
unit.

NOTE:

For random-access memory, it is equal to 1/(cycle time).

Tr= 1/cycle time
For non-random-access memory,
the following relationship holds:

10
Memory Hierarchy
A typical hierarchy is illustrated in
Figure 4.1.
As one goes down the hierarchy, the
following occur:

a. Decreasing cost per bit

b. Increasing capacity
c. Increasing access time
d. Decreasing frequency of access of
the memory by the processor

Thus, smaller, more expensive, faster

memories are supplemented by
larger, cheaper, slower memories.
The key to the success of this
organization is item (d): decreasing
frequency of access Figure 4.1 The Memory
Hierarchy 11
RULES OF HIERARCHY

A variety of technologies are used to implement memory systems, and

across this spectrum of technologies, the following relationships hold
 Faster access time, greater cost
 Greater capacity, smaller cost
 Greater capacity, slow access time

12
CACHE MEMORY

• A small amount of fast memory that stays between normal main

memory and CPU.

• May be located on CPU chip or module.

• Intended to allow access speed approaching register speed.

• Used to hold frequently used data.

Cache memory is intended to give memory speed approaching that of the

fastest memories available, and at the same time provide a large memory
size at the price of less expensive types of semiconductor memories.

. 13
CACHE MEMORY PRINCIPLES

The cache contains a copy of portions of main memory.

 When the processor attempts to read a word of memory, a check is

made to determine if the word is in the cache.

 If so, the word is delivered to the processor.

 If not, a block of main memory, consisting of some fixed number of

words, is read into the cache and then the word is delivered to
the processor.

14
Figure depicts the use of Single and multiple levels of cache.

Single cache

Three-level cache
In the figure below shows the use of multiple levels of cache. The L2 cache is slower and
typically larger than the L1 cache, and the L3 cache is slower and typically larger than the
L2 cache.

15
Cache/Main Memory Structure
• Main memory consists of up to 2n addressable words, with
each word having a unique n-bit address.
• For mapping purposes, this memory is considered to consist of a number
of fixed length blocks of K words each.
• There are M=2n/K blocks in main memory.

• The cache consists of m blocks, called lines.

• Each line contains K words, plus a tag of a few bits. Each line also
includes control bits (not shown), such as a bit to indicate whether the
line has been modified since being loaded into the cache.
• The length of a line, not including tag and control bits, is the
line size.
• The line size may be as small as 32 bits, with each “word” being
a single byte; in this case the line size is 4 bytes.
16
• The number of lines is considerably less than the number of main
memory blocks (m<<M).

• If a word in a block of memory is read, that block is

transferred to one of the lines of the cache. Because there are more
blocks than lines, an individual line cannot be uniquely and
permanently dedicated to a particular block. Thus, each line includes
a tag that identifies which particular block is currently being stored.

• The tag is usually a portion of the main memory address.

17
Cache/Main Memory Structure

18
Elements of cache design
There are a large number of cache implementations, there are a few

basic design elements that serve to classify and differentiate cache

architectures.

 Cache Address-Logical cache address or Physical cache address.

 Cache Size

 Cache Memory Mapping

 Replacement Algorithm.

19
 Cache Addresses

• Virtual memory is a facility that allows programs to address

memory from a logical point of view, without regard to the amount
of main memory physically available.

• When virtual memory is used, the address fields of machine

instructions contain virtual addresses. For reads to and writes from
main memory, a hardware memory management unit (MMU)
translates each virtual address into a physical address in main
memory.

• When virtual addresses are used, the system designer may

choose to place the cache between the processor and the
MMU or between the MMU and main memory.
20
• A logical cache, also known as a virtual cache, stores data
using virtual addresses.

• The processor accesses the cache directly, without

going through the MMU.

• A physical cache stores data using main memory physical

addresses.

21
Addresses (Logical & Physical)

Logical Address

Physical Address
22
 Cache Size

We would like the size of the cache to be small enough so that the

overall average cost per bit is close to that of main memory

alone, and large enough so that the overall average access time is

close to that of the cache alone.

23
 Cache Memory Mapping
Memory Mapping means, making connection or link between main

memory with the cache memory.

Because there are fewer cache lines than main memory blocks, an

algorithm is needed for mapping main memory blocks into cache

lines.

The choice of the mapping function dictates how the cache is

organized. Three techniques can be used:

 direct

 associative, and

 set associative.
24
Direct Mapping
The simplest technique, known as direct mapping, maps each block of
main memory into only one possible cache line.

The mapping is expressed as:

i = j modulo m

where

i: cache line number

j: main memory block number
m: number of lines in the cache

Each block of main memory maps into one unique line of the cache.
The next blocks of main memory map into the cache in the same fashion;
that is, block Bm0 of main memory maps into line L0 of cache, block Bm1
maps into line L1, and so on.

25
Direct Mapping

26
 The direct mapping technique is simple and inexpensive to

implement.

 Its main disadvantage is that there is a fixed cache location for any

given block.

 If a program happens to reference words repeatedly from two

different blocks that map into the same line, then the blocks will be

continually swapped in the cache, and the hit ratio will be low (a

phenomenon known as thrashing).

27
Associated mapping
• The second type of mapping is associated mapping.

• In associated mapping each block of main memory is associated

to all blocks of cache memory.

• The above concept is clear from the diagram below.

Associated Mapping
28
Replacement algorithms
Once the cache has been filled, when a new block is 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, and no choice

is possible.

For the associative techniques, a replacement algorithm is needed.

The four most popular replacement algorithms:

 Least Recently used (LRU).

 First in first out (FIFO).

 Least frequently used (LFU).

 Random.
29
1. Least Recently used (LRU)

Replace that block in the set that has been in the cache longest with
no reference to it.

2. First in first out (FIFO)

Replace block that has been in cache longest.

3. Least frequently used (LFU)

Replace block which has had fewest hits.

4. Random

to pick a line at random from among the candidate

lines.

30