Direct Mapping: Direct mapping is used for random access memory since associative memories are not economical and added associative logic with each cell. The following figures demonstrates the direct mapping.
The CPU address of 15-bits is divided into two fields. The nine least significant bits forms the index field and the remaining six bits form the Tag field. From the above figure, main memory requires and address that includes both the tag and the index bits. The number of bits in the field is equal to the number of address bits required to access the cache memory.
Generally these are 2K words in cache memory and 2n words in main memory. The n-bit memory address is divided into index and tag field. K-bit for index field and (n-k) bits for tag field. The cache with direct mapping uses n-bits address to access main memory organization of the words and cache consists of the data word and it’s associated tag only when a new word is first brought into the cache, the tag bits are stored alongside the data bits.
When CPU generates a memory request, the index field is used for the address to access the cache. The tag field of the CPU address is compared with the word read from the cache. If the two tags match, ahit is produced and the required data word is in cache. If there is no match, there is a miss and the desired data word is read from the main memory.
It is then stored in the cache together with new tag replaced by the previous value. The disadvantage of direct mapping is the hit ratio drop if two or more words whose addresses have the same index but different tags are accessed repeatedly. However this can be minimized by the fast technique, such that words are relatively for a part in the address range 512 location are here in this example.
Consider a numerical example to know how the direct mapping operates. The word 1220 is stored at address 00 000 in the main memory, and the same address is stored in the cache as index = 000, tag=00, data = 1220. If CPU wants to access the word stored at address 02000(word =5670). The index address is 000, so it is used to access the cache. The two tags are compared. The cache tag is 00 but the address tag is 02, which does not produce a match. Therefore the main memory is accessed and the data word 5670 is transferred to the CPU. The cache word at index address 000 is then replaced with a tag of 02 and data of 5670.
The above figure shows Direct Mapping Cache organization
The direct –Mapping is expressed as i=j modulo m
Where, i= Cache line number, j=Main memory block number, n=Number of lines of Cache memory.
Set Associative Mapping : The main draw back of direct mapping is two words with same index address but different values cannot reside in cache memory at the same time.
Therefore an improved cache organization implemented called as set associative mapping. And is used to store two or more words of memory under the same index address. Each data word is stored together with its tag and the number of tag-data pairs in one word of cache is called a set.
For example, consider a set associative cache organization for a set size of two as shown in figure, Each tag requires six bits and each data word has 12 bits, therefore word length becomes 2(6+12) = 36 bits. An index address of a bits can accomadate 1024 words of main memory since each word of cache contains two data word.
In general, a set-associative cache of set size k will accomadate k words main memory.
The octal numbers listed in figure are with reference to the main memory contents. The words stored at addresses 01000 and 02000 of main memory are stored in cache memory at index address 000. Similarly, the words stored at addresses 02777 and 00777 are stored in at index address 777 of cache memory.
As the CPU generates a memory request, the index address is used to access the cache. The tag field of the CPU address is then compared with both tags of the cache to see if a match occurs. The comparison is done by an associative search of the tags in the set similar to an associative memory search. Thus the name “Set associative”.
At the set size increases, bit ration also increases because more words, with same index address but different tags can be stored in cache. However as set size increases and requires complex comparision logic.
The relationship are m = v * k
i = j MODULO V
Where i = Cache Set number
j = main memory block number
m = number of lines in the cache.