Computer Science and Engineering Advanced Computer Architecture Experiments

MOESI Cache Coherence Protocol

This experiment demonstrates the MOESI cache coherence protocol through an interactive simulation. Follow these step-by-step instructions to understand how cache states transition and observe bus traffic patterns.

Step 1: Understanding the Interface

  1. Review the MOESI State Transition Table at the top of the simulator

    • Observe the 5 states: Modified (M), Owned (O), Exclusive (E), Shared (S), Invalid (I)
    • Note the color coding for each state
    • Study the transition conditions and bus actions

  2. Examine the Simulation Controls

    • Processor Selection: Choose between Processor 0 (P0) and Processor 1 (P1)
    • Operation Type: Select either PrRd (Processor Read) or PrWr (Processor Write)
    • Memory Address: Choose from addresses 0x0, 0x1, 0x2, or 0x3
    • Data Value: Enter data for write operations (enabled only for writes)

  3. Monitor Cache States

    • View the current state of each cache line
    • Observe cache performance statistics (hits/misses)
    • Track valid/invalid status of cache lines

Basic Exercises

Exercise 1: Understanding Cache Miss Behavior

  1. Initial Read Miss (I → E)

    • Select Processor 0
    • Choose PrRd (Processor Read)
    • Select Memory Address 0x0
    • Click "Execute Operation"
    • Observe: P0 cache line transitions from Invalid (I) to Exclusive (E)
    • Note: Bus activity shows "BusRd" and cache miss is recorded

  2. Sharing Creation (E → S)

    • Select Processor 1
    • Choose PrRd (Processor Read)
    • Select Memory Address 0x0 (same address)
    • Click "Execute Operation"
    • Observe:
      • P0: Exclusive (E) → Shared (S)
      • P1: Invalid (I) → Shared (S)
    • Note: Both processors now share the same data

Exercise 2: Write Operations and Invalidation

  1. Write Hit from Shared (S → M)

    • Select Processor 0
    • Choose PrWr (Processor Write)
    • Select Memory Address 0x0
    • Enter Data Value: "100"
    • Click "Execute Operation"
    • Observe:
      • P0: Shared (S) → Modified (M)
      • P1: Shared (S) → Invalid (I)
    • Note: Bus activity shows "BusUpgr" (Bus Upgrade)

  2. Write Miss (I → M)

    • Select Processor 1
    • Choose PrWr (Processor Write)
    • Select Memory Address 0x1 (different address)
    • Enter Data Value: "200"
    • Click "Execute Operation"
    • Observe: P1 cache line 0x1 transitions from Invalid (I) to Modified (M)

Exercise 3: The Owned State in Action

  1. Creating the Owned State (M → O)

    • First, ensure P0 has Modified data at address 0x0 from previous steps
    • Select Processor 1
    • Choose PrRd (Processor Read)
    • Select Memory Address 0x0
    • Click "Execute Operation"
    • Observe:
      • P0: Modified (M) → Owned (O)
      • P1: Invalid (I) → Shared (S)
    • Note: P0 retains ownership while P1 gets a shared copy

  2. Maintaining Ownership

    • Select Processor 0
    • Choose PrRd (Processor Read)
    • Select Memory Address 0x0
    • Click "Execute Operation"
    • Observe: P0 remains in Owned (O) state - read hit

Advanced Exercises

Exercise 4: Silent Upgrade (E → M)

  1. Exclusive to Modified Transition
    • Select Processor 0
    • Choose PrRd (Processor Read)
    • Select Memory Address 0x2 (new address)
    • Click "Execute Operation"
    • Observe: P0 gets Exclusive (E) access
  2. Silent Upgrade
    • Keep Processor 0 selected
    • Choose PrWr (Processor Write)
    • Select Memory Address 0x2 (same address)
    • Enter Data Value: "300"
    • Click "Execute Operation"
    • Observe: P0 transitions from Exclusive (E) to Modified (M)
    • Note: No bus traffic generated (silent upgrade)

