Cache Mapping Techniques Tutorial based gate study material for computer science

Mapping Techniques used for Cache Memory, mapping techniques in cache memory, mapping techniques in cache memory ppt, mapping techniques in cache memory pdf , advantages of mapping techniques in cache memory, different mapping techniques in cache memory,different types of mapping techniques in cache memory, associative cache memory definition, associative cache memory with example,associative mapping in cache memory ppt, associative mapping in cache implementation,fully associative cache mapping techniques with example, two way set associative mapping with example,direct mapping in cache with example,



Mapping Techniques in Cache Memory

Today in this cache mapping techniques tutorial for Gate  we will learn about different type of address mapping techniques in the cache memory these techniques are used to fetch the information from main memory to cache memory.  There are three type of memory mapping techniques. Let us see them one by one

Three types of mapping procedures used for cache memory

(i) Associative mapping
(ii) Direct mapping
(iii) Set-associative mapping

(i) Associative mapping

The fastest and most flexible cache organization uses an associative memory. The organization is illustrated. The associative memory stores both the address and content (data) of the memory word. This permits any location in cache to store any word from main memory. The diagram shows three words presently stored in the cache. The address value of 15 bits is shown as a five-digit octal number and its
corresponding 12-bit word is shown as a four-digit octal number and its corresponding 12-bit word is shown as a four-digit octal number. A CPU address of 15 bits is placed in the argument register and the associative memory is searched for a matching address. If the address is found, the corresponding 12-bit data is read and sent to the CPU. If no match occurs, the main memory is accessed for the word. The address-data pair is then transferred to the associative cache memory. 




















direct mapping










Computer Science Study Material for Gate


If the cache is full, an address-data pair must be displaced to make room for a pair that is needed and not presently in the cache. The decision as to what pair is replaced is determined from the replacement algorithm that the designer chooses for the cache. A simple procedure is to replace cells of the cache is round-robin order whenever a new word is requested from main memory. This constitutes a first-in first-out (FIFO) replacement policy.

(ii) Direct Mapping 

Associative memories are expensive compared to random-access memories because of the added logic associated with each cell. The possibility of using a random access memory for the cache is investigated. The CPU address of 15 bits is divided into two fields. The nine least significant bits constitute the index field and the remaining six bits form the tag field. The figure shows that main memory needs an address that includes both the tag and the index bits.

 The number of bits in the index field is equal to the number of address bits required to access the cache memory. In the general case, there are 2k words in cache memory and 2n words in main memory. The n bit memory address is divided into two fields: k bits for the index field and the n-k bits for the tag field. The direct mapping cache organization uses the n-k bits for the tag field.

 In this direct mapped cache tutorial it is also explained the direct mapping cache organization uses the bit address to access the main memory and the k-bit index to access the cache. The internal organization of the words in the cache memory is as shown. Each word in cache consists of the data word and its associated tag. When a new word is first brought into the cache, the tag bits are stored alongside the data bits. When the CPU generates a memory request, the index field is used for the address to access that cache. The tag field of the CPU address is compared with the tag in the word read from the cache. If the two tags match, there is a hit and the desired data word is in
cache.

 If there is no match, there is a miss and the required word is read from main memory. It is then stored in the cache together with the new tag, replacing the previous value. The disadvantage of direct mapping is that the hit ratio can drop considerably if two or more words whose addresses have the same index but different tags are accessed repeatedly. However, this possibility is minimized by the fact that such words are relatively far apart in the address range.



mapping technique based gate study material for computer science


To see how the direct-mapping organization operates, consider the numerical example hown. The word at address zero is presently stored in the cache (index = 000, tag = 00, data = 1220). Suppose that the CPU now wants to access the word at address 02000. The index address is 000, so it is used to access the cache. The two tags are then 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 direct-mapping example just described uses a block size of one word. The same organization but using a block size of 8 words is shown.




address mapping in cache based Study Material for  gate Computer Science

The index field is now divided into two parts: the block field and the word field. In a 512-word cache there are 64 blocks of 8 words cache, since 64 x 8 = 512. The block number is specified with a 6-bit field and the word within the block is specified with a 3-bit field. The tag field stored within the cache is common to all eight
words of the same block. Every time a miss occurs, an entire block of eight words
must be transferred from main memory to cache memory. Although this takes extra
time, the hit ratio will most likely improve with a larger block size because of the
sequential nature of computer programs

