IFB 206
KOMPUTASI PARALEL DAN SISTEM
TERDISTRIBUSI
(parallel computing and distributed system)
~ Parallel Programming 03 ~
Lisa Kristiana PhD
Informatics – Spring 2026
• Mampu memahami pemrograman parallel
• Mampu mendiskripsikan aspek dalam
Learning pemrograman parallel
• Synchronization
Outcome • Race conditions
• Deadlocks
• Load balancing
• Communication overhead
What is Parallel Programming?
Parallel programming is a programming approach where:
• A problem is divided into multiple parts
• The parts are executed simultaneously
• On multiple processing units (cores, CPUs, GPUs, nodes)
Creating a parallel
program
Sub
problem,
You are thinking: a.k.a. task,
work to do
1. Identify work that
can be performed in
parallel Parallel
Threads
2. Partition work (and (worker)
also data associated
with the work)
3. Manage data access, Parallel program
communication and (communicating
synchronization threads
Identify the Problem
Large
Loops
Can the problem be Data
split into Decomposition
independent parts?
Independent
Tasks Can parts run at the
same time? Task
Decomposition
Big
Datasets
Data
Decomposition Data Parallelism (1)
pseudocode
• Array processing parallel for i = 1 to N do
• Matrix computation parallel for j = 1 to N do
C[i][j] = 0
for k = 1 to N do
C[i][j] = C[i][j] +
A[i][k] * B[k][j]
end for
end parallel for
end parallel for
Data
Decomposition Data Parallelism (2)
def matrix_multiply_parallel(A, B):
N = len(A)
Step 1: Initialize Result Matrix C = [[0] * N for _ in range(N)]
# Conceptual parallel loops
Step 2: Outer Loop (i) – Parallel for i in range(N): # parallel
Step 3: Second Loop (j) – Parallel for j in range(N): # parallel
Step 4: Inner Loop (k) – Sequential for k in range(N): # sequential
C[i][j] += A[i][k] * B[k][j]
return C
Conclusion to Data parallelism
Requirement Goals
Same operation Multiply + add
Different data Different i, j
Independent tasks Each C[i][j]
Parallelizable loops i, j
Each processor/thread can compute a different C[i][j] using the same code.
Thread 1 → computes C[0][0]
Thread 2 → computes C[0][1]
Thread 3 → computes C[1][0]
Thread 4 → computes C[1][1]
...etc
Data
Decomposition Task Parallelism (1)
Matrix
Operations
as Tasks
Task 1 → Matrix Addition
Task 2 → Matrix Multiplication
Task 3 → Matrix Transpose
Data
Decomposition Task Parallelism (2)
Sorting
All at once (run in parallel) ቐSearching
Logging
Result:
Task 1: Matrix Addition
Addition Result: [[6, 8], [10, 12]]
Task 3: Matrix Transpose
Transpose Result: [[1, 3], [2, 4]]
Task 2: Matrix Multiplication
Multiplication Result: [[19, 22], [43, 50]]
[Link]
Thread (1)
Thread (in Parallel Programming) is the smallest unit of execution
inside a program (process).
• A process can have multiple threads
• Threads share the same memory
• Each thread has its own execution path
Why Threads Are Used
• Run tasks concurrently
• Improve responsiveness
• Efficient for I/O-bound work
• Common in servers, GUIs, apps
Thread (2) Thread 1
• Task A runs at t1–t2
• Task A runs again at t2–t3
• Idle from t3–t4
Thread 2
• Idle at t1–t2
• Task B runs at t2–t3
• Task B continues at t3–t4
Thread 3
• Task C runs at t1–t2
Can you see the difference amongst • Idle at t2–t3
those threads? • Task C resumes at t3–t4
Parallelism
Calculation (1)
Strategy:
• Step 1 : Execute in parallel, time for
𝑁2
phase
𝑃
• Step 2 : execute serially, time for
phase 𝑁 2
Overall Performance:
2𝑛2
• Speed up ≤ 𝑛2
𝑝
+𝑛2
• Speed up ≤ 2
Parallelism
Calculation (2)
Strategy:
• Step 1 : Execute in parallel, time for
𝑁2
phase 𝑃
• Step 2 : execute serially, time for
𝑁2
phase 𝑃 + 𝑃2
Overall Performance:
2𝑛2
• Speed up ≤ 2𝑛2
+𝑃
𝑝
• Speed up ≤ 2
Amdahl's law
Cray – 2 The
Supercomputer
• Located at ETH Zurich, Switzerland
• Developer: Cray Research
• Introduced: 1985
• Peak performance: 1.9 gigaflops
• Memory capacity: Up to 512 megabytes
• Cooling system: Liquid immersion
(Fluorinert dielectric fluid)
From the archives: the supercomputer Cray at ETH Zurich –
Department of Computer Science
Summit
Supercomputer
• Summit was one of the world’s most
powerful supercomputers, developed by
IBM and installed at Oak Ridge National
Laboratory in Tennessee, USA.
• Peak Performance: ~200 petaflops (200
quadrillion calculations per second)
• Architecture: Hybrid CPU + GPU
• CPUs: IBM POWER9
• GPUs: 6 × NVIDIA Tesla V100 per node (from
NVIDIA)
• Total Nodes: 4,608
• Memory: ~2.8 PB
• Storage: ~250 PB
Answer :
Based on Amdahl’s Law
• S = the fraction of the program that is strictly serial
27,648 GPUs × 5,376 ALUs/GPU = 148,635,648 ALUs (cannot be parallelized)
• 1 − S = the fraction that can be parallelized
Means: ~148 million arithmetic operations at the • N = number of processors
same time • S(N) = overall speedup when using N processors
If, N = 148,635,648, then
Final answer,
= 1 1
𝑆 = 0.00100000672 = 0.001 = 1000
=
= 𝑆 ≈ 1000 ×
Even with 148 million parallel ALUs, the speedup is limited to ~1000× , WHY?
Danke