Cache Memory-


Cache memory is a Random Access Memory.

 The main advantage of cache memory is its very fast speed.

 It can be accessed by the CPU at much faster speed than main

memory.

Location-

 Cache memory lies on the path between the CPU and the main
memory.

 It facilitates the transfer of data between the processor and the

main memory at the speed which matches to the speed of the
processor.
  Data is transferred in the form of words between the cache memory
and the CPU.

 Data is transferred in the form of blocks or pages between the cache

memory and the main memory.

Purpose-

 The fast speed of the cache memory makes it extremely useful.

 It is used for bridging the speed mismatch between the fastest CPU
and the main memory.

 It does not let the CPU performance suffer due to the slower speed
of the main memory.

Execution Of Program-

 Whenever any program has to be executed, it is first loaded in the

main memory.

 The portion of the program that is mostly probably going to be

executed in the near future is kept in the cache memory.

 This allows CPU to access the most probable portion at a faster

speed.

Step-01:
Whenever CPU requires any word of memory, it is first searched in the
CPU registers.

Now, there are two cases possible-

Case-01:

Advertisements

 If the required word is found in the CPU registers, it is read from

there.

Case-02:

 If the required word is not found in the CPU registers, Step-02 is

followed.

Step-02:

 When the required word is not found in the CPU registers, it is

searched in the cache memory.

 Tag directory of the cache memory is used to search whether the

required word is present in the cache memory or not.

Now, there are two cases possible-

Case-01:

 If the required word is found in the cache memory, the word is

delivered to the CPU.

 This is known as Cache hit.

Case-02:

 If the required word is not found in the cache memory, Step-03 is

followed.

 This is known as Cache miss.

Step-03:

 When the required word is not found in the cache memory, it is

searched in the main memory.

 Page Table is used to determine whether the required page is

present in the main memory or not.

Now, there are two cases possible-

Case-01:

If the page containing the required word is found in the main memory,

 The page is mapped from the main memory to the cache memory.

 This mapping is performed using cache mapping techniques.

 Then, the required word is delivered to the CPU.

Case-02:

If the page containing the required word is not found in the main memory,

 A page fault occurs.

 The page containing the required word is mapped from the

secondary memory to the main memory.

 Then, the page is mapped from the main memory to the cache
memory.

 Then, the required word is delivered to the CPU.

Multilevel Cache Organization-

 A multilevel cache organization is an organization where cache

memories of different sizes are organized at multiple levels to
increase the processing speed to a greater extent.

 The smaller the size of cache, the faster its speed.

 The smallest size cache memory is placed closest to the CPU.

 This helps to achieve better performance in terms of speed.

Example-

Three level cache organization consists of three cache memories of

different size organized at three different levels as shown below-

Size (L1 Cache) < Size (L2 Cache) < Size (L3 Cache) < Size (Main
Memory)

Cache memory bridges the speed mismatch between the processor and
the main memory.

hen cache hit occurs,

 The required word is present in the cache memory.

 The required word is delivered to the CPU from the cache memory.
 When cache miss occurs,

 The required word is not present in the cache memory.

 The page containing the required word has to be mapped from the
main memory.

 This mapping is performed using cache mapping techniques.

Cache Mapping-

 Cache mapping defines how a block from the main memory is

mapped to the cache memory in case of a cache miss.

OR

 Cache mapping is a technique by which the contents of main

memory are brought into the cache memory.

The following diagram illustrates the mapping process-

Now, before proceeding further, it is important to note the following

points-

NOTES

 Main memory is divided into equal size partitions called as blocks or frames.
 Cache memory is divided into partitions having same size as that of blocks
called as lines.

 During cache mapping, block of main memory is simply copied to the cache
and the block is not actually brought from the main memory.

Cache Mapping Techniques-

Cache mapping is performed using following three different techniques-

1. Direct Mapping

2. Fully Associative Mapping

3. K-way Set Associative Mapping

1. Direct Mapping-
 In direct mapping,

 A particular block of main memory can map only to a particular line

of the cache.

 The line number of cache to which a particular block can map is

given by-

Cache line number

= ( Main Memory Block Address ) Modulo (Number of lines in Cache)

Example-

 Consider cache memory is divided into ‘n’ number of lines.

 Then, block ‘j’ of main memory can map to line number (j mod n)
only of the cache.

Need of Replacement Algorithm-

In direct mapping,

 There is no need of any replacement algorithm.

 This is because a main memory block can map only to a particular

line of the cache.

 Thus, the new incoming block will always replace the existing block
(if any) in that particular line.

Division of Physical Address-

In direct mapping, the physical address is divided as-

Case : swap the pages Replace pg 2 and 4 and 6
Change the cache size
2. Fully Associative Mapping-