Exercise 5: Complex State Interactions

  1. Multi-Cache Sharing Pattern

    • Create a scenario where multiple addresses have different states
    • Try operations like:
      • P0 reads 0x0, P1 reads 0x0 (both Shared)
      • P0 writes 0x1 (Modified)
      • P1 reads 0x1 (P0: Modified → Owned, P1: Invalid → Shared)
      • P1 writes 0x0 (P0: Shared → Invalid, P1: Shared → Modified)

  2. Analyzing the Transaction Log

    • Review the Bus Transaction Log table
    • Understand each column:
      • Processor Activity: What operation was performed
      • Bus Activity: What bus transactions occurred
      • P0/P1 Content: Data values in each cache
      • P0/P1 State: Current cache states
      • P0/P1 Transition: State changes that occurred
      • Memory: Memory content

Performance Analysis

Exercise 6: Cache Performance Metrics

  1. Hit Rate Analysis

    • Perform multiple operations on the same addresses
    • Observe how cache hit rates improve with repeated accesses
    • Compare hit rates between processors

  2. Bus Traffic Observation

    • Count the number of bus transactions for different operation sequences
    • Compare MOESI efficiency with simpler protocols (theoretical)

Suggested Experiment Sequences

Sequence A: Basic Protocol Flow

          1. P0 reads 0x0 → P0: I→E
          2. P1 reads 0x0 → P0: E→S, P1: I→S
          3. P0 writes "ABC" to 0x0 → P0: S→M, P1: S→I
          4. P1 reads 0x0 → P0: M→O, P1: I→S

Sequence B: Exclusive State Benefits

          1. P0 reads 0x1 → P0: I→E
          2. P0 writes "XYZ" to 0x1 → P0: E→M (no bus traffic)
          3. P1 reads 0x1 → P0: M→O, P1: I→S

Sequence C: Multiple Address Management

          1. P0 reads 0x0 → P0: I→E
          2. P0 reads 0x1 → P0: I→E
          3. P1 reads 0x0 → P0: E→S, P1: I→S
          4. P1 writes "123" to 0x1 → P0: E→I, P1: I→M

Learning Objectives Check

After completing these exercises, you should be able to:

  1. ✓ Identify MOESI States: Recognize when and why each state is used
  2. ✓ Predict Transitions: Anticipate state changes before executing operations
  3. ✓ Understand Bus Traffic: Explain why certain operations generate bus activity
  4. ✓ Analyze Performance: Compare different access patterns and their efficiency
  5. ✓ Apply Knowledge: Design cache access patterns for optimal performance

Troubleshooting Tips

  • No State Change: If an operation doesn't change states, it's likely a cache hit
  • Unexpected Transitions: Review the state transition table to understand the logic
  • Bus Traffic: Remember that cache-to-cache transfers avoid memory access
  • Invalid States: Understand that Invalid doesn't mean error - it's a valid protocol state

Additional Experiments

Try these advanced scenarios:

  • Write-Through vs Write-Back: Observe when data is written to memory
  • Cache Line Eviction: See what happens when cache fills up
  • Mixed Access Patterns: Combine reads and writes on multiple addresses
  • Performance Comparison: Mentally compare with simpler protocols like MSI

Follow these step-by-step instructions to understand and experiment with the MOESI cache coherence protocol:

Pre-Experiment Setup

  1. Review the Theory Section

    • Understand the five MOESI states: Modified (M), Owned (O), Exclusive (E), Shared (S), Invalid (I)
    • Familiarize yourself with processor operations (PrRd, PrWr) and bus operations (BusRd, BusRdX, BusUpgr)

  2. Understand the Simulation Interface

    • The simulator shows two processors (P0 and P1) with their respective caches
    • Each cache has 4 lines (indices 0-3)
    • Memory addresses are mapped to cache lines using modulo operation

Basic Operations

Step 1: Initial Cache State Observation

  1. Launch the simulation
  2. Observe the initial state - All cache lines start in Invalid (I) state
  3. Note the interface elements:
    • Processor selection (P0 or P1)
    • Operation type (Read/Write)
    • Memory address input
    • Data value input (for write operations)

Step 2: First Read Operation (Cold Miss)

  1. Select Processor P0
  2. Choose operation type: Read (PrRd)
  3. Enter memory address: 0
  4. Click "Execute Operation"
  5. Observe the results:
    • P0's cache line 0 transitions from Invalid (I) to Exclusive (E)
    • Bus generates BusRd transaction
    • Data is loaded from memory
    • Transaction log shows the state transition

Step 3: Read from Same Address by Different Processor

  1. Select Processor P1
  2. Choose operation type: Read (PrRd)
  3. Enter memory address: 0
  4. Execute the operation
  5. Analyze the outcome:
    • P0's cache line 0: Exclusive (E) → Shared (S)
    • P1's cache line 0: Invalid (I) → Shared (S)
    • Bus activity shows data sharing

