UNIT- 2

Memory Hierarchy Technology in Computer Architecture

Introduction:

Storage devices such as registers, cache main memory disk devices and backup
storage are often organized as a hierarchy. The memory technology and
storage organization at each level are characterized by five parameters:

1. Access time
2. Memory size
3. Cost per bit or byte
4. Transfer bandwidth
5. Unit of transfer

There are three important properties for maintaining consistency in the

memory hierarchy these three properties are Inclusion, Coherence, and
Locality.

1
Information stored in a memory hierarchy satisfies all the above properties the
first property i.e the inclusion property, it states as: (M1CM2C...)

Inclusive property:

The set inclusive implies that all the information's are originally stored in the
outermost level Mi and the information word found in Mn then copies of the
same word can also be found in all the upper levels Mi+1, Mi+2.

1. Access by word(4 bytes) from a cache block of 32 bytes, such as block A

2. Access by block (32 bytes) from a memory page of 32 blocks or 1 KB such
as block B from page B.
3. Access by page 1 KB from a file consisting of many pages like A & B in
segment F
4. Segment Transfer with different No. of pages

Coherence Property

The coherence property requires that copies of the same information item at
successive memory level should be consistent. If a word is modified in the
cache copies of that word must be updated immediately at the higher levels.

There are two strategies for maintaining coherence in a memory hierarchy.

The first method is,

1. Write through which demand immediate update through

broadcasting Mi+1 level of memory if a word is modified in Mi.
2. Write back – the second method is written which delays the update
in Mi.

Locality of references

• Temporal Locality - Recently referenced items like instructions or data

are likely to be referred again shortly

Example stacks

• Spatial Locality - This refers to the tendency for a process to access

items whose addresses are nearer to another
• Sequential Locality - In typical programs the execution of instructions
follows a sequential order unless branch instructions create out of order
execution.

2
 Example The ratio of in order execution to out of order execution
is roughly 5:1 in ordinary programs.

Levels of Memory
• Level 1 or Register: It is a type of memory in which data is stored and
accepted that are immediately stored in the CPU. The most commonly used
register is Accumulator, Program counter, Address Register, etc.
• Level 2 or Cache memory: It is the fastest memory that has faster access
time where data is temporarily stored for faster access.
• Level 3 or Main Memory: It is the memory on which the computer works
currently. It is small in size and once power is off data no longer stays in this
memory.
• Level 4 or Secondary Memory: It is external memory that is not as fast as
the main memory but data stays permanently in this memory.

Cache Memory
•

Cache Memory is a special very high-speed memory. The cache is a smaller and
faster memory that stores copies of the data from frequently used main memory
locations.
Characteristics of Cache Memory
• Cache memory is an extremely fast memory type that acts as a buffer
between RAM and the CPU.
• Cache Memory holds frequently requested data and instructions so that
they are immediately available to the CPU when needed.
• Cache memory is costlier than main memory or disk memory but more
economical than CPU registers.
• Cache Memory is used to speed up and synchronize with a high-speed CPU.

Cache Memory

3
Cache Performance
When the processor needs to read or write a location in the main memory, it
first checks for a corresponding entry in the cache.
• If the processor finds that the memory location is in the cache, a Cache
Hit has occurred and data is read from the cache.
• If the processor does not find the memory location in the cache, a cache
miss has occurred. For a cache miss, the cache allocates a new entry and
copies in data from the main memory, then the request is fulfilled from the
contents of the cache.

The performance of cache memory is frequently measured in terms of a

quantity called Hit ratio.

Hit Ratio(H) = hit / (hit + miss)

= no. of hits/total accesses

Miss Ratio = miss / (hit + miss) = no. of miss/total accesses

= 1 - hit ratio(H)

We can improve Cache performance using higher cache block size, and higher
associativity, reduce miss rate, reduce miss penalty, and reduce the time to hit
in the cache.
Cache Mapping
There are three different types of mapping used for the purpose of cache
memory which is as follows:
• Direct Mapping
• Associative Mapping
• Set-Associative Mapping

1. Direct Mapping
The simplest technique, known as direct mapping, maps each block of main
memory into only one possible cache line. or In Direct mapping, assign each
memory block to a specific line in the cache. If a line is previously taken up by
a memory block when a new block needs to be loaded, the old block is trashed.
An address space is split into two parts index field and a tag field. The cache is

