More Related Content
What's hot (20)
Recently uploaded (20)
캐쉬 일관성 Msi, mesi 프로토콜 흐름
- 1. Extra Cache Coherence Examples In the following examples there are a couple questions. You can answer these for practice by emailing Colin at cdbryan@gmail.com.
- 2. MSI Protocol There are three processors. Each is reading/writing the same value from memory where r1 means a read by processor 1 and w3 means a write by processor 3. For simplicity sake, the memory location will be referred to as “value.” The memory access stream is: r1, r2, w3, r2, w1, w2, r3, r2, r1
- 3. P1 P2 P3 Snooper Snooper Snooper P1 wants to read the value. The cache does not have itand generates a BusRd for the data. Main memory controller provides the data. The data goes into the cache in the shared state. r1 PrRd BusRd value S Main Memory
- 4. P1 P2 P3 PrRd value S Snooper Snooper Snooper BusRd r2 value S Main Memory P2 wants to read the value. Its cache does not have the data, so it places a BusRd to notify other processors and ask for the data. The memory controller provides the data.
- 5. P1 P2 P3 value S Snooper Snooper Snooper w3 value S P3 wants to write the value. It places a BusRdX to get exclusive access and the most recent copy of the data. The caches of P1 and P2 see the BusRdX and invalidate their copies. Because the value is still up-to-date in memory, memory provides the data. PrWr BusRdX I I value M Main Memory
- 6. P1 P2 P3 PrRd S S value I value M Snooper Snooper Snooper Flush Main Memory r2 value I BusRd P2 wants to read the value. P3’s cache has the most up-to-date copy and will provide it. P2’s cache puts a BusRd on the bus. P3’s cache snoops this and cancels the memory access because it will provide the data. P3’s cache flushes the data to the bus.
- 7. P1 P2 P3 PrWr M I I value I value S Snooper Snooper Snooper w1 value S BusRdX Main Memory P1 wants to write to its cache. The cache places a BusRdX on the bus to gain exclusive access and the most up-to-date value. Main memory is not stale so it provides the data. The snoopers for P2 and P3 see the BusRdX and invalidate their copies in cache.
- 8. P1 P2 P3 PrWr I M value M value I Snooper Snooper Snooper w2 value I BusRdX Flush Main Memory P2 wants to write the value. Its cache places a BusRdX to get exclusive access and the most recent copy of the data. P1’s snooper sees the BusRdX and flushes the data to the bus. Also, it invalides the data in its cache and cancels the memory access.
- 9. P1 P2 P3 S S value I value I Snooper Snooper Snooper Flush Main Memory r3 value M PrRd BusRd P3 wants to read the value. Its cache does not have a valid copy, so it places a BusRd on the bus. P2 has a modified copy, so it flushes the data on the bus and changes the status of the cache data to shared. The flush cancels the memory accecss and updates the data in memory as well.
- 10. P1 P2 P3 PrRd value I value S Snooper Snooper Snooper r2 value S Main Memory P2 wants to read the value. Its cache has an up-to-date copy. No bus transactions need to take place as there is no cache miss.
- 11. P1 P2 P3 value I value S Snooper Snooper Snooper r1 value S P1 wants to read the value. The cache does not have it, so it places a BusRd onto the bus for the data. The memory controller provides the data as it has an up-to-date copy. The data goes into the cache in the shared state. PrRd BusRd S Main Memory
- 12. MESI Protocol There are three processors. Each is loading or storing different words from memory given as w0, w1, and w2. These all map to the same location in cache.
- 13. The memory accesses are as follows: P1: ld w0, P3: ld w2 P1: st w0, P2: st w2 P2 st w2, P3 ld w0 P3: st w0 P1: ld w2 P2: ld w1 P3: ld w1
- 14. P1 P3 Snooper Snooper Snooper P1 ld w0 P3 ld w2 In both loads, a cache miss happens so each cache puts a BusRd onto the bus for the information. Main memory is the owner and will provide the up-to-date data. P1’s cache loads w0 in the E state. P3’s cache loads w2 in the E state as well. PrRd BusRd(¬S) PrRd BusRd (¬S) P2 w0 E w2 E Main Memory
- 15. P1 P3 M w2 M I w0 E w2 E Snooper Snooper Snooper P1 st w0 P2 st w2 P1 has w0 in the exclusive state, so on the cache hit, it does not need to have a bus transaction. w2 is not in P2’s cache, so the cache places a BusRdX to gain exclusive access. Main memory provides the data because it is not stale even though P3’s cache has the data. w2 is loaded in M state and P3’s cache invalidates its copy of w2. PrWr Flush P2 PrWr BusRdX Main Memory
- 16. P2 st w0 P3 ld w0 P2 P1 P3 PrWr PrRd S w0 S w0 M w2 M w2 I Snooper Snooper Snooper BusRd(S) Flush Main Memory P2 executes another store to w2. It already has exclusive access to w2 and the store results in a cache hit. No bus transaction is issued by P2’s cache. P3 wants to load w0. This results in a cache miss and the cache issues a BusRd transaction. P1’s cache asserts the S signal because it has a dirty w0 and provides the up-to-date data through a flush. P1 changes its state to S. P3’s cache loads w0 in the S state.
- 17. P1 P2 P3 I w2 M w0 S w0 S Snooper Snooper Snooper P3 st w0 PrWr M Main Memory P3 executes a store to w0. Both P1 and P3 have an up-to-date, unmodified w0. What bus transactions are needed?
- 18. P1 P2 P3 w2 S w0 S w2 M w0 M Snooper Snooper Snooper Main Memory P1 ld w2 P1 wants to load w2. P1’s cache does not have w2, so it issues a BusRd transaction. P2’s cache turns on the S signal, so P1’s cache knows to load w2 in the S state. P2’s cache provides w2 for P1 and cancels the access to main memory through a Flush. PrRd BusRd(S) S Flush
- 19. P1 P2 P3 PrRd w1 E w2 S w2 S w0 M Snooper Snooper Snooper P2 ld w1 BusRd(¬S) Main Memory P2 wants to load w1. This generates a cache miss. P2’s cache issues a BusRd transaction. The S signal is not asserted, so it knows that it has exclusive access to w1. Main memory provides the data for w1. Should the state of w2 be changed in P1 because it is the only cache that has a copy of w2?
- 20. P1 P2 P3 PrRd S w1 S w2 S w1 E w0 M Snooper Snooper Snooper P3 ld w1 BusRd(S) Flush Main Memory P3 wants to load w1. This generates a cache miss. P3’s cache issues a BusRd transaction. The S signal is asserted by P2’s cache, so P3’s cache knows that it will load w1 in the S state. Main memory provides the data for w1 because its copy is not stale. P3 flushes w0 before loading w1. Flush
- 21. Dragon Protocol In this system there are 3 processors. Each is loading or storing from memory locations w0, w1, w2, and w3. w0 and w1 are on the same cache line and are loaded at the same time. Likewise for w2 and w3. The two cache lines map to the same location in cache.
- 22. P1 P3 Snooper Snooper Snooper P1 ld w2 P1 wants to load w2. This generates a cache miss and P1’s cache issues a BusRd bus transaction. The S signal is not asserted, so the cache knows to load w2 and w3 in the E state. PrRd BusRd(¬S) P2 w2,w3 E Main Memory
- 23. P1 P3 w2, w3 E PrRd P2 w0, w1 E Snooper Snooper Snooper BusRd(¬S) P2 ld w0 Main Memory P2 wants to load w0. This generates a cache miss and P1’s cache issues a BusRd bus transaction. The S signal is not asserted, so the cache knows to load w0 and w1 in the E state.
- 24. P1 P3 w2, w3 E P2 E w0, w1 Sm Sc w0, w1 Snooper Snooper Snooper PrWr BusRd(S) P3 st w1 BusUpd Main Memory Update P3 wants to store w1. This generates a cache miss. Memory will provide the data as no other cache has this line in a modified state. After storing the new value of w1, P3’s cache issues a BusUpd. P2 snoops this and updates its cache with the updated w1.
- 25. P1 P2 P3 M w2, w3 E w0, w1 Sc w0, w1 Sm Snooper Snooper Snooper P1 st w3 PrRd Main Memory P1 issues store w3. It has exclusive access to this cache line. What bus transactions does P1’s cache issue?
- 26. P1 P2 P3 PrRd Sm w2, w3 M w2, w0, w1 w3 Sc w0, w1 Sm Snooper Snooper Snooper P2 ld w3 BusRd(S) ??? Main Memory Flush P2 wants to load w3. This generates a cache miss. P2’s cache issues a BusRd transaction. P1 asserts the S signal, so P2 will load the cache line in Sc state. P1’s cache has a modified version of the cache line, so it will provide the data for P2 with a flush transaction. P1’s cache will update the line’s state to Sm. Should P3 change w0/w1’s state to M?
- 27. P2 ld w2 P3 st w0 P2 P1 P3 PrRd PrWr w2, w3 Sm w2, w3 Sc w0, w1 ? Snooper Snooper Snooper Main Memory P2 wants to load w2. P3 wants to store w0. What are the necessary bus transactions and cache updates that need to take place?