Problems of cache design!

Problems of cache design!
It should be clear that as more requests for items that do not exist in the cache (cache miss) occur, more blocks would have to be brought to the cache. This should raise (يثير) two basic questions:
first : Where to place an incoming main memory block in the cache?
Second: In the case where the cache is totally filled, which cache block should the incoming main memory block replace?
In other words, the designer faces two problems must be taken into consideration:
Placement of incoming blocks and Replacement of existing blocks are performed according.

There are solutions (algorithms) to each problem. The rest of this lecture was dedicated to highlight the Placement problem and its solutions.

Placement Algorithms

A)Direct Mapping (many-to-one mapping technique)
B) Fully Associative Mapping
C) Set-Associative Mapping
-----------------------------------------------------------------------------------------
A)Direct Mapping (many-to-one mapping technique)
-----------------------------------------------------------------------------------------
The main advantage of this method is: it is the simplest among the three techniques because it places an incoming main memory block into a specific fixed cache block location. The placement is done based on a fixed relation between the incoming block number, i, the cache block number, j, and the number of cache blocks, N:
j = i mod N

Its main disadvantage is the inefficient use of the cache. This is because according to this technique, a number of main memory blocks may compete for a given cache block even if there exist other empty cache blocks. This disadvantage should lead to achieving a low cache hit ratio.

According to the direct-mapping technique the MMU interprets the address issued by the processor by dividing the address into three fields as shown below :


-----------------------------------------------------------------------------------------
B) Fully Associative Mapping
-----------------------------------------------------------------------------------------
According to this technique, an incoming main memory block can be placed in any available cache block. Therefore, the address issued by the processor need only have two fields. These are the Tag and Word fields. The first uniquely identifies the block while residing in the cache. The second field identifies the element within the block that is requested by the processor:



The main advantage is:
The efficient use of the cache because there is no restriction on where to place incoming main memory blocks. Any unoccupied cache block can potentially be used to receive those incoming main memory blocks.

The main disadvantage :
The hardware overhead required to perform the associative search conducted in order to find a match between the tag field and the tag memory as discussed above.

-----------------------------------------------------------------------------------------
C) Set-Associative Mapping
-----------------------------------------------------------------------------------------
In the set-associative mapping technique, the cache is divided into a number of sets. Each set consists of a number of blocks. A given main memory block maps to a specific cache set based on the equation:
s = i mod S
where S is the number of sets in the cache, i is the main memory block number, and s is the specific cache set to which block i maps.

However, an incoming block maps to any block in the assigned cache set. Therefore, the address issued by the processor is divided into three distinct fields:



DISADVANTGE: The set-associative-mapping technique produces a moderate cache utilization efficiency, that is, not as efficient as the fully associative technique and not as poor as the direct technique.

ADVANTAGE :the technique inherits the simplicity of the direct mapping technique in terms of determining the target set.
-----------------------------------------------------------------------------------------
SUMMARY:
-----------------------------------------------------------------------------------------

How to determine the no. of bits in each field ?

A) Word field : its constant in the three methods. This field depends on no. of words in the block. Convert this no. to the formula 2k and take k as the no. of bits in the word field.

B) Block field : it depends on no. of blocks in the block. Convert this no. to the formula 2k and take k as the no. of bits in the block field. But, how could we calculate the No. of blocks?

No. of blocks= size of cache(in word unit) / no. of words in block

C) Set field : it depends on no. of sets in the cache. Convert this no. to the formula 2k and take k as the no. of bits in the set field. But, how could we calculate the No. of sets in the cache?

No. of sets= no. of blocks in cache / no. of blocks in set
D) Tag field: it is calculated by the following equation:

Tag bits=no. of bits in M.M address - sum of other fields

Notes:
1- Memory (M.M and cache) size must be measured in word so you should take notice if the size of the memories measured in bytes, it must be turned into a word unit by dividing by 2.

2- Tag field is the last field is calculated, why?