(iii) Set-Associative Mapping 

It was mentioned previously that the disadvantage of direct mapping is that two words with the same index in their address but with different tag values cannot reside in cache memory at the same time. A third type of cache organization, called set associative mapping, is an improvement over the direct-mapping organization in that each word of cache can stored two or more words of memory under the same index address. Each data word is stored together with its tag and the number of tagdata items in one word of cache is said to form a set.


 An example of a set associative cache organization for a set size of two is shown. Each index address
refers to two data words and their associated tags. Each tag requires six bits and each data words has 12 bits, so the word length is 2(6+12) = 36 bits. An index address of nine bits can accommodate 512 words. Thus the size of cache memory is 512 x 36. It can accommodate 1024 words of main memory since each word of cache contains two data words. In general, a set-associative cache of set size k will accommodate k words of main memory in each word of cache.






The octal numbers listed are with reference to the main memory contents illustrated in the fig. The words stored at addresses 01000 and 02000 of main memory are stored in cache memory at index address 000. Similarly, the words at addresses 02777 and 00777 are stored in cache at index address 777



When the CPU generates a memory request, the index value of the address is used to access the cache. The tag field of the CPU address is then compared with both tags in the cache to determine if a match occurs. The comparison logic is done by an associative search of the tags in the set similar to an associative memory search: thus the name "set-associative."

The hit ratio will improve as the set size increases because more words with the same index but different tags can reside in cache. However, an increase in the set size increases the number of bits in words of cache and requires more complex comparison logic. 



When a miss occurs in a set-associative cache and the set if full, it is necessary to replace one of the tag-data items with a new value. The most common replacement algorithms used are: random replacement, first-in, first-out (FIFO), and least recently used (LRU). With the random replacement policy the control chooses one tag-data item for replacement at random. The FIFO procedure selects for replacement the item that has been in the set the longest. The LRU algorithm selects for replacement the item that has been least recently used by the CPU. Both FIFO and LRU can be implemented by adding a few extra bits in each word of cache.


ache memory is costly in term of cost per bit.



I hope this Computer Science Study Material for Gate will be beneficial for gate aspirants.




COMMENTS

Name

