Multiprocessors can feel like disconnected Flynn letters, coherence acronyms and network diagrams. Yet GATE often asks you to calculate an Amdahl's law speedup or trace cached data. Both reduce to small rules: a serial fraction that caps every speedup, and four cache states that decide which processor holds the valid copy.
What a multiprocessor actually is, and Flynn's taxonomy
A multiprocessor has two or more processors sharing access to memory and I/O under one operating system. A tightly coupled system uses common memory and one address space, the shared-memory model. A loosely coupled system gives each processor local memory and uses message passing, like a distributed cluster.
Flynn's taxonomy classifies machines by instruction and data streams:
SISD: one instruction stream, one data stream, as in a classic uniprocessor.
SIMD: one instruction stream applies an operation to many data elements, as in vector units and GPU-style lanes.
MISD: multiple instruction streams operate on one data stream. It is rare and mostly theoretical.
MIMD: processors run independent instruction streams on different data. Modern multicore CPUs and true multiprocessors belong here.
A multicore CPU is MIMD, while its vector unit is SIMD. Confusing them is a standard exam trap. Multiprocessor parallelism is also different from the instruction overlap in Pipelining in Computer Architecture.
How processors are wired together
The interconnection structure decides cost and simultaneous memory traffic.
A time-shared common bus is cheapest, but its one transfer at a time becomes a bottleneck.
Multiport memory gives a module separate ports and uses fixed processor priorities for conflicts.
A crossbar has a switch at every processor-to-memory pair. It is non-blocking but expensive.
A multistage network uses layers of 2x2 switches. An Omega network costs less, but internal paths can collide.
For N = 8 processors and M = 8 memory modules, the crossbar count is:
N × M = 8 × 8 = 64 crosspoints
The Omega network has:
log₂(N) = log₂(8) = 3 stages
Each stage has N/2 = 8/2 = 4 switches, so:
3 × 4 = 12 switching elements
Structure | Cost for 8x8 | Blocking? |
|---|---|---|
Crossbar | 64 crosspoints | No |
Omega (multistage) | 12 2x2 switches | Yes |
Shared bus | 1 shared path | Serializes |
The choice is 64 non-blocking crosspoints versus 12 cheaper switching elements that can block. GATE often asks exactly these counts.
Memory organisation: UMA, NUMA and distributed memory
In UMA, every processor sees the same access time to all shared memory. The classic symmetric multiprocessor suits a modest count, but its shared interconnect limits growth.
In NUMA, memory is physically distributed. Local memory is faster than remote memory, so the operating system and programmer must care about placement. COMA is the cache-only variant, where local memories act as large caches.
A distributed-memory system has no shared address space. Nodes cooperate by explicit send and receive operations. Shared memory therefore needs cache-coherence hardware, while message passing avoids coherence but makes communication explicit. See Memory Hierarchy and Virtual Memory for the wider memory model.
Speedup and Amdahl's law
Processors do not multiply speed one-for-one because part of a program remains serial. If f is the parallelisable fraction and N is the processor count:
S = 1 / ((1 - f) + f/N), with efficiency E = S/N
Let f = 0.8, so 1 - f = 0.2, and N = 4:
S = 1 / ((1 - 0.8) + 0.8/4) = 1 / (0.2 + 0.2) = 1 / 0.4 = 2.5x
Now set N = 8:
S = 1 / (0.2 + 0.8/8) = 1 / (0.2 + 0.1) = 1 / 0.3 = 3.33x
As N tends to infinity, f/N tends to zero:
S_max = 1 / (1 - f) = 1 / 0.2 = 5x
Even unlimited processors cannot overcome the 20% serial part. Efficiency at N = 4 is:
E = S/N = 2.5/4 = 0.625 = 62.5%
At N = 8, E = 3.33/8 = 0.42, or about 42% against 62.5% at N = 4. More processors raise speedup but reduce efficiency.
Cache coherence and the MESI protocol
Shared-memory processors may cache separate copies of one block, so a write can stale the others. Coherence concerns one location's value across caches. Memory consistency concerns the ordering of accesses to different locations. Cache Memory: Mapping and Hit Ratio covers the cache basics behind this problem.
With snooping, every cache watches a shared bus and reacts to reads and writes. It is simple but limited by the bus. With a directory, metadata tracks which caches hold each block, which scales better for NUMA. Write-through updates memory on every write. Write-back keeps the change in cache, marks it dirty and writes it later.
MESI gives a block four states: Modified means dirty and the only valid copy; Exclusive means clean and the only copy; Shared means clean and possibly copied elsewhere; Invalid means unusable.
Trace a write-back, snoopy system. Memory starts with X = 5, and P1 and P2 have empty caches.
P1 reads X. It misses and loads 5. No other copy exists, so P1 becomes [E, 5]. P2 is empty and memory is 5.
P2 reads X. P1 snoops the read and changes E to S. P2 loads [S, 5]. P1 is [S, 5], and memory stays 5.
P1 writes X = 10. P1 broadcasts an invalidate. P2 changes S to I; P1 changes S to M and holds 10. Under write-back, memory still has 5.
P2 reads X again. Its Invalid copy misses. P1 supplies 10 and changes M to S. P2 loads [S, 10], and memory is updated to 10 during the transfer. Both caches now agree.
False sharing occurs when unrelated variables share a cache block and make it ping-pong between processors.
Hardware support for synchronisation
Disabling interrupts on one processor cannot provide system-wide mutual exclusion. Hardware supplies an atomic read-modify-write operation such as test-and-set, atomic exchange or compare-and-swap. A lock uses it to change a shared flag only when free. Atomicity across the shared interconnect prevents two processors from acquiring the lock together.
The traps that cost marks
Reading f as serial: f is parallelisable; 1 - f is serial. Check that S ≤ 1/(1 - f).
Expecting Nx speedup: the serial fraction set our ceiling at 5x, not 8x.
Calling multicore SIMD: independent core instruction streams make it MIMD.
Mixing coherence and consistency: one is about a location's value; the other is about access ordering.
Calling Omega non-blocking: its 12-switch cost instead of 64 crosspoints comes with blocking.
Confusing UMA and NUMA: UMA is uniform; NUMA has faster local and slower remote access.
How GATE and interviews test multiprocessors, plus the short version
GATE-style questions ask for Amdahl speedup or efficiency, Flynn classification, valid coherence transitions, and crossbar or Omega counts. The official GATE CS syllabus lists parallel processing and multiprocessor topics under Computer Organization and Architecture. Confirm the assessed scope in the current syllabus on the conducting institute's GATE portal.
Interviews ask you to explain coherence, expand MESI and walk through a write, compare shared memory with message passing, or define false sharing. Traced examples beat memorised definitions.
The short version: Flynn classifies, the interconnect and memory model decide how processors share, Amdahl bounds their help, and coherence keeps caches honest. Nail the two worked patterns and the rest becomes manageable.
For structured coverage across the full GATE CS syllabus, use GATE CS Exam Preparation, and for timed practice on numericals like these, the GATE Test Series.