In fully associative mapping,

 A block of main memory can map to any line of the cache that is
freely available at that moment.

 This makes fully associative mapping more flexible than direct

mapping.

Example-

Consider the following scenario-

Here,

 All the lines of cache are freely available.

 Thus, any block of main memory can map to any line of the cache.

 Had all the cache lines been occupied, then one of the existing
blocks will have to be replaced.

Need of Replacement Algorithm-

In fully associative mapping,

 A replacement algorithm is required.

  Replacement algorithm suggests the block to be replaced if all the
cache lines are occupied.

 Thus, replacement algorithm like FCFS Algorithm, LRU Algorithm etc

is employed.

Division of Physical Address-

In fully associative mapping, the physical address is divided as-

3. K-way Set Associative Mapping-

In k-way set associative mapping,

 Cache lines are grouped into sets where each set contains k number
of lines.

 A particular block of main memory can map to only one particular

set of the cache.

 However, within that set, the memory block can map any cache line
that is freely available.

 The set of the cache to which a particular block of the main memory
can map is given by-

Cache set number

= ( Main Memory Block Address ) Modulo (Number of sets in

Cache)
Example-

Consider the following example of 2-way set associative mapping-

Here,

 k = 2 suggests that each set contains two cache lines.

 Since cache contains 6 lines, so number of sets in the cache = 6 / 2

= 3 sets.
  Block ‘j’ of main memory can map to set number (j mod 3) only of
the cache.

 Within that set, block ‘j’ can map to any cache line that is freely
available at that moment.

 If all the cache lines are occupied, then one of the existing blocks
will have to be replaced.

Need of Replacement Algorithm-

 Set associative mapping is a combination of direct mapping and

fully associative mapping.

 It uses fully associative mapping within each set.

 Thus, set associative mapping requires a replacement algorithm.

Division of Physical Address-

In set associative mapping, the physical address is divided as-

Special Cases-

 If k = 1, then k-way set associative mapping becomes direct

mapping i.e.

1-way Set Associative Mapping ≡ Direct Mapping

  If k = Total number of lines in the cache, then k-way set associative
mapping becomes fully associative mapping.

Cache Coherence

Cache Coherence assures the data consistency among the various

memory blocks in the system, i.e. local cache memory of each processor
and the common memory shared by the processors. It confirms that each
copy of a data block among the caches of the processors has a consistent
value.

In this section, we will discuss the cache coherence problem and the
protocol for resolving the cache coherence problem.

Cache Coherence in Computer Architecture

1. Cache Coherence Problem

2. Memory Block States

3. Cache Coherence Protocols

o Write-Through Protocol

o Write-Back Protocol

o Snoopy Protocol

o Directory Protocol

4. Key Takeaways

What is Cache Coherence Problem?

In a multiprocessor environment, all the processors in the system share

the main memory via a bus. Now, keeping a common cache for all the
processors will enhance the size of the cache thereby slowing down the
performance of the system.

For better performance, each processor implements its own cache.

Processors may share the same data block by keeping a copy of this data
block in their cache. The figure below shows how processors P1, P3 & Pn
have the copy of shared data block X of main memory in their caches.
In case, the processor P1 modifies the copy of shared memory block X
present in its cache. It would result in data inconsistency. As the
processor P1 will have the modified copy of the shared memory block
i.e. X1. But, the main memory and other processors’ cache will have
the old copy of the shared memory block X. And this problem is
the cache coherence problem.

The figure below shows the cache coherence problem in a multiprocessing

environment.
Well, this cache coherence problem can be sorted using the protocols
discussed below. But before getting into the protocols we will discuss
some terminologies associated to cache coherence problem.

States of Memory Block in Cache memory

If we talk about the cache memory it is subdivided into a number of

blocks. And whenever a processor requires a data block it first checks it in
its own cache memory. If it is not there the data is retrieved from the main
memory and a copy of it is placed in the cache block.

Now to maintain the cache coherency the cache controller maintain some
information to keep the the caches of other processors in the system
synchronized, while a processor is modifying its copy of data that is also
shared by other processors in the system. So the cache controller
maintains the state for every cache block of the cache memory which
helps in maintaining the coherency.

 Modify (M): The data block in a cache is modified and the

processor modifying the data block is the owner of that data block.
This copy of the data block is not available with any other caches in
the system.
The main memory copy for the same data block does not contain
the modified value of the data block. If the processor wants to
 modify it again, it doesn’t need to broadcast this request over the
bus again.

 Exclusive (E): When the processor wants to modify a data block in