advance-java,2,advancejava,1,aktu entrance exam,1,aktu exam schedule,1,ASP,1,bare machine,1,base register and limit register,1,Basic Computer network questions,1,C Programming,15,C Plus Plus,1,C Programming,2,C Programming MCQ,2,C Programming Questions,2,C programming study material for gate exam,13,CBNST Program,1,Childcare,1,CJ,2,Cloud Computing,1,components of use case diagram,1,Computer architecture based questions for gate exam,11,Computer Network,3,Computer Network Study Material,4,Computer network study material for gate,2,Computer Networks,7,Computer Science Study Material for Gate,20,computer science study material for gate exam,37,content based image retrieval content based image retrieval system,1,contiguous memory allocation,2,Core Java,8,COre Java Interview Questions,1,core java interviews questions,1,cyber crime report,1,Cyber crime status,1,cybercrime and security,1,cybercrime examples,1,Data link Layer Questions,1,Data Mining,1,Data Structure Questions,1,Data Transmission Architecture,1,Data Transmission in wsn,1,DBMS,4,dbms question paper,1,DE,1,Different types of addressing modes,1,Digital Electronics,1,DS,1,dynamic linking,1,dynamic linking in memory management,1,Electroencephalogram,1,file concept in os,1,File Handling,1,file management in operating system,1,FOC,1,Fundamenatl of Computer,1,Gate 2017,5,Gate 2017 Admit card,1,Gate 2017 Exam Schedule,1,Gate 2017 Syllabus,1,gate 2018,1,gate cse study material,1,gate practice set,10,gate study material for computer science,19,Gate study material for computer science 2017,1,GatePreviousYear,1,General,3,HCL Aptitude Test,1,HR Interview Questions,1,HTML,1,Image Processing,1,Important Date of Gate 2017 Exam,1,Information Security Policy,1,internal and external fragmentation,1,JS,1,lagrange's interpolation formula,1,lagrange's interpolation formula examples,1,Looping in C,1,MComputing,1,memory fragmentation,1,memory management,1,Motivational,4,NCER,2,Numerical Techniques Lab,1,OOT,1,Operating System,8,Operating System Objective Questions,4,Operating System Questions Bank,1,Operating system questions for gate,1,Operating System Study material,2,operating system study material for gate exam,17,Operating system tutorial,3,ORACLE,1,page swapping,1,paged memory allocation,1,paged memory allocation in operating system,1,paging technique of memory management .paging technique,1,paging technique of memory management program in c,1,Pointer in C,5,Process based question for gate,1,Quiz on non conventional energy resources,1,Regression testing,1,relocation in memory management,1,relocation registe,1,relocation register,1,resident monitor,1,resident monitor in operating system,1,routing table,1,segmentation in memory management,1,segmentation in memory management in operating system,1,Servlet,1,session tracking,1,session tracking in java,1,session tracking in servlet,1,Software Engineering,7,Software Engineering baes study material for gate,1,software engineering interview questions,1,Software Quality Assurance,3,SPM,1,SQL,1,Structure in C,1,Study Material for gate Computer Science,11,swapping in memory management,1,swapping in operating system,1,TCS Code Vita,1,Technical Questions from DBMS,1,Threads concept in operating system,1,Tips to Learn Coding,1,Top 30 Core Java Interview Questions with Answer,2,top down approach,1,top down approach in programming,1,Types of operating system,1,UML,1,use case diagram explanation,1,website uses cookies,1,what is cookies website,1,What is process control block ?,1,Wireless Sensor Network,4,worst fit algorithm for memory allocation,1,XML,1,
ltr
item
Computer Science Junction: Cache Mapping Techniques Tutorial based gate study material for computer science
Cache Mapping Techniques Tutorial based gate study material for computer science
Mapping Techniques used for Cache Memory, mapping techniques in cache memory, mapping techniques in cache memory ppt, mapping techniques in cache memory pdf , advantages of mapping techniques in cache memory, different mapping techniques in cache memory,different types of mapping techniques in cache memory, associative cache memory definition, associative cache memory with example,associative mapping in cache memory ppt, associative mapping in cache implementation,fully associative cache mapping techniques with example, two way set associative mapping with example,direct mapping in cache with example,
https://3.bp.blogspot.com/-UWyKsB78n3I/WwFlLDjSBkI/AAAAAAAAAus/F8WrgvasEZk64_G90JOtir02FTngVI3gACLcBGAs/s1600/cache%2Bmapping%2Btechniques.png
https://3.bp.blogspot.com/-UWyKsB78n3I/WwFlLDjSBkI/AAAAAAAAAus/F8WrgvasEZk64_G90JOtir02FTngVI3gACLcBGAs/s72-c/cache%2Bmapping%2Btechniques.png
Computer Science Junction
https://www.computersciencejunction.in/2018/04/types-of-cache-mapping-techniques.html
https://www.computersciencejunction.in/
https://www.computersciencejunction.in/
https://www.computersciencejunction.in/2018/04/types-of-cache-mapping-techniques.html
true
425357657003182083
UTF-8
Loaded All Posts Not found any posts VIEW ALL Readmore Reply Cancel reply Delete By Home PAGES POSTS View All RECOMMENDED FOR YOU LABEL ARCHIVE SEARCH ALL POSTS Not found any post match with your request Back Home Sunday Monday Tuesday Wednesday Thursday Friday Saturday Sun Mon Tue Wed Thu Fri Sat January February March April May June July August September October November December Jan Feb Mar Apr May Jun Jul Aug Sep Oct Nov Dec just now 1 minute ago $$1$$ minutes ago 1 hour ago $$1$$ hours ago Yesterday $$1$$ days ago $$1$$ weeks ago more than 5 weeks ago Followers Follow THIS PREMIUM CONTENT IS LOCKED STEP 1: Share. STEP 2: Click the link you shared to unlock Copy All Code Select All Code All codes were copied to your clipboard Can not copy the codes / texts, please press [CTRL]+[C] (or CMD+C with Mac) to copy