cache part 1

Cache Memory
By Noor Kadhum

Historical introduction


Sir Maurice Vincent Wilkes
Cache memory owes its introduction to Wilkes back in 1965. At that time, Wilkes distinguished between two types of main memory: The conventional and the slave memory. In Wilkes terminology, a slave memory is a second level of unconventional
high-speed memory, which nowadays corresponds to what is called cache memory (the term cache means a safe place for hiding or storing things).


Principle of : Locality of reference

The idea behind using a cache as the first level of the memory hierarchy is to keep the information expected to be used more frequently by the CPU in the cache (a small high-speed memory that is near the CPU).
The end result is that at any given time some active portion of the main memory is duplicated in the cache. Therefore when the processor makes a request for a memory reference, the request is first sought in the cache. If the request corresponds to an element that is currently residing in the cache, we call that a cache hit. On the other hand, if the request corresponds to an element that is not currently in the cache, we call that a cache miss.





Important Laws:

1) Hit ratio = hit / (hit + miss)

2) access time cache = (hit + miss ) * t cache

3) access time M.M= miss * t M.M

4) Total access time = Access time cache + Access time M.M

5) Average access time :

a- with cache = Total access time / (hit+miss)
b- without cache = t M.M
-----------------------------------------------------------------------------------------
Example:
-----------------------------------------------------------------------------------------
Compute the Average access time for memory system when the time for M.M is 1000 ns, the time for cache is 100 ns and hit ratio is 0.9.

Sol:
Hit ratio = 0.9= 9/10 --> Hit =9 , miss =1
Access time cache = (hit + miss ) * t cache
= 10 * 100ns = 1000 ns

Access time M.M= miss * t M.M
= 1* 1000 ns = 1000 ns

Total access time = Access time cache + Access time M.M
= 1000 + 1000 = 2000 ns
Average access time :

a- with cache = Total access time / (hit+miss)
= 2000 ns / 10 = 200 ns
b- without cache = t M.M
= 1000 ns




Cache-Mapping Function

A request for accessing a memory element is made by the
processor through issuing the address of the requested element. The address issued by the processor may correspond to that of an element that exists currently in the cache (cache hit); otherwise, it may correspond to an element that is currently residing in the main memory.
Therefore, address translation has to be made in order to determine the whereabouts of the requested element. This is one of the functions performed by the memory management unit (MMU). A schematic of the address mapping function is shown in the following Figure:

In this figure, the system address represents the address issued by the processor for the requested element. This address is used by an address translation function inside the MMU. If address translation reveals that the issued address corresponds to an element currently residing in the cache, then the element will be made available to the processor.

If, on the other hand, the element is not currently in the cache, then it will be brought (as part of a block) from the main memory and placed in the cache and the element requested is made available to the processor.


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?

Next Lecture …

Next week we will use the previous laws and notes to solve the following questions:

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.
-----------------------------------------------------------------------------------------
Until that time, try to practice on solving them.
-----------------------------------------------------------------------------------------