Consider the following reference stream: r1(A), r2(A), w3(B), r2(A), r3(A), r1(B), r2(B), w3(B), w3(A), r1(A)
All of the references in the stream are to the same cache block but for different data words, A and B within the same cache block. r and w indicate read and write, respectively, and the digit refers to the processor issuing the reference.
We runMESIprotocol. Assume thatall caches are initially empty and the accessed cache block is not evicted while executing the reference stream. Use the following cost model:
•Read / write cache hit with no bus access: 1 cycle
•Invalidation broadcasting without requesting the cache block (BusUpgr): 10 cycles
•Request remote processor to send updated a cache block (BusRd / BusRdX): 50 cycles
•Request the memory (or next level cache) to send a cache block (BusRd): 150 cycles
Fill the following table with the coherence state of the three processors, coherence message, and cache hit/miss for each memory references. Each column should show the status of the corresponding data word (either A or B). Show the total number of cycles used for running the reference stream.
r2(B) w3(B) w3(A) r1(A) r1(A) r2(A) w3(B) r2(A) r3(A) r1(B) M BusRd E hit/miss bus Statel State2 State3 cycles I 1 150 The total number of cycles : cycles 1. bus row: the row will be filled with the message that the processor that takes the action will send out to all. For example, in the first action r1(A), processor 1 reads A so sends BusRd message to all. 2. State 1, State2, State3 rows: Each of these rows presents the new state of processor 1, 2, and 3, respectively. In other words, State1 will be filled with the new state that processor 1 will have, State2 will be for processor 2, and State3 will be for processor 3. For example, when r1(A) is executed (the first action), processor 1 will go to E state because processor 1 is the only processor that has the cache block so you can find E on the State 1 row. For the processors 2 and 3, they will receive the "BusRd" message from processor 1 and will stay in I state because they do not have the blocks yet so nothing to be done yet. 3. hit/miss row: This row should be filled by the processor that takes the action (e. g., in the first r1(A), processor 1 will have miss because it didn't have the cache block yet so you will fill 'M'iss). In the single CPU system, hit and miss was clear for you. But, in the multi-processor system, miss can happen when 1) the cache block is not in your cache already or 2) the cache block is invalid even when the block is in your cache already. Cache blocks can be invalid if remote processors make changes on it. So, think carefully if the processor that will take the action has a valid cache block in its cache already or not. 4. cycles row: Once you found what message will be sent out by the processor that takes the action (e. g., BusRd for the first r1(A)), find the corresponding delay for the message from the specification and fill it in. For example, as r1(A) will send BusRd, you can simply enter 150 cycles in the cycles row. If you think no message will be sent out for the corresponding action (normally the hit cases), you will enter 1 cycles as specified in the description (read/write cache hit : 1 cycle). 5. cache transition unit: As explained the lecture, this MESI state transition will happen per cache block unit, not in data word unit. In the problem, we assumed that word A and B are in the same cache block.