NPTEL Online Certification Course
Multi-Core Computer Architecture
Assignment-8: Detailed Solutions
Indian Institute of Technology Guwahati
1. In a directory-based cache coherence protocol, what does the E bit in the directory
entry for a cache block indicate?
a. The block is exclusively owned by the processor.
b. The block is shared by multiple processors.
c. The block is invalid in all caches.
d. The block is pending for eviction.
E bit indicates that a cache block is exclusively owned by a processor. This means that no
other processor has a copy of the block, and the processor can update the block without
notifying others.
2. Which one of the following statements is FALSE? [1 mark]
a. Write propagation ensures that a write is eventually seen by all the threads.
b. Memory consistency provides local ordering of accesses to all words in a
cache block.
c. Cache coherence provides local ordering of accesses to each cache block.
d. Write serialization ensures that writes to the same location are globally
ordered.
Memory consistency provides local ordering of accesses to all words in a cache
block. This statement is false. Memory consistency primarily focuses on the order in
which memory operations are perceived by different threads, not on the local ordering
of accesses to specific words within a cache block.
3. Which one of the following protocols ensures that a cache controller sends broadcast
messages in a common medium for other cache controllers connected to it for taking
appropriate cache coherence operations?
a. Write serialization protocols
b. Snoopy protocols
c. Directory based protocols
d. Consistency protocols
Snoopy protocols are a class of cache coherence protocols in which each cache
controller monitors or "snoops" the common communication medium (usually a
shared bus) for transactions initiated by other cache controllers. When a cache
controller observes a transaction that may affect its own cache's data, it takes
appropriate cache coherence actions, such as invalidating or updating its cache line to
maintain data consistency. These protocols rely on broadcast messages to keep caches
coherent and are efficient for smaller-scale systems.
4. What is the purpose of Write Propagation in memory consistency and cache
coherence? [1 mark]
a. It delays write operations to ensure coherence.
b. It ensures that the value written in one cache is propagated to at least one sharer i
in a predetermined order.
c. It guarantees that a write is eventually seen by all threads.
d. It blocks propagating the write values to other threads to ensure coherence.
Write propagation ensures that when a write operation is performed, the modified data
is eventually made visible to all threads in a multi-threaded system. This is essential
for maintaining memory consistency and ensuring that all threads have a coherent and
up-to-date view of the data. Write propagation helps prevent data inconsistencies and
synchronization issues in multi-threaded programs.
5. Two processors P1 and P2 use MSI protocol. A block X is initially only in memory
(value = 0).
Step 1: P1 reads X
Step 2: P2 reads X
Step 3: P1 writes X = 5
What is the state of X in P1 and P2 after Step 3? [1 mark]
a. P1: Modified, P2: Shared
b. P1: Modified, P2: Invalid
c. P1: Shared, P2: Shared
d. P1: Exclusive, P2: Shared
Step 1: P1 loads from memory → Exclusive (but MSI has no Exclusive, so it’s
Shared if others may load).
Step 2: P2 reads → both Shared.
Step 3: P1 writes → must invalidate P2 ,
P1 = Modified, P2 = Invalid.
6. Match the MESI states with their meaning: [1 mark]
Column 1 (States) Column 2 (Meaning)
A. M – Modified P. Block not present in cache
B. E – Exclusive Q. Block present in one cache, matches
memory
C. S – Shared R. Block present in multiple caches,
matches memory
D. I – Invalid S. Block updated in cache, not in
memory
a. A → S, B → Q, C → R, D → P
b. A → P, B → Q, C → R, D → S
c. A → S, B → R, C → Q, D → P
d. A → Q, B → S, C → R, D → P
Modified: dirty copy in one cache.
Exclusive: clean copy only in one cache.
Shared: clean copy may be in multiple caches.
Invalid: no valid copy.
7. A system uses the MESI cache coherence protocol. The initial value of variable X = 100
in memory. The following sequence of operations occurs:
Step 1: P1 reads X
Step 2: P2 reads X
Step 3: P1 writes X = 200
Step 4: P2 writes X = 300
Step 5: P1 reads X
What value does P1 observe in step 5, and what are the final cache states of X in both
processors? [2 marks]
a. Value = 200, P1: Modified, P2: Invalid
b. Value = 300, P1: Shared, P2: Shared
c. Value = 300, P1: Invalid, P2: Modified
d. Value = 100, P1: Shared, P2: Shared
Step 1: P1 reads X
I.e. 100
Step 2: P2 reads X
I.e. 100
Step 3: P1 writes X=200
=> For P1, Modified. (value different from main memory)
Rest all, Invalid.
Step 4: P2 writes X=300
=> For P2, Modified.
Rest all, Invalid.
Step 5: P1 reads X.
P1 has invalid state -> cache miss.
P2 writes data back to main memory.
Then P1 gets value from the main memory.
I.e. P1 Invalid->Shared.
P2 Modified -> Shared
=> P1 observes X=300.P1 -> Shared and P2 ->Shared
P1 P2
I I
S1 E I
S2 S S
S3 M I
S4 I M
S5 S S
8. Consider a multi- processing system with two cores A and B with their own private
caches and a single shared main memory. The following 5 lines of code is running in each of
the two cores. Since both A and B are using their private caches, MESI cache coherence
protocol is used for operation on shared variables.
1. LW R1, M1
2. LW R2, M2
3. SW R3, M2
4. SW R2, M1
5. LW R1, M2
LW indicates Load and SW indicates Store operation. Ri and Mj indicate Register and
Memory operands, respectively. Assume that the addresses pointed by M1 and M2
map to different cache blocks. Consider the following execution sequence in the
format; Core Name-Instruction Number. A-1, A-2, B-1, B-2, A-3, B-3, B-4, A-4, A-5,
B-5 (total 10 instruction instances).The initial state of all cache blocks is invalid IIII.
Which one of the following represents the state of these blocks after the execution of
the above 10 instruction sequences? [2 marks]
a. MMII
b. SSSS
c. MSIS
d. ISMI
State of M1 State of M2 State of M1
Core- Instruction in A in A in B State of M2 in
B
I I I
initial I
A-1 E I I
I
A-2 E E I
I
B-1 S E S
I
B-2 S S S S
A-3 S M S
I
B-3 S I S M
B-4 I I M M
A-4 M I I M
A-5 M S I S
B-5 M S I S