3 MAPPING TECHNIQUES

-

 WHAT IS MAPPING?

    We need to bring data from the main memory to the cache for reducing the access time for the CPU as the cache is closer to the CPU than the main memory.

 ASSOCIATIVE MAPPING

    Data from main memory are placed randomly in cache.Let us say we have 16 bit memory address then out of that we have 12 bit tag bits & 4 bit word bits.That is cache will have total 2^12 blocks and each block will have 2^4 data words.if get 1111111111111111 then tag bits is 111111111111 & word bits is 1111,that is we will look for block with tage of 111111111111 and in that block we will search for 16th word block.refer the figure => 


benefits of associative mapping are like 
  1. No thrashing as it happens in direct mapping

 DIRECT MAPPING

    Same like above , if we use 16 bit addressing then tag bits have 5 bits,block bits of 7bits & word bits have 4 bits.Word bit identifies the column number,block bit identifies the row number & tag bits refers the corresponding address in main memory.
    What happens in direct mapping is that if cache has 8 block then block number x is added in (x%8)th block of cache.That is 0th & 8th block in memory is added in 0th block in cache,this can create thrashing that is fighting for space.refer the figure

benefits of direct mapping => 


  1. fast 
  2. cheap

 SET-ASSOCIATIVE MAPPING

    What if we get fast & cheap cache design with no thrashing,is it possible?YES PAL.Like hybridization we will combine the properties of direct mapping and associative mapping and this will result in set-associative mapping.
    Same as above if we use 16bit addressing then tag bit is of 6 bits,set bits is of 6 bits & word bits is of 4 bits.By using set bits we will find the block number and if block number is same it has subparts for preventing thrashing,if space is free then thrashing is preventing and if not then we cant prevent thrasing then we need to use REPLACEMENT ALGORITHM.Then by using word bit we find ith block and so on.
refer the figure => 

Comments

Post a Comment

Popular posts from this blog

LOWEST COMMON ANCESTOR IN BST

-
 PROBLEM => FIND THE LOWEST COMMON ANCESTOR OF TWO NODES (a & b) IN BINARY                                        SEARCH TREE STEPS =>  1.Find whether these two nodes are present in bst.If not found then return NULL. 2.If both nodes are found then there are 4 possibilites =>                    1.root == a || root == b => return root                    2.a is found in left subtree and b is found in right subtree => return NULL from that subtree                                  where we cant find both a & b                    3.if a and b are found in left/right subtree return root node * lca ( node * root , int a , int b ){     if ( root == NULL ) // root is NULL     {         return NULL ;     }     if ( root -> data == a || root -> data == b ) // if found numbers at current node     {         return root ;     }     node * left = lca ( root -> left , a , b ); // find in left subtree     node * right = lca ( root -> right , a ,
Read more

VIRTUAL MEMORY

-
Image
  Basic Idea Of Virtual Memory     Let us say we have a game of 50GB and RAM of 8 GB then by logic we will think that 50GB is greater than 8GB so the game can't fit in RAM so the game cant work. This is not the computers and world work pal...     Of 50GB let us say we require only 2 GB of data of RAM for making a game run and RAM is   8GB, yes we will put those data in RAM that is in use and others in physical memory (disk ) that are not in use right now.     The above process is done by the concept of virtual memory, it will show that it is doing hard work (running  50GB in 8GB space) but actually, it is doing smart work (running 2GB in 8GB).     Take a look at the following diagram =>       1. Processor issues for a virtual address asking for a physical address 2. Memory Management Unit converts the virtual address into a physical address using some internal methods. 3. You get data from that physical address either from cache or from main memory if that is not found in both o
Read more