Parallel Processing — Computer Science | CSS Notes

CSS Optional — Paper-II, Computer Organization & Architecture

1. Definition

Parallel processing is the use of multiple processing resources working simultaneously on different parts of a problem to reduce overall execution time, as opposed to a single processor working through the problem sequentially.

For the classification of architectures by instruction/data stream count (SISD/SIMD/MISD/MIMD), see System Level Architecture — this page instead focuses on how much speedup parallelism actually delivers, and where its limits lie.

2. Classification — Types of Parallelism

Bit-level parallelism — increasing processor word width (e.g., 8-bit → 16-bit → 32-bit → 64-bit) so more data is processed per instruction.
Instruction-level parallelism (ILP) — overlapping instruction execution within one core (pipelining, superscalar) — see the dedicated Instruction-Level Parallelism & Superscalar Processors page.
Data parallelism — the same operation applied simultaneously to different data elements (SIMD-style; e.g., adding a constant to every element of a large array at once).
Task/control parallelism — different operations executed simultaneously, typically on independent processors/cores (MIMD-style; e.g., one core rendering video while another handles audio).

3. Classification — Memory Organization for Parallel Systems

Shared-memory systems — all processors access a single common address space; simpler to program, but contention and cache coherence become bottlenecks as processor count grows.
Distributed-memory systems — each processor has its own private memory; processors communicate explicitly by passing messages, which scales further but adds communication overhead and programming complexity.

4. Measuring Parallel Performance

Speedup: $S = \frac{T_{serial}}{T_{parallel}}$ — how many times faster the parallel version runs.
Efficiency: $E = \frac{S}{N}$ (N = number of processors) — how well the added processors are actually being used; ideal efficiency is 1 (100%), realistically always less.
Amdahl's Law — assumes a fixed problem size; models the speedup ceiling imposed by the portion of a program that must run serially.

S = \frac{1}{(1 - p) + \frac{p}{N}}

where $p$ = the fraction of the program that is parallelizable and $N$ = number of processors

As N → ∞, S → 1 / (1 − p) — a hard ceiling set entirely by the serial fraction, no matter how many processors are added.

Gustafson's Law — assumes the problem size grows with the number of processors (a more realistic model for many real workloads); gives a much more optimistic, near-linear speedup:

S = N - \alpha(N - 1)

where $\alpha$ = the serial fraction of the (now larger) workload

🧮 Solved Numerical 1 — Amdahl's Law, Fixed N

Q: 80% of a program can be parallelized; the rest must run serially. Find the speedup achievable with 4 processors.

Given: $p = 0.8$ , $N = 4$

Solution:

\begin{aligned} S &= \frac{1}{(1 - 0.8) + \frac{0.8}{4}} \\ &= \frac{1}{0.2 + 0.2} \\ &= \frac{1}{0.4} \\ &= 2.5 \end{aligned}

Answer: 2.5× speedup — far short of the naive expectation of 4× from 4 processors, entirely because of the unparallelized 20%.

🧮 Solved Numerical 2 — Amdahl's Law, Speedup Limit

Q: Using the same program (80% parallelizable), what is the maximum speedup achievable no matter how many processors are used?

Solution:

S_{max} = \frac{1}{1 - p} = \frac{1}{1 - 0.8} = \frac{1}{0.2} = 5

Answer: 5× is the absolute ceiling — even with 1,000 processors, this program can never run faster than 5× its serial time, because of the fixed 20% serial portion. This is the single most important consequence of Amdahl's Law.

🧮 Solved Numerical 3 — Efficiency

Q: Using Numerical 1 (speedup 2.5 with 4 processors), find the parallel efficiency.

Solution:

E = \frac{S}{N} = \frac{2.5}{4} = 0.625 = 62.5\%

Answer: 62.5% efficiency — meaning the 4-processor system is, on average, delivering only about five-eighths of each processor's theoretical contribution.

🧮 Solved Numerical 4 — Gustafson's Law

Q: A workload has a serial fraction of 5% and runs on 8 processors, with the problem size scaled up to use all of them. Find the speedup under Gustafson's Law.

Given: $\alpha = 0.05$ , $N = 8$

