Home » Computer Science Organization

Computer Science Organization | Cache Memory

In this article, we will learn about Cache memory, Cache coherence and page replacement algorithm (replacement policy) of cache memory in computer system organization.
Submitted by Abhishek Kataria, on July 18, 2018

Cache Memory

• Cache memory is a fast memory which is smaller in size, it is used as the intermediate memory between the CPU and Main Memory which objective is to support CPU access with a minimum delay.
• CPU performs the read and write operation on a cache memory as the functioning of the cache memory is hidden from both user and system programs.
• A system with a cache memory delivers high performance and offers high throughput.
• Generally, cache consists of cache data memory and tag. Memory words are stored in a cache data memory and then these words are grouped into a block. Basic data transfer unit between main memory and cache is a block of words.

Each cache block is then marked up with the block address which is referred as a tag. In this case, tag indicates the part of the memory space from which the block belongs.

Each cache block is then marked up with the block address which is referred as a tag. In this case, the tag indicates the part of the memory space from which the block belongs.

Cache Coherence

As it’s known, the cache has improved the performance of a system. However, there is a creation of a problem known as a coherence problem. In a single CPU system, two copies of the same data, one in the cache memory and another one in main memory may become different. Therefore by this content of cache and main memory can be altered by more than one device, by which it can result in inconsistencies in the value of cache and main memory.

Techniques for cache coherence

1. Write through: In this technique write the data in the cache and in main memory, which will always keep the two copies of data consistent.
2. Write block: In this method, updates are made in the cache, by setting a bit called update bit. Only those blocks whose updates bit is set is replaced in the main memory.
3. Instruction cache: This is a technique, which is employed for accessing only the instruction and nothing else. As we know, the instruction does not change, as there will not be any inconsistency.

Cache coherence strategies

Cache strategies have been divided into two categories:

1. Software solution: In software solution the problem of cache coherence is managed entirely by the compiler and operating system. By this, there is no need of circuitry for managing the cache coherence scheme.
2. Hardware solution: These are referred to as cache coherence protocols. By this protocol, inconsistency can be handled during runtime, which leads to a more effective utilization of a cache and improved performance.

Replacement algorithm of cache memory

When the cache is full, there is a need for replacement algorithm for replacing the cache block with a new block. For achieving the high-speed such types of the algorithm is implemented in hardware. In the cache memory, there are three types of replacement algorithm are used that are:

1. Random replacement policy.
2. First in first Out (FIFO) replacement policy
3. Least recently used (LCU) replacement policy.

1) Random replacement policy

This is a very simple algorithm which used to choose the block to be overwritten at random. In this algorithm replace any cache line by using random selection. It is an algorithm which is simple and has been found to be very effective in practice.

2) First in first out (FIFO)

In this algorithm replace the cache block which is having the longest time stamp. While using this technique there is no need of updating when a hit occurs but when there is a miss occur then the block is put into an empty block and the counter values are incremented by one.

3) Least recently used (LRU)

In the LRU, replace the cache block which is having the less reference with the longest time stamp. In this case also when a hit occurs when the counter value will be set to 0 but when the miss occurs there will be arising of two possibilities in which one possibility is that counter value is set as 0 and in another possibility, the counter value can be incremented as 1.