Unit I — Introduction to Parallel Processing

Why Parallelism?

Session 01 • 2311CSC501J — Parallel Processing

What You'll Learn

Why the "free lunch" of faster chips ended
Concurrency vs parallelism vs multitasking
Latency vs throughput
Why not everything can be parallelized

"Concurrency is about dealing with lots of things at once. Parallelism is about doing lots of things at once."

— Rob Pike

The Free Lunch Is Over

For 40 years, code got faster for free

Moore's Law (1965): transistors per chip double every ~2 years
Dennard Scaling: smaller transistors → less power → higher clock speeds
Result: 1 MHz → 100 MHz → 1 GHz → 3 GHz. Same code, faster every year.

Then, around 2005, the wall

Dennard scaling broke. Push the clock higher and the chip becomes a tiny electric heater. Intel cancelled its 4 GHz Pentium. We hit the Power Wall.

Clock speed over time (simplified)

3+ GHz  |               ________________  ← flat since ~2005
        |             /
        |           /
        |         /
        |       /
  1 MHz |_____/
        +----------------------------------
        1975       2005            today
        "free lunch"    "the multicore era"

Moore's Law kept giving us more transistors — but we could no longer spend them on speed. So we spent them on more cores.

Example: The Same Code on Two Machines

One program. It adds up 100 million numbers, one at a time. We run it on a 2004 chip and on a 2024 chip.

	Pentium 4 (2004)	Modern laptop (2024)
Clock speed	3.4 GHz	~3.5–4 GHz (barely moved!)
Cores	1	8–16 (16× more)
Our one-at-a-time program	~2.0 s	~0.7 s
Speedup after 20 years	—	under 3×

Twenty years of engineering. Billions of rupees of R&D. Your single-threaded code got under 3× faster.

Compare: between 1985 and 2005, the same code would have gotten ~1000× faster over 20 years. That was the free lunch, and it is gone.

But: rewrite that same program to use all 16 cores, and it finishes in ~0.05 s. The performance is still there — it just moved from the hardware's job to yours. That transfer of responsibility is this entire course.

Every Device You Own Is Parallel

6–8

cores in your phone

8–16

cores in your laptop

1000s

cores in a GPU

10,000s

GPUs to train an AI model

The catch: a program not written for multiple cores uses only one of them.

A 16-core laptop running bad code = 1/16th of the machine. Parallel processing is the skill of using all of it.

Three Words People Confuse

Term	Meaning	Needs many cores?
Concurrency	Dealing with many things at once (structure)	No
Parallelism	Doing many things at once (execution)	Yes
Multitasking	OS switching between tasks on shared cores	No

The Chef Analogy (remember this)

1 chef, 1 dish

Sequential. No concurrency, no parallelism.

1 chef, 3 dishes, juggling

Concurrency. One core, but progress on many tasks by switching cleverly.

3 chefs, 3 dishes, at once

Parallelism. Real simultaneous work. Needs 3 chefs (3 cores).

Examples From Your Own Day

Scenario	What it is	Why
One canteen counter, long queue	Sequential	One server, one customer at a time, in order
Four canteen counters open	Parallelism	Four customers genuinely served at the same instant
Washing machine running while you study	Concurrency	You started it and walked away — you're not doing two things
Chatting on WhatsApp while a video downloads	Multitasking	OS interleaves them; on 1 core it just looks simultaneous
100 teachers correcting Q1 of 100 papers	Data parallelism	Same operation, different data, all at once
One cuts veg, one boils rice, one lays table	Task parallelism	Different operations, same time
Boiling water → then adding rice	Cannot parallelise	Step 2 needs step 1's result — a true dependency
Two people grab the last egg together	Race condition	Outcome depends on who got there first — not on your code

Notice: you already understand every idea in this course. What you're learning is the vocabulary for it — and how to make a machine do it without getting the wrong answer.

Quick Check: Call It Out

Concurrency, parallelism, multitasking — or none of them? Shout it out.

1. A single-core phone running Instagram, Spotify and Maps

Multitasking. One core, rapid switching. Nothing is truly simultaneous.

2. A GPU shading 2 million pixels for one frame

Parallelism (data parallelism). Thousands of cores, same operation.

3. A web server handling 500 users on one thread

Concurrency. It switches while waiting on the database. One core is enough.

4. Ten cooks making idli batter ferment in one hour

Impossible. The batter needs 8 hours no matter how many cooks watch it. Strictly sequential — adding workers changes nothing.

5. Four servers behind a load balancer

