معمارية : المحاضرة الخامسة - مشاكل تصميم الكاش

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.

Replacement Techniques
We discuss three algorithms that are used to deal with miss case when the cache is full:-
-----------------------------------------------------------------------------------------
A) Random Selection
-----------------------------------------------------------------------------------------
It is done based on the output of the random number generator at the time of replacement. The generator produce a number between 0 and (N - 1) where N is no. of blocks in cache. This technique is simple and does not require much additional overhead. However, its main shortcoming is that it does not take locality into consideration. Random techniques have been found effective enough such that they have been first used by Intel in its iAPX microprocessor series.




-----------------------------------------------------------------------------------------
B) The FIFO technique
-----------------------------------------------------------------------------------------
It takes the time spent by a block in the cache as a measure for replacement. The block that has been in the cache the longest is selected for replacement regardless of the recent pattern of access to the block. This technique requires keeping track of the lifetime of a cache block. Therefore, it is not as simple as the random selection technique. The FIFO technique is reasonable to use for straightline programs where locality of reference is not of concern.
-------------------------------------------------------------------------------------------------------
C) LRU (least recently used) technique:
-------------------------------------------------------------------------------------------------------
In this method, the cache block that has been recently used the least is selected for replacement. Among the three replacement techniques, the LRU technique is the most effective. This is because the history of block usage (as the criterion for replacement) is taken into consideration.
The LRU algorithm requires the use of a cache controller circuit that keeps track of references to all blocks while residing in the cache. This can be achieved through a number of possible implementations. Among these implementations is the use of counters:
In this case each cache block is assigned a counter. Upon a cache hit, the counter of the corresponding block is set to 0, all other counters having a smaller value than the original value in the counter of the hit block are incremented by 1, and all counters having a larger value are kept unchanged. Upon a cache miss, the block whose counter is showing the maximum value is chosen for replacement, the counter is set to 0, and all other counters are incremented by 1.






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?

Examples …


A) Using all placement techniques to determine the no. of bits in each field in the address depending on the following information:
Size of M.M= 64 KW.
Size of Cache= 2 KW.
Size of block = 16 W.
Size of set = 2 block.

B) Draw the address format with pointing the number of bits for each field using the all placement algorithms. Suppose that:
Size of M.M= 1 MB.
Size of Cache= 4 KB.
The block contains 2W.
There are 4 blocks in each set.