Step 4: Write Operation on Shared Data

  1. Select Processor P0
  2. Choose operation type: Write (PrWr)
  3. Enter memory address: 0
  4. Enter data value: 42
  5. Execute the operation
  6. Examine the changes:
    • P0's cache line 0: Shared (S) → Modified (M)
    • P1's cache line 0: Shared (S) → Invalid (I)
    • Bus generates BusUpgr to invalidate other copies

Advanced Scenarios

Step 5: Demonstrating the Owned State

  1. Reset the simulation
  2. P0 writes to address 4:
    • Select P0, Write operation, address 4, data "100"
    • P0's cache line 0 becomes Modified (M)
  3. P1 reads from address 4:
    • Select P1, Read operation, address 4
    • P0's cache line 0: Modified (M) → Owned (O)
    • P1's cache line 0: Invalid (I) → Shared (S)
    • P0 supplies data to P1 (cache-to-cache transfer)

Step 6: Write to Owned Data

  1. Continue from Step 5
  2. P0 writes to address 4 again:
    • P0's cache remains in Owned (O) state (or transitions to Modified)
    • Data is updated without invalidating P1's copy initially
  3. Observe the coherence maintenance

Step 7: Exclusive to Modified Transition

  1. Reset the simulation
  2. P0 reads from a new address (address 8):
    • P0's cache line 0 becomes Exclusive (E)
  3. P0 writes to the same address:
    • P0's cache line 0: Exclusive (E) → Modified (M)
    • No bus traffic generated (silent transition)

Step 8: Complex Multi-Address Scenario

  1. Perform the following sequence:
    • P0 reads address 0 (becomes Exclusive)
    • P0 reads address 4 (becomes Exclusive in line 0)
    • P1 reads address 0 (both become Shared)
    • P1 writes address 0 (P1 becomes Modified, P0 becomes Invalid)
    • P0 reads address 0 (P1 becomes Owned, P0 becomes Shared)

Analyzing Results

Step 9: Transaction Log Analysis

  1. Review the transaction log after each operation
  2. Identify the components:
    • Processor activity description
    • Bus activity generated
    • State transitions for both processors
    • Memory content changes

Step 10: State Transition Table Verification

  1. Compare observed transitions with the MOESI state transition table
  2. Verify correctness of each state change
  3. Understand the bus operations generated for each transition

Step 11: Performance Analysis

  1. Count cache hits vs. misses for different scenarios
  2. Observe bus traffic patterns for various operation sequences
  3. Analyze memory bandwidth utilization

Experimental Exercises

Exercise 1: Cache Hit Rate Analysis

  1. Perform 10 random read/write operations
  2. Calculate the cache hit rate for each processor
  3. Compare hit rates between processors

Exercise 2: Bus Traffic Optimization

  1. Design a sequence of operations that minimizes bus traffic
  2. Design a sequence that maximizes bus traffic
  3. Compare the two scenarios

Exercise 3: Coherence Overhead Measurement

  1. Measure the number of bus transactions for a given workload
  2. Compare with an ideal scenario (no coherence required)
  3. Calculate the coherence overhead percentage

Exercise 4: State Distribution Analysis

  1. Run a long sequence of operations
  2. Record the frequency of each MOESI state
  3. Analyze which states are most commonly used

Common Observations and Learning Points

Key Observations:

  • Cold misses always result in Exclusive state (if no sharing)
  • Sharing automatically downgrades Exclusive to Shared
  • Write operations on shared data trigger invalidations
  • Owned state enables efficient sharing of modified data
  • Cache-to-cache transfers reduce memory traffic

Learning Outcomes:

  • Understanding of cache coherence complexity
  • Appreciation for protocol optimization
  • Recognition of performance trade-offs
  • Insight into multiprocessor system design

Troubleshooting Tips

  1. If simulation doesn't respond: Refresh the page and try again
  2. If state transitions seem incorrect: Verify your understanding with the theory section
  3. If confused about bus operations: Review the state transition table
  4. For complex scenarios: Break down into simpler steps

Post-Experiment Analysis

  1. Summarize key findings from your experiments
  2. Compare MOESI behavior with simpler protocols (if familiar)
  3. Consider real-world implications of observed behaviors
  4. Reflect on scalability and performance aspects