Parallelism — and note it's task-level, across machines, not cores. Same idea, bigger scale. This is how every app you use is deployed.

Watch: Concurrency Is Not Parallelism

Rob Pike (co-creator of Go) — the definitive mental model. Show the first ~10 minutes.

You can have concurrency without parallelism (one core switching fast). You generally can't get useful parallelism without concurrency — you must split the work first.

Latency vs Throughput

Latency

How long one task takes.

How fast is one car through the toll booth?

Throughput

How many tasks finish per unit time.

How many cars per minute overall?

Opening more toll booths doesn't make any single car faster (latency unchanged) — but far more cars get through per minute (throughput up).

Most parallelism is a throughput win, not a latency win. A GPU doesn't compute one pixel faster — it computes millions at once.

Worked Example: The Canteen Counter

One counter. It takes 2 minutes to serve one student. 120 students are waiting.

Counters	Time per student (latency)	Students per hour (throughput)	Queue cleared in
1	2 min	30	240 min
2	2 min (same)	60	120 min
4	2 min (same)	120	60 min
8	2 min (same)	240	30 min

Read the second column again. It never changes. No individual student is served faster. But the queue clears 8× sooner.

The same example, in a real system

An API takes 200 ms per request and handles 5 requests/sec. Add 3 more servers behind a load balancer → 20 requests/sec, but every single request still takes 200 ms.

This is why "add more servers" fixes a slow site under load but never fixes a slow page. Two completely different problems — and engineers confuse them every day.

Parallelism Already Runs Your Life

You do this…	…parallelism makes it possible
Google a query	Thousands of servers search different slices of the web at once, merge in ~0.5s
Play BGMI / GTA	The GPU shades millions of pixels in parallel, 60+ times a second
Ask ChatGPT	Trained across tens of thousands of GPUs running in parallel for months
Pay via UPI at peak	Millions of transactions processed concurrently across many machines
Check the weather	Supercomputers split the atmosphere into a grid, simulate each cell in parallel

Parallel computing isn't niche. It is the foundation of every system that operates at scale — which is every system you actually use.

Example in Depth: One Google Search

You type a query and press Enter. Roughly 0.4 seconds later you have 10 results, ranked, from an index of 100+ billion pages. How?

If it were sequential

One machine checks 100 billion pages, one after another. At a wildly optimistic 1 million pages/sec, that's 27 hours. Per search.

Google gets ~100,000 searches per second.

What actually happens

The index is split across thousands of machines. Your query is broadcast to all of them. Each searches only its own slice. Each returns its best few. A final machine merges and ranks.

          your query
               |
    +----------+----------+---- ... ----+
    |          |          |             |
 shard 1    shard 2    shard 3  ...  shard 1000     <-- all search AT THE SAME TIME
    |          |          |             |
    +----------+----------+---- ... ----+
               |
          merge + rank                              <-- this part is SEQUENTIAL
               |
          10 blue links

Three ideas from today, all in one example:

Data parallelism — same "search" operation, different slice of data.
Throughput, not latency — each shard isn't faster; there are just 1000 of them.
The sequential ceiling — that merge-and-rank step can't be split. Amdahl is standing right there.

Watch: CPU vs GPU, Visually

NVIDIA / Mythbusters — 1:30 that makes data parallelism unforgettable.

A CPU is a few very smart painters. A GPU is one giant machine that paints the entire picture in a single shot. Different tools for different jobs — we'll see why in Unit II.

Two Flavors of Parallelism

Data Parallelism

Same operation, lots of data.

"Add 1 to every element of a million-item array." Split the array; each core does its chunk. This is what GPUs are built for.

100 students each grade one page of the same exam.

Task Parallelism

Different operations, running together.

One thread loads the file, another compresses it, another uploads it. Different jobs, same time.

One person chops, another fries, another plates.

Most real systems mix both. We go deep in Unit III.

Example in Code: One Line Changes Everything

A first look — you don't have to understand the syntax yet. Just see how little changes.

Serial — uses 1 core

for (i = 0; i < n; i++) {
    c[i] = a[i] + b[i];
}

10 million elements → ~40 ms

Parallel — uses all 8 cores

#pragma omp parallel for
for (i = 0; i < n; i++) {
    c[i] = a[i] + b[i];
}

10 million elements → ~7 ms

One line. Roughly 6× faster on 8 cores. That's OpenMP, and you'll write it yourself in Session 03.

Two questions to hold onto:

