Multiprocessor Fundamentals: Architecture, Speedup and Worked Examples

Adding four processors does not automatically divide execution time by four. Multiprocessors in COA: Concepts, Amdahl's Law and Cache Coherence Worked Examples connects interconnects, UMA and NUMA, Amdahl's theoretical limit, and a full MESI state trace. In the four-processor shared-memory machine P0 to P3, the decisive results are absolute execution time, the value returned after a coherent write, and the counter after two unprotected increments.

What a Multiprocessor System Actually Is

A multiprocessor system has two or more processing units that cooperate on work and share some combination of memory, I/O, and interconnection resources. The definition is architectural, not brand-specific.

Four related terms need to stay separate:

• A processor is a unit that executes instructions.

• A core is an execution engine within a processor chip.

• A multiprocessor has cooperating processing units, so a multicore chip can behave as one.

• A multicomputer has computers with separate memories that usually communicate by messages.

Multiprocessing divides work across processing units. Pipelining overlaps instruction stages inside a processor, as explained in Pipelining in Computer Architecture Explained.

Architecture Map: Memory, Control and Flynn Classification

For the full axis-by-axis method and a UMA-versus-NUMA latency calculation, use Multiprocessor Classification: Flynn Taxonomy, Memory Models and Exam-Style Worked Examples. The P0 to P3 machine is MIMD, shared-memory, and symmetric because its processors run independent instruction streams, address one memory space, and act as peers.

In a shared-memory system, processors address a common memory space. In a distributed-memory system, each node owns local memory and reaches another node's data through explicit communication. Tightly coupled systems share resources closely. Loosely coupled systems have more independent nodes and often use messages.

Control is another axis. In symmetric multiprocessing, processors are peers. In an asymmetric master-worker design, one processor coordinates the others.

Flynn's classification asks about instruction and data streams:

A general-purpose shared-memory multiprocessor is normally MIMD. Do not call every parallel machine SIMD merely because computations happen together.

Processors P0, P1, P2, and P3 each have a private L1 cache. The caches connect through a shared interconnect to shared main memory. Ask who owns memory, how another processor reaches data, whether instruction streams are independent, and where contention occurs. Hardware designs vary.

Fully Worked Speedup Example with Amdahl's Law

The earlier overview expresses this 20/80 workload as normalized speedup and its 5x theoretical ceiling. Assigning it T1 = 40 ms exposes the execution-time arithmetic: the fixed serial 8 ms never divides.

Let T1 = 40 ms, serial fraction 0.20, parallel fraction 0.80, and processor count N = 4.

First split the original work:

• Serial work = 0.20 × 40 = 8 ms

• Parallel work = 0.80 × 40 = 32 ms

Only the 32 ms part is divided among four processors:

1. T4 = 8 + (32/4) = 8 + 8 = 16 ms

2. S4 = T1/T4 = 40/16 = 2.5

3. E4 = S4/4 = 2.5/4 = 0.625 = 62.5%

The tempting answer 40/4 = 10 ms is wrong because it divides the fixed 8 ms serial part.

Now keep the same workload and vary N:

More processors reduce time here, but efficiency falls because the serial 8 ms stays fixed.

Shared Data and Cache Coherence: Follow One Write

At address 0x100, main memory, P0's cache, and P1's cache initially contain X=20. P0 then writes X=35.

In a simplified write-invalidate trace, P0's write invalidates P1's old X=20 copy. P1's next read must obtain X=35 through the coherent memory system. Protocol details vary, but all coherent systems must uphold the same coherence obligation.

Cache coherence keeps writes to the same location logically compatible across cached copies. Memory consistency instead constrains the order in which processors may observe memory operations. For prerequisite cache mechanics, revise Cache Memory: Mapping and Hit Ratio. The wider memory hierarchy does not remove the need for coherence.

Communication, Synchronisation and the Lost-Update Problem

Processors communicate through shared-memory operations or explicit messages in a distributed-memory design. In our machine, cache and memory requests use the shared interconnect. Concurrent demand can make it or a memory module a contention point.

Now let a shared counter C start at 100:

1. P0 reads 100 and computes 101.

2. Before P0's update is safely coordinated, P1 also reads 100 and computes 101.

3. P0 writes 101, and P1 writes 101.

4. The final value is 101, although two increments should produce 102.

This is a lost update. Mutual exclusion can protect the read-modify-write critical section, or an atomic increment can make it indivisible. A lock protects a critical section. At a barrier, every participating processor waits until all reach the same phase.

How Exams Turn These Ideas into Questions

Questions may ask you to classify an architecture, distinguish SIMD from MIMD, calculate speedup or efficiency, trace a stale copy, or identify a race or bottleneck. Try this self-check:

1. Classify the P0 to P3 shared-memory teaching machine by Flynn's scheme.

2. Recompute T4 from the 8 ms serial and 32 ms parallel parts.

3. State what P1 must eventually read after P0 writes X=35.

4. Explain why two increments can leave C at 101 rather than 102.

The answers are MIMD, 16 ms, 35, and an unprotected read-modify-write race. For a broader preparation route around this subject, use the GATE category.

Common Traps and How to Correct Them

• Assuming N processors guarantee speedup N: isolate the serial fraction, calculate actual time, and only then calculate speedup.

• Treating speedup and efficiency as the same number: use S = T1/TN and E = S/N. Here S4 is 2.5, while E4 is 62.5%.

• Assuming shared memory is automatically coherent: ask whether copies agree on X, then separately ask what operation order processors may observe.

• Calling every parallel machine SIMD: inspect its instruction streams and data streams. Also separate work divided across processors from instruction stages overlapped within one processor.

• Treating locks as only a performance detail: the C=100 example shows that synchronisation is required for correctness before its overhead matters.

Short Version and the Next Practice Step

Keep five points clear: architecture decides how processors share data; MIMD is usual for general-purpose multiprocessors; serial work limits speedup; coherence keeps copies of X compatible; and synchronisation prevents lost updates.

For a focused 15-minute revision, redraw the P0 to P3 machine from memory, redo the N=4 and N=8 calculations without looking, and narrate the X=20 to X=35 trace aloud. Then practise questions on Multiprocessors.

If you are preparing specifically for GATE, continue with GATE Guidance by Sanchit Sir.