Solution:

\begin{aligned} S &= N - \alpha(N - 1) \\ &= 8 - 0.05 \times 7 \\ &= 8 - 0.35 \\ &= 7.65 \end{aligned}

Answer: 7.65× speedup — close to the ideal linear 8×, illustrating why Gustafson's Law is far more optimistic than Amdahl's Law: it assumes the problem is scaled up rather than fixed while processors are simply added.

🎯 CSS Exam Angle

Amdahl's Law is the single highest-yield formula in this topic — expect a direct numerical (find speedup) and a conceptual question (why is there a ceiling?) in the same paper.
Always state explicitly that Amdahl's Law assumes a fixed problem size, while Gustafson's Law assumes the problem size scales with processor count — this contrast is a favourite "compare the two laws" short question.
Data parallelism vs task parallelism is a clean, quick short-answer pairing with concrete examples (array processing vs independent pipeline stages).

🔁 Repeated CSS Questions

State and explain Amdahl's Law with a numerical example. (Numerical — very frequently repeated)
Why does speedup not increase linearly with the number of processors?
Differentiate between Amdahl's Law and Gustafson's Law.
Differentiate between data parallelism and task parallelism with examples.
Differentiate between shared-memory and distributed-memory parallel systems.
Calculate the efficiency of a parallel system given its speedup and processor count. (Numerical)

⚠️ MCQ Traps

Amdahl's Law's speedup ceiling depends only on the serial fraction, not on the number of processors — adding processors beyond a certain point yields almost no benefit.
Efficiency is always ≤ 1 (100%) in practice; values above 1 ("superlinear speedup") can occur only due to secondary effects like better cache utilization with more processors, not from parallelism alone.
Gustafson's Law does not contradict Amdahl's Law — they model different scenarios (fixed vs scaled problem size), not competing "correct" answers.
Data parallelism = same operation, different data; task parallelism = different operations, possibly on the same or different data — the operation, not the data, is what distinguishes them.

📜 Past-Paper Questions & MCQs (CSS 2016–2026)

2017 · Paper-I · Q8(c) · 5 marks

Q. Write a short note on parallel processing and the use of pipelining for this purpose.

Ans.

Parallel processing means carrying out many operations at the same time to finish work faster (multiple processors, cores, or overlapped stages).
Pipelining achieves parallelism inside one processor by dividing instruction execution into stages (fetch, decode, execute, write-back) and overlapping different instructions, like an assembly line.
Speed-up: n instructions on a k-stage pipeline take k + n − 1 cycles instead of n·k, so the ideal speed-up approaches k.
Limits: hazards (data, control, structural) cause stalls. They are reduced by forwarding, branch prediction and good scheduling.

2024 · Paper-II · Q3(b) · 7 marks

Q. Explain the concept of parallelism in computer architecture. How does the internal structure of a microprocessor contribute to parallel processing capabilities?

Ans.

Parallelism is doing several things simultaneously. Levels: bit-level (wider words), instruction-level (pipelining, superscalar), thread-level (multi-core, hyper-threading) and data-level (SIMD, vector, GPU).
Microprocessor structures that support it:
- instruction pipeline with several stages
- multiple ALUs, FPUs and load/store units (superscalar)
- on-chip caches that feed the units quickly
- branch predictor and out-of-order execution logic
- multiple cores, each with its own registers and L1 cache, sharing L2/L3
- SIMD vector units (such as SSE and AVX)

2025 · Paper-II · Q2(c)(ii) · 5 marks

Q. Explain parallel processing and draw the pipeline processing for the instruction Ai × Bi + Ci.

Ans.

Parallel processing uses multiple processing elements to work on parts of a task at the same time.
Pipeline for Ai × Bi + Ci (three segments, each with a register stage):

Segment 1:  R1 ← Ai ,  R2 ← Bi            (input)
Segment 2:  R3 ← R1 × R2 ,  R4 ← Ci       (multiply)
Segment 3:  R5 ← R3 + R4                  (add)

While segment 3 adds for item i, segment 2 multiplies item i + 1 and segment 1 loads item i + 2. After the pipeline fills, one result is produced every clock cycle.