4
used to store the tag field whereas the rest is stored in the main memory.
Direct mapping`s performance is directly proportional to the Hit ratio.
i = j modulo m where,
i = cache line number
j = main memory block number
m = number of lines in the cache

Direct Mapping

For purposes of cache access, each main memory address can be viewed as
consisting of three fields. The least significant w bits identify a unique word or
byte within a block of main memory. In most contemporary machines, the
address is at the byte level. The remaining s bits specify one of the 2 s blocks of
main memory. The cache logic interprets these s bits as a tag of s-r bits (the
most significant portion) and a line field of r bits. This latter field identifies one
of the m=2r lines of the cache. Line offset is index bits in the direct mapping.

Direct Mapping – Structure

5
2. Associative Mapping
In this type of mapping, associative memory is used to store the content and
addresses of the memory word. Any block can go into any line of the cache.
This means that the word id bits are used to identify which word in the block
is needed, but the tag becomes all of the remaining bits. This enables the
placement of any word at any place in the cache memory. It is considered to
be the fastest and most flexible mapping form. In associative mapping, the
index bits are zero.

Associative Mapping – Structure

3. Set-Associative Mapping
This form of mapping is an enhanced form of direct mapping where the
drawbacks of direct mapping are removed. Set associative addresses the
problem of possible thrashing in the direct mapping method. It does this by
saying that instead of having exactly one line that a block can map to in the
cache, we will group a few lines together creating a set. Then a block in
memory can map to any one of the lines of a specific set. Set-associative
mapping allows each word that is present in the cache can have two or more
words in the main memory for the same index address. Set associative cache
mapping combines the best of direct and associative cache mapping
techniques. In set associative mapping the index bits are given by the set offset

6
bits. In this case, the cache consists of a number of sets, each of which consists
of a number of lines.

Set-Associative Mapping

Relationships in the Set-Associative Mapping can be defined as:

m=v*k
i= j mod v

where
i = cache set number
j = main memory block number
v = number of sets
m = number of lines in the cache number of sets
k = number of lines in each set

7
 Set-Associative Mapping – Structure

Direct-Mapped Cache:
Advantages:

1. Simple and easy to put into effect

2. Low hardware overhead

3. Fast hit time

Disadvantages:

1. High pass over fee because of restrained wide variety of cache blocks

2. Increased war misses because of block collisions

3. Limited flexibility in phrases of block placement

8
Set-Associative Cache:

Advantages:

1. Higher hit fee than direct-mapped cache because of more than one blocks
being saved in each set

2. More bendy block placement than direct-mapped cache

3. Lower struggle misses as compared to direct-mapped cache

Disadvantages:

1. Higher hardware overhead than direct-mapped cache

2. Longer hit time than direct-mapped cache because of looking multiple

blocks

3. Limited scalability due to fixed quantity of ways in step with set

Fully-Associative Cache:

Advantages:

1. Highest hit rate amongst cache businesses

2. Most flexible block placement

3. No struggle misses because of fully-associative mapping

Disadvantages:

1. Highest hardware overhead among cache agencies

2. Longest hit time due to searching all blocks in cache

3. Limited scalability because of constrained physical area and huge tag

storage necessities

9
What a Cache Miss Is

A cache miss is when the data that is being requested by a system or an

application isn’t found in the cache memory. This is in contrast to a cache hit,
which refers to when the site content is successfully retrieved and loaded from
the cache.

In other words, a cache miss is a failure in an attempt to access and retrieve

requested data. There are multiple reasons why this might happen.

One is that the data was never put into the cache, to begin with. Another
possibility is that the data was removed at one point. This data eviction could
have been caused by the caching system, such as if more space was needed, or
a third-party application that requested it is removed. It’s also possible that
the TTL (Time to Live) policy on the data expired.

What Happens During a Cache Miss

When a cache miss occurs, the system or application will try a second time to
find the data. However, when it’s not able to locate it in the cache memory on
the first attempt, the next step is to check the main database.

If the data is found, it’s usually copied and saved to the cache with the
assumption that there will be another request for it in the future. Checking the
main database for the data takes more time, which leads to latency.

In other words, it can hamper the speed and performance of your site. The
more cache misses that occur, the longer the latency. As we mentioned earlier,
when the system is searching for relevant data, it passes through each of the
cache levels (L1, L2, L3, and so on).

Each time this happens, it causes a delay, also known as a miss penalty. This is
why it’s critical to know how to keep cache misses as low as possible.

How to Reduce Cache Misses (3 Key Tips)

1. Increase the Size of Random Access Memory (RAM)

Another option for reducing cache misses is to increase the size of your RAM.
Obviously, the larger your cache, the more data it can hold and, thus, the
fewer cache misses you’re likely to deal with.

10
 2. Use the Optimal Cache Policies for Your Specific Circumstances

third way to reduce cache misses is by testing out different cache.

The four main cache policies are:

1. First In First Out (FIFO): This policy means that the data that was added
the earliest to the cache will be the first to be evicted.
2. Last In First Out (LIFO): This means that the data entries added last to
the cache will be the first to be removed.
3. Least Recently Used (LRU): True to its name, this policy first evicts the
data accessed the longest time ago.
4. Most Recently Used (MRU): With this policy, the data most recently
accessed is evicted first.

3. Set an Expiry Date for the Cache Lifespan

Every time your cache is purged, the data in it needs to be written into the
memory after the first request. The more you purge your cache, the more
likely cache misses are to occur. Of course, sometimes clearing your cache is
necessary.

However, one way you can prevent this problem is to expand the lifespan of
your cache by increasing its expiry time. Keep in mind that the expiry time
should coincide with how often you update your website to ensure that the
changes appear to your users.

For example, if you don’t frequently update your site, you can probably set the
expiry time to two weeks. Alternatively, if site updates are a weekly
occurrence, your expiry time shouldn’t exceed a day or two.

virtual memory

• What is virtual memory?

Virtual memory is a memory management technique where secondary
memory can be used as if it were a part of the main memory. Virtual memory
is a common technique used in a computer's operating system (OS).

Virtual memory uses both hardware and software to enable a computer to

compensate for physical memory shortages, temporarily transferring data

11
from random access memory (RAM) to disk storage. Mapping chunks of
memory to disk files enables a computer to treat secondary memory as though
it were main memory.

Today, most personal computers (PCs) come with at least 8 GB (gigabytes) of

RAM. But, sometimes, this is not enough to run several programs at one time.
This is where virtual memory comes in. Virtual memory frees up RAM by
swapping data that has not been used recently over to a storage device, such
as a hard drive or solid-state drive (SSD).

Virtual memory is important for improving system performance, multitasking

and using large programs. However, users should not overly rely on virtual
memory, since it is considerably slower than RAM. If the OS has to swap data
between virtual memory and RAM too often, the computer will begin to slow
down -- this is called thrashing.

Virtual memory was developed at a time when physical memory -- also

referenced as RAM -- was expensive. Computers have a finite amount of RAM,
so memory will eventually run out when multiple programs run at the same
time. A system using virtual memory uses a section of the hard drive to
emulate RAM.

• How virtual memory works

Virtual memory uses both hardware and software to operate. When an
application is in use, data from that program is stored in a physical address
using RAM. A memory management unit (MMU) maps the address to RAM and
automatically translates addresses. The MMU can, for example, map a logical
address space to a corresponding physical address.

If, at any point, the RAM space is needed for something more urgent, data can
be swapped out of RAM and into virtual memory. The computer's memory
manager is in charge of keeping track of the shifts between physical and virtual
memory. If that data is needed again, the computer's MMU will use a context
switch to resume execution.

12
 • What are the benefits of using virtual memory?
The advantages to using virtual memory include:

• It enables more applications to be used at once.

• It has increased speed when only a segment of a program is needed for
execution.
• It has increased security because of memory isolation.
• It enables multiple larger applications to run simultaneously.
• Allocating memory is relatively inexpensive.
• It does not need external fragmentation.
• Data can be moved automatically.
• Pages in the original process can be shared during a fork system call
operation that creates a copy of itself.

• What are the limitations of using virtual memory?

Although the use of virtual memory has its benefits, it also comes with some
trade-offs worth considering, such as:

• Applications run slower if they are running from virtual memory.

• Data must be mapped between virtual and physical memory, which
requires extra hardware support for address translations, slowing down a
computer further.
• The size of virtual storage is limited by the amount of secondary storage, as
well as the addressing scheme with the computer system.
• It may take time to switch between applications using virtual memory.
• It lessens the amount of available hard drive space.

13
 • Virtual memory (virtual RAM) vs. physical memory (RAM)
When talking about the differences between virtual and physical memory, the
biggest distinction commonly made is to speed. RAM is considerably faster
than virtual memory. RAM, however, tends to be more expensive.

When a computer requires storage, RAM is the first used. Virtual memory,
which is slower, is used only when the RAM is filled.

Q: What is a page fault and demand paging?

Answer:
A page fault occurs when a program references a virtual memory page that is
not currently resident in physical memory. This happens when the required
page has been paged out to disk or has not been accessed yet. When a page
fault occurs, the operating system handles it by fetching the required page from
disk and updating the page tables to reflect the new mapping.

Demand Paging
The process of loading the page into memory on demand (whenever a page
fault occurs) is known as demand paging. The process includes the following
steps are as follows:
1. If the CPU tries to refer to a page that is currently not available in the main
memory, it generates an interrupt indicating a memory access fault that is
called page fault.
2. The OS puts the interrupted process in a blocking state. For the execution
to proceed the OS must bring the required page into the memory.
3. The OS will search for the required page in the logical address space.
4. The required page will be brought from logical address space to physical
address space. The page replacement algorithms are used for the decision-
making of replacing the page in physical address space.
5. The page table will be updated accordingly.
6. The signal will be sent to the CPU to continue the program execution and
it will place the process back into the ready state.

14