Why 6× and not 8×? → overhead + the parts that don't split. (Session 08)
Why is this loop safe to split at all? → because c[i] never depends on c[i-1]. Change that and the same line gives you wrong answers. (Session 03)

The Catch: Not Everything Speeds Up

"Nine musicians can't play a four-minute song in thirty seconds."

Some work is inherently sequential — step 2 needs the result of step 1.
Every parallel program has parts that can't split: reading input, combining results, coordination.

Amdahl's Law (preview, Session 08): if 90% parallelizes but 10% can't, then even with infinite cores you can never beat 10×. That stubborn 10% is the ceiling.

And parallelism creates brand-new bugs

Race condition

Two cores update the same variable at once; result depends on luck.

Deadlock

Two cores each wait for the other, forever.

Load imbalance

One core gets 90% of the work while others sit idle.

Worked Example: The Ceiling Is Real

A job takes 10 hours. 1 hour is setup that cannot be split. The other 9 hours split perfectly.

Cores	Sequential part	Parallel part	Total	Speedup
1	1 hr	9 hrs	10 hrs	1×
2	1 hr	4.5 hrs	5.5 hrs	1.8×
10	1 hr	0.9 hr	1.9 hrs	5.3×
100	1 hr	0.09 hr	1.09 hrs	9.2×
1,000,000	1 hr	~0	~1 hr	9.99×
∞	1 hr	0	1 hr	10× — never more

Look at the jump from 100 cores to a million: 9.2× → 9.99×. You added 999,900 cores and gained almost nothing.

That single un-splittable hour caps you at 10× forever. The sequential fraction — not the core count — decides your fate. This is Amdahl's Law, and we make it a formula in Session 08.

Example: A Race Condition, Step by Step

Your bank balance is ₹1000. You and your friend withdraw ₹600 each, from two ATMs, at the exact same moment.

Time	ATM A	ATM B	Balance in DB
t1	reads balance → 1000		1000
t2		reads balance → 1000	1000
t3	1000 − 600 = 400 ✓		1000
t4		1000 − 600 = 400 ✓	1000
t5	writes 400		400
t6		writes 400	400

₹1200 dispensed. Balance says ₹400. The bank just lost ₹600.

Every individual step was correct. Both ATMs did valid arithmetic. The bug lives entirely in the timing.

Change the timing by a microsecond and it works fine. That's why these bugs are brutal: they vanish when you go looking for them. Run it 1000 times in testing, pass 1000 times, fail in production on a busy day.

Same bug, same shape, in Session 03 — when two threads both do sum += a[i].

A First Feel for Speedup

                time on 1 core
   Speedup  =  ---------------------
                time on N cores

100s on 1 core → 25s on 4 cores

= 4× speedup (perfect!)

100s on 1 core → 40s on 4 cores

= 2.5× (real life)

Perfect (linear) speedup = N× on N cores. It's the dream, rarely achieved — the sequential parts and coordination overhead eat into it. Session 08 turns this into real formulas.

Your Turn: Parallelise a Morning

In pairs, 5 minutes. Getting ready for college, alone, takes 55 minutes:

The task list

Boil water for tea — 5 min
Make tea (needs boiled water) — 2 min
Take a shower — 15 min
Iron your shirt — 8 min
Wear the shirt (needs ironing) — 2 min
Charge your phone — 20 min
Pack your bag — 3 min

Answer these

1. Which tasks have a dependency?
2. Which need you, and which run on their own?
3. Alone, what's the fastest possible time?
4. With a roommate helping, what's the fastest?
5. With ten roommates?

The three lessons hiding in Q5:

Ten roommates is no better than one or two — you run out of splittable work.
Your shower is 15 minutes no matter what. Nobody can shower for you — that's your sequential floor (Amdahl).
Boiling and charging need no one watching — start them first. Overlapping waiting with work is concurrency, and it's free.

Recap & What's Next

Key Takeaways

The free lunch is over — chips got wider (more cores), not faster (higher clock).
Concurrency = structure; parallelism = execution; multitasking = fast switching.
Parallelism mostly buys throughput, not lower latency.
Not everything parallelizes — sequential parts set a hard ceiling (Amdahl).
It trades the speed problem for coordination problems.

Homework

Explain to a non-technical friend why "more GHz" stopped being the way to get faster.
Find the core count of your own phone and laptop.
Come ready: "CPU with 8 strong cores vs GPU with 4000 weak cores — why does each exist?"

Next session: Flynn's Taxonomy & Memory Models

How we classify every parallel machine ever built.