IRJET- Implementation of Mesi Protocol using Verilog

15 pages
0 views
of 15

Please download to get full document.

View again

All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Share
Description
International Research Journal of Engineering and Technology (IRJET) Volume: 06 Issue: 06 | June 2019www.irjet.nete-ISSN: 2395-0056 p-ISSN: 2395-0072IMPLEMENTATION…
Transcript
International Research Journal of Engineering and Technology (IRJET) Volume: 06 Issue: 06 | June 2019www.irjet.nete-ISSN: 2395-0056 p-ISSN: 2395-0072IMPLEMENTATION OF MESI PROTOCOL USING VERILOG Attada Sravanthi1, Ch. Rajasekhara Rao2, K. Krishnam Raju3, L. Rambabu4 1PGScholar, Aditya Institute of Technology and Management, Tekkali, 532201, India Aditya Institute of Technology and Management, Tekkali, 532201, India --------------------------------------------------------------------------***---------------------------------------------------------------------------2,3,4Associate,Abstract:- Multiprocessor system has two or more processors working simultaneously and sharing the same memory. Nowadays multiprocessors are being widely used due to their high throughput and reliability. It is important to maintain data consistency in multi-processor systems as different processors may communicate and share the data with each other. In multiprocessor systems caching plays a vital role. Cache coherence is a major issue in multiprocessor systems. In the present paper, three direct- mapped caches are designed and to maintain the cache coherence and data consistency among the processors, MESI protocol is used. The MESI protocol is the invalidation based cache coherence protocol. In this protocol each cache block can be in one of four states i.e., Modified, Exclusive, Shared and Invalid. In this protocol, whenever a processor writes into the local cache, all copies of it in other processors are invalidated in order to maintain data consistency and cache coherence. The cache design is simulated and syn papered using Xilinx ISE 14.7 Simulator and XST Synthesizer . Keywords: MESI Introduction In recent years multiprocessors are gaining more importance as they have better performance and reliability than single processor systems. Multiprocessors with shared memory are being used in the today’s computers and researches [1]. Using the single address space the processors can communicate among themselves because address space is shared among the processors in multiprocessor systems. So, same cache entry exists in other processors as the address is being shared. The shared memory multiprocessor system architecture is shown in the figure1.1.Figure 1.1: Shared memory multiprocessor system Sharing of data among the processors is not a problem during reading operation but it is a serious problem during write operation. When one processor writes a value to a location that is being shared, the changed value has to be updated to all caches; otherwise the processors hold different data for the same location which is called as cache coherence problem [2]. Evolution of cache coherence protocols MI Protocol It is the basic conventional protocol used for maintaining cache coherence in shared memory multi-processor systems. Each cache block can be in any one of the two states i.e., modified, invalid.Š 2019, IRJET|Impact Factor value: 7.211|ISO 9001:2008 Certified Journal|Page 1763International Research Journal of Engineering and Technology (IRJET) Volume: 06 Issue: 06 | June 2019www.irjet.nete-ISSN: 2395-0056 p-ISSN: 2395-0072Modified: Modified means the data present in the cache line is different from the data present in the main memory. If the cache block is in modified state then it can perform read and write operation. Whenever a write operation is performed only one block can be in modified state and the rest should be in invalid state. Invalid: No reading and writing operations can be performed if the cache block is in invalid state. The cache block is said to be in invalid state if the required location is not present in the cache. Advantages of MI Protocol 1) Implementation of the protocol is easier. 2) Number of transient states are less. Disadvantage of MI Protocol 1) There is no difference between shared and modified block. MSI Protocol It is the extension to MI Protocol. Each cache block can be in any one of the three states i.e., modified, shared, invalid [4]. a)Modified: Modified means the data present in the cache line is different from the data present in the main memory. If the cache block is in modified state then it can perform read and write operation.b) Shared: The data present in the cache is similar to the data present in the main memory. The same location may be present in other caches also. c)Invalid: No reading and writing operations can be performed if the cache block is in invalid state. The cache block is said to be in invalid state if the required location is not present in the cache.Advantages of MSI Protocol 1) There is a difference between M and S states. 2) As it contains S state multiple copies of block can be present at the same time. 3) S to M transition can be made without reading data from cache. Disadvantages of MSI Protocol 1) Whenever write request is issued, the state though it is the only copy present.changes from S to M and invalidate message is sent e v e n2) During a read, though there is only one copy present, the block goes to S state. MESI Protocol It is an extension to MSI Protocol. Each cache block can be in any one of the four states i.e., modified, exclusive, shared, invalid [5-6]. a)Modified: Modified means the data present in the cache line is different from the data present in the main memory. If the cache block is in modified state then it can perform read and write operation.b) Exclusive: The data present in the cache line is same as that present in the main memory and it is the only cached copy. c)Shared: The data present in the cache is similar to the data present in the main memory. The same location may be present in other caches also.d) Invalid: No reading and writing operations can be performed if the cache block is invalid state. The cache block is said to be in invalid state if the required location is not present in the cache.Š 2019, IRJET|Impact Factor value: 7.211|ISO 9001:2008 Certified Journal|Page 1764International Research Journal of Engineering and Technology (IRJET) Volume: 06 Issue: 06 | June 2019www.irjet.nete-ISSN: 2395-0056 p-ISSN: 2395-0072Figure 2.1: Evolution from MI to MSI and MSI to MESI Entry contains data as well as tag as shown in the figure3.1 below.Figure 2.2 Cache coherence in multiprocessor systems using MESI protocol Cache memory Cache memory is being used in the modern computer systems, to temporarily hold the currently used contents of the main memory locations. Data present in the cache memory can be accessed in less time than from main memory; therefore cache memory is faster memory. Cache memory is expensive than main memory even though it is much smaller than main memory. Cache entries Data is transferred between memory and cache in blocks of fixed size, called cache lines. A cache entry is created, when a cache line is copied from memory to the cache. The cacheŠ 2019, IRJET|Impact Factor value: 7.211|ISO 9001:2008 Certified Journal|Page 1765International Research Journal of Engineering and Technology (IRJET) Volume: 06 Issue: 06 | June 2019www.irjet.nete-ISSN: 2395-0056 p-ISSN: 2395-0072Figure 3.1: Cache entry Tags are added to the cache entry along with data in order to supply the remaining bits of address, which are used to differentiate memory locations that are mapped to the same cache block. When the processor wants to read from a location or write to a location, it first checks for a corresponding entry in the cache. If the location is found in the cache then cache hit has occurred. If cache hit occurs the processor immediately reads the data from the cache line or writes the data into the cache line. If the location is not found in the cache, then cache miss has occurred, so it reads the data from main memory and copies this data into the cache. Cache performance To have a good cache performance, a high h i t ratio a n d h i g h s e a r c h speed are required. The cache hit rate means the number of times hits occurred to the total number of accesses. The possibilities of cache containing memory addresses that the processor wants needs to be increased. The cache performance will be increased if more number of hits occur and decrease with more number of misses. A cache hit is said to occur, when the processor requested location is found in t h e cache entry. A cache miss is said to occur, when the processor requested location is not found in the cache entry. For a miss, the cache is going to get the data from memory and the data will be placed into the cache, so this takes more time and hence the performance of cache reduces. Write policies When a write operation is performed, the data that was written into the cache need to be copied to the main memory at some point of time. In cache there are two writing policies. They are write-through and write-back [7]. 1. Write-through: In this policy every write to the cache is reflected immediately to main memory. 2. Write-back: In this policy writes are not immediately reflected to main memory. In this whenever a write operation is performed on cache, it is marked dirty. If the cache line marked dirty is evicted from cache block, the changed data is written to that particular location in main memory and the dirty bit is made to zero. In this paper write- back mechanism is used. Operations performed on cache four operations are performed on cache [8]. They are: 1) Read hit 2) Read miss 3) Write hit 4) Write missŠ 2019, IRJET|Impact Factor value: 7.211|ISO 9001:2008 Certified Journal|Page 1766International Research Journal of Engineering and Technology (IRJET) Volume: 06 Issue: 06 | June 2019www.irjet.nete-ISSN: 2395-0056 p-ISSN: 2395-0072Read hit If processor wants to read a value f r o m a location and if that location is found in cache then read hit is said to be occurred. Read miss If processor wants to read a value f r o m a location and if that location is not found in cache then read miss occurs. Write hit If processor wants to write a value to a location and if that location is found in cache then write hit is said to be occurred. Write miss If processor wants to write a value to a location and if that location is not found in cache then write miss occurs. Now the processor writes that value in the main memory and caches that value. CACHE Design To the cache the processor sends four input signals, they are cpu cac add, cpu cac read, cpu cac data and cpu cac wrt. To the processor the cache sends three outputs they are cac cpu hit, cac cpu miss, cac cpu data. If the processor requested address location is not found in cache then the cache sends cac mem read, cac mem add, cac mem data and cac mem wrt as inputs to the memory. After data is fetched from memory, the data is placed in the cache through mem cac data signal sent by the memory to the cache as shown in the figure 3.2 .Figure 3.2: Architectural view The memory that is designed in this paper is of 32bytes. Therefore five address bits are required. Eight bytes size direct mapped cache is designed in this paperŠ 2019, IRJET|Impact Factor value: 7.211|ISO 9001:2008 Certified Journal|Page 1767International Research Journal of Engineering and Technology (IRJET) Volume: 06 Issue: 06 | June 2019www.irjet.nete-ISSN: 2395-0056 p-ISSN: 2395-0072Simulation results for single cache Simulation result for read hit When reset (rst 1) is ‘0’, the cache memory is loaded with the initial values. When rst 1 is ‘1’, the cpu sends read signal (cpu cac read) and address (cpu cac add) to the cache. The cpu cac add sent by the cpu to cache is “11000”. The cpu cac add is divided into cpu tag and cpu index. The MSB 2bits indicate the cpu tag and the LSB 3bits indicate the cpu index. Therefore, cpu tag is “11” and cpu index is “000”. In cache at ‘0’ index the value present is 011100000100. The MSB bit indicates the dirty bit, 10th bit indicates the valid bit, 9th and 8th bits are tag bits(cur tag), 7 to 0 bits are the data bits. At 20ns the cpu sends the read signal. The cache compare the cpu tag and cur tag. As both are matched, the cache sends the hit (cac cpu hit) signal and data(cac cpu data) i.e.,00000100 to the cpu.Figure 4.1.2: Cache read hit Simulation result for read miss When reset (rst 1) is ‘0’, the cache memory is loaded with the initial values. When rst 1 is ‘1’, the cpu sends read signal(cpu cac read) and address(cpu cac add) to the cache. The cpu cac add sent by the cpu to cache is “01101”. The cpu cac add is divided into cpu tag and cpu index. The MSB 2bits indicate the cpu tag and the LSB 3bits indicate the cpu index. Therefore, cpu tag is “01” and cpu index is “101”. In cache at index 5, the value present is 011000001010. The MSB bit indicates the dirty bit, 10th bit indicates the valid bit, 9th and 8th bits are tag bits(cur tag), 7 to 0 bits are the data bits. At 20ns the cpu sends the read signal. The cache compares the cpu tag and cur tag. The cpu tag is “01” and cur tag is “10”. There is a mismatch, therefore cache sends cac cpu miss signal to the CPU. The cache reads the data from memory and place the value in cache. Now the cache contains 010100001110. After placing the value in cache, the cache sends cac cpu hit signal and cac cpu data i.e., 00001110 to the cpu.© 2019, IRJET|Impact Factor value: 7.211|ISO 9001:2008 Certified Journal|Page 1768International Research Journal of Engineering and Technology (IRJET) Volume: 06 Issue: 06 | June 2019www.irjet.nete-ISSN: 2395-0056 p-ISSN: 2395-0072Figure 4.1.3: Cache read miss Simulation results for write hit When reset (rst 1) is ‘0’, the cache memory is loaded with the initial values. When rst 1 is ‘1’, the cpu sends write signal (cpu cac wrt), data (cpu cac data) and address (cpu cac add) to the cache. The cpu cac add sent by the cpu to cache is “11000” and cpu cac data is “00001000”. The cpu cac add is divided into cpu tag and cpu index. The MSB 2bits indicate the cpu tag and the LSB 3 bits indicate the cpu index. Therefore, cpu tag is “11” and cpu index is “000”. In cache at ‘0’ index the value present is 011100000100. The MSB bit indicates the dirty bit, 10th bit indicates the valid bit, 9th and 8th bits aretag bits(cur tag), 7 to 0 bits are the data bits. At 20ns the cpu sends the write signal and cpu cac data. The cache compares the cpu tag and cur tag. As both are matched, the cache sends the hit (cac cpu hit) signal and writes the new data into the cache. Now the cache contains 111100001000. The dirty bit is set to 1 in the cache entry to indicate that the data present in the cache is modified and different from that present in main memory.Figure 4.1.4: Cache write hit© 2019, IRJET|Impact Factor value: 7.211|ISO 9001:2008 Certified Journal|Page 1769International Research Journal of Engineering and Technology (IRJET) Volume: 06 Issue: 06 | June 2019www.irjet.nete-ISSN: 2395-0056 p-ISSN: 2395-0072Simulation results for write miss and read hit When reset (rst 1) is ‘0’, the cache memory is loaded with the initial values. When rst 1 is ‘1’, the cpu sends write signal(cpu cac wrt),data (cpu cac data) and address (cpu cac add) to the cache. The cpu cac add sent by the cpu to cache is “10000” and cpu cac data is “00001000”. The cpu cac add is divided into cpu tag and cpu index. The MSB 2bits indicate the cpu tag and the LSB 3 bits indicate the cpu index. Therefore, cpu tag is “10” and cpu index is “000”. In cache at ‘0’ index the value present is 011100000100. The MSB bit indicates the dirty bit, 10th bit indicates the valid bit, 9th and 8th bits are tag bits(cur tag), 7 to 0 bits are the data bits. At 20ns the cpu sends the write signal and cpu cac data. The cache compares the cpu tag and cur tag. There is a mismatch, the cache sends the miss (cac cpu miss) signal and writes the new data into the cache. Now the cache contains 111000001000. The dirty bit is set to 1 in the cache entry to indicate that the data present in the cache is modified and different from that present in main memory. After 20ns the cpu sends read signal. As the tags matched, the cache sends cac cpu hit signal and cac cpu data 00001000 to the cpu.Figure 4.1.5: Cache write miss and read hit Simulation result for write back When reset (rst 1) is ‘0’, the cache memory is loaded with the initial values. When rst 1 is ‘1’, the cpu sends write signal(cpu cac wrt),data (cpu cac data) and address (cpu cac add) to the cache. The cpu cac add sent by the cpu to cache is “10000” and cpu cac data is “00001000”. The cpu cac add is divided into cpu tag and cpu index. The MSB 2bits indicate the cpu tag and the LSB 3 bits indicate the cpu index. Therefore, cpu tag is “10” and cpu index is “000”. In cache at ‘0’ index the value present is 011100000100. The MSB bit indicates the dirty bit, 10th bit indicates the valid bit, 9th and 8th bits are tag bits(cur tag), 7 to 0 bits are the data bits. At 20ns the cpu sends the write signal and cpu cac data. The cache compares the cpu tag and cur tag. There is a mismatch, the cache sends the miss (cac cpu miss) signal and writes the new data into the cache. Now the cache contains 111000001000. The dirty bit is set to 1 in the cache entry to indicate that the data present in the cache is modified and different from that present in main memory. After 12ns the cpu sends read signal and address. 11000. The tags are not matched so cac cpu miss signal is sent to the processor. The controller checks the dirty bit© 2019, IRJET|Impact Factor value: 7.211|ISO 9001:2008 Certified Journal|Page 1770International Research Journal of Engineering and Technology (IRJET) Volume: 06 Issue: 06 | June 2019www.irjet.nete-ISSN: 2395-0056 p-ISSN: 2395-0072before placing a new cache entry. The dirty bit is set to 1 so, the controller writes back the modified data to main memory and clears the dirty bit. Now new entry is placed and tags got matched so, cac cpu hit signal and cac cpu data is 00000100 is sent to the processor.Figure 4.1.6: Cache write back mechanism Simulation result for read hit and read miss When reset (rst 1) is ‘0’, the cache memory is loaded with the initial values. When rst 1 is ‘1’, the cpu sends read signal(cpu cac read and address (cpu cac add) to the cache. The cpu cac add sent by the cpu to cache is “11000”. The cpu cac add is divided into cpu tag and cpu index. The MSB 2bits indicate the cpu tag and the LSB 3 bits indicate the cpu index. Therefore, cpu tag is “11” and cpu index is “000”. In cache at ‘0’ index the value present is “011100000100”. The MSB bit indicates the dirty bit, 10th bit indicates the valid bit, 9th and 8th bits are tag bits(cur tag), 7 to 0 bits are the data bits.At 20ns the cpu sends the write signal and cpu cac data. The cache compares the cpu tag and cur tag. There is a match ,therefore the cache sends the hit (cac cpu hit) signal and cac cpu data “00000100”.After 10ns the cpu sends cpu cac read and address 01001 to the cache. The cpu tag is “01” and cur tag is “10”. There is a mismatch in tags so, cac cpu miss signal is sent to the processor. The data is now read from memory and placed in cache. Now the cache index 1 contains “010110001000”. Now tags are matched, so cac cpu hit signal and cac cpu data “10001000” is sent to the cpu.Figure 4.1.7: Cache read hit and read miss© 2019, IRJET|Impact Factor value: 7.211|ISO 9001:2008 Certified Journal|Page 1771International Research Journal of Engineering and Technology (IRJET) Volume: 06 Issue: 06 | June 2019www.irjet.nete-ISSN: 2395-0056 p-ISSN: 2395-0072Results Simulation results Simulation result for local cache read hit When reset (rst 1) is ‘0’, the cache memories are loaded with the initial values. When rst 1 is ‘1’, the cpu sends read signal(cpu cac read) and address (cpu cac add) to the cache. The cpu cac add sent by the cpu to cacheA is “00111”. The cpu cac add is divided into cpu tag A and cpu index A. The MSB 2 bits indicate the cpu tag and the LSB 3 bits indicate the cpu index. Therefore, cpu tag A is “00” and cpu index A is “111”. In cacheA at index 7, the value present is “01010000010100”. The MS
Related Search
Advertisement
Related Documents
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks
SAVE OUR EARTH

We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

More details...

Sign Now!

We are very appreciated for your Prompt Action!

x