Parallel Processors

Parallel processors execute multiple operations concurrently to increase throughput. Classified by Flynn's taxonomy:

• SISD: Single Instruction Single Data - conventional uniprocessor.
• SIMD: Single Instruction Multiple Data - array/vector processors, e.g., GPU, vector supercomputer.
• MISD: Multiple Instruction Single Data - rare, pipelined architectures.
• MIMD: Multiple Instruction Multiple Data - most parallel computers. Two models:
  1. Shared Memory (Tightly coupled): All processors share a common main memory via interconnection network (bus, crossbar, multistage). Sub-types: UMA (uniform memory access / SMP) - equal access time; NUMA - distributed shared memory, non-uniform latency; COMA/COMA.
  2. Distributed Memory (Loosely coupled): Each processor has private memory, communicates via message passing.
• Multicore / Multiprocessor: Modern CMPs are MIMD shared-memory on single chip.

Parallelism levels: Job-level, task-level, instruction-level and loop-level.

Cache Coherency Problem in Shared Memory

In shared-memory MIMD, each processor has private cache for latency reduction. Coherency problem: If multiple caches hold a copy of same memory block $X$, and one processor writes $X$, other copies become stale, leading to inconsistent views.

Example: $P_1$ and $P_2$ cache $X=5$. $P_1$ does $X \leftarrow 10$ in its cache, $P_2$ still sees $X=5$. Memory may be 5 or 10 depending on write-through/write-back - inconsistency.

Coherence requires: (1) Writes to same location seen in same order by all processors (write serialization), (2) Read returns last written value.

Solutions:

1. Snooping (Snoopy) Protocol - for bus-based SMPs: Every cache monitors (snoops) bus transactions.

   • Write-Invalidate: On write hit, processor broadcasts invalidate to all other caches holding block. Others discard copy. Most common (MESI/MOESI).
   • Write-Update (Write-Broadcast): Write is broadcast to update all copies.

2. Directory-Based Protocol - for scalable networks / NUMA: Central directory keeps state of each block (which caches have copy, dirty/clean). On write, directory sends point-to-point invalidates only to holders. Avoids broadcast overhead.

3. MESI States (Illinois Protocol):

   • M (Modified): Dirty, exclusive.
   • E (Exclusive): Clean, exclusive.
   • S (Shared): Clean, may be shared.
   • I (Invalid): Not valid.

On Read Miss → BusRd, on Write → BusRdX / BusUpgr, state transitions enforce coherence.

Coherence is handled in hardware; software must ensure consistency model (sequential consistency, etc.).