its cache, it broadcast the request to invalidate the copy of the
same data block in other caches.
So, the data block to be modified is now only with the processor
that wishes to modify it and with the main memory. Here, the
processor is the exclusive owner of the data block.

 Shared (S): A data block in the main memory is shared by many

processors in the system and all the processors have a valid copy
of the data block in their caches.

 Invalid (I): The cache has a data block that does not have valid
data. If it wants to read or write/modify this data block it has to
send a request to the owner of the same data block.

Cache Coherence Protocols

1. Write-Through Protocol

In write-through protocol when a processor modifies a data block in its

cache, it immediately updates the main memory with the new copy of
the same data block. So, the main memory here always has consistent
data.
The write-through protocols have two versions and those are:

1. Updating Values in Other Caches

2. Invalidating Values in Other Caches.

Updating Values

Let us understand the first version where the inconsistent copies of

shared data are updated in other caches.

1. Whenever a processor modifies a shared data block in its cache, it

immediately updates the same data block in the main memory.

2. Now other processors with the same data block present in their
cache will have inconsistent data. So the processor that has
modified the shared data block, broadcast the modified data to all
the other processors in the system.

3. When the other processors in the system receive the broadcasted

modified data they verify whether they have the same data block
present in their cache. If yes, the content of that data block is
 modified as specified in broadcasted data else the broadcasted data
is discarded.

Invalidating Values

Now, let us see the second version where the inconsistent copies in
other processors caches are invalidated.

1. Whenever a processor modifies a data block present in its cache

memory, it immediately updates the same data block in the main
memory.

2. The processor modifying the data block broadcast request to other

processors present in the system to invalidate the copies of the
same data block in their caches.

2. Write-Back Protocol

This protocol permits the processor to modify a data block only if it

acquires ownership.

Steps to Acquire Ownership

1. Initially, the memory is the owner of all the data blocks and it
retains that ownership when a processor reads a data block and
sites its copy in its cache.

2. When a processor wants to modify a data block in its cache it has

to confirm that it is an exclusive owner of that data block.

o For this, it has to first invalidate the copies of this data block
in the other caches by broadcasting an invalidating request
to all processors.

o Once it has become the exclusive owner, it can modify the

data block.

3. If any processor wants to read this modified data block it has to

send the request to the current owner processor of that data
block.

4. The owner forwards the data to the requesting processor and to

the main memory.

5. The main memory updates the content of the data block that has
been modified and reacquires its ownership again over the data
block.
If any processor requires this data block it will be serviced by the
main memory.
Modify Data

If another processor in the system wishes to modify/write the data block

that has been modified. It sends a request to the current owner. The
current owner sends the data and control over the block to the
requesting processor.

Now, the requesting processor is the owner. It modifies the data block and
also services the other processor’s request for the data block. Here the
modified data block is not updated in the main memory. Since only
the owner is authorized to modify the data block.

3. Snoopy Protocol

In the multiprocessor environment, all the processors are connected to

memory modules via a single bus. The transaction between the
processors and the memory module i.e. read, write, invalidate request for
the data block occurs via bus.

If we implement the cache controller to every processor’s cache in the

system, it will snoop all the transactions over the bus and perform the
appropriate action. So, we can say that the Snoopy protocol is
the hardware solution to the cache coherence problem.
It is used for small multiprocessor environments as the large shared-
memory multiprocessors are connected via the interconnection network.

Consider a scenario from write-back, if a processor has just modified a

data block in its cache, and is a current owner of the block.

Now, if processor P1 wishes to modify the same data block that has been
modified. P1 would broadcast the invalidation request on the bus and
becomes the owner for that data block and modify the data block. The
other processors who have the copy of the same data block snoop the
bus and invalidate their copy of the data block (I). It updates memory
using the write-back protocol.

4. Directory-Based Cache Coherence Protocol

Directory-Based cache coherence protocol is a hardware solution to the

cache coherence problem. It is implemented in a large multiprocessor
system where the shared memory and processors are connected using
the interconnection network.
The directories are implemented in each memory module of the
multiprocessors system. These directories keep the record of all the
actions taken to each data block i.e. whether a data block in the cache of
a processor is invalid, or is being modified, or is in the shared state. Due
to its cost and complexity directory-based cache coherence protocols
are implemented only to large multiprocessors systems.

Key Takeaways

 Cache coherence promises data consistency among all the

memory blocks in the system (cache memory of various processors
and the main memory).

 Whenever a processor modifies a data block in its cache, the copies

of the same data block in other caches and the memory are not
updated. So, the other caches would have the old copy of the same
data block. This leads to data inconsistency and it’s a cache
coherence problem.

 We have the protocols to maintain the cache coherence in the

system like write-through protocol, write-
back protocol, snoopy protocol, and directory-based protocol.