CSC 334 – Parallel and Distributed Computing

Instructor: Dr. M. Hasan Jamal

Lecture# 02: Types of Parallelism

1
Types of Parallelism
• Implicit Parallelism: The compiler, runtime, or system automatically identifies
and manages parallelism without requiring the programmer to explicitly define it.

• Explicit Parallelism: The programmer directly specifies the parallelism, defining

threads, synchronization, and communication.

2
Explicit Parallelism
• A programming approach where the developer explicitly instructs the system
where and how to parallelize operations using dedicated language features like
operators, function calls, or directives.

• Since multiple threads are executing concurrently, explicit synchronization

mechanisms like barrier or locks are often required to ensure data consistency.

• Examples of explicit parallelism techniques

• Data parallelism
• Task parallelism
• Loop-level parallelism
• Thread-based parallelism 3
Data Parallelism
• Applying the same operation to large datasets in parallel, often using loops to
iterate through data chunks. The same code segment runs concurrently on each
processor, but each processor is assigned its own part of the data to work on.
• For loops define the parallelism.
• The iterations must be independent of each other.
• Data parallelism is called "fine grain parallelism" because the computational work is
spread into many small subtasks.

4
Task Parallelism
• As the opposite of data parallelism, task parallelism breaks down a problem
into independent tasks that can be executed concurrently on different
processors. Different operations are performed on different parts of the data.
• Task parallelism is called "coarse grain" parallelism because the computational work
is spread into just a few subtasks.
• More code is run in parallel because the parallelism is implemented at a higher level
than in data parallelism.
• Easier to implement and has less overhead than data parallelism.

Example: an image (like color channels) are

processed in parallel using separate threads,
effectively treating each color channel as a
separate task. 5
Loop-Level Parallelism
• Parallelizing operations within loops where each iteration can be executed
independently

• Loop-level parallelism is a specific technique often used to achieve data

parallelism, but data parallelism encompasses a wider range of strategies.

• Example:
#pragma omp parallel for
for (int i = 0; i < n; i++)
a[i] = b[i] + c[i];

6
Thread-Level Parallelism
• Deals with the execution of multiple threads within a program to execute
different parts of the code simultaneously. The programmer explicitly creates
and manages threads that run concurrently.

• Thread-level parallelism is a mechanism for achieving task parallelism by

managing threads, but not all task parallelism requires explicit thread
management.

• Example: A web server using multiple threads to handle incoming requests

simultaneously, where each thread processes a single request independently.

7
Implicit Parallelism
• The compiler, runtime, or system automatically identifies and manages
parallelism without requiring the programmer to explicitly define it.

• Examples of implicit parallelism techniques

• Instruction-Level Parallelism (ILP)
• Compiler-Driven Parallelism

8
Instruction Level Parallelism
• Instruction Level Parallelism (ILP) is a set of techniques for executing multiple
instructions at the same time within the same CPU core (Note: ILP has
nothing to do with multicore)

• Basic Idea: Execute several instructions in parallel; i.e., overlap the execution
of instructions to run programs faster (“to improve performance”)

• The Problem: A CPU core has lots of circuitry, and at any given time, most of it
is idle, which is wasteful.

• The solution: Have different parts of the CPU core work on different operations
at the same time. If the CPU core has the ability to work on 10 operations at a
time, then the program can, in principle, run as much as 10 times as fast
9
(although in practice, not quite so much).
Examples of Instruction Level Parallelism
• Pipelining: Start performing an operation on one piece of data while finishing
the same operation on another piece of data – perform different stages of the
same INSTRUCTION on different sets of operands at the same time (like an
assembly line).

• Superscalar: Perform multiple instructions at the same time (for example,

simultaneously perform an add, a multiply and a load)

• Super-pipelining: A combination of superscalar and pipelining – perform

multiple pipelined instructions at the same time.

• Vectorization: Load multiple pieces of data into special registers and perform
the same instruction on all of them at the same time.
10
5 Stages in Executing a MIPS instruction
• IF: Instruction Fetch, Increment Program Counter

• ID: Instruction Decode, Read Registers

• EX: Execution
• Mem-ref: Calculate Address
• Arithmetic/logical: Perform Operation

• MEM:
• Load: Read Data from Memory
• Store: Write Data to Memory

• WB: 11
• Write Data Back to Register
Instruction Execution

12
Instruction Execution

13
Pipelining Execution

14
Superscalar Execution

15
Super-pipelining: Superscalar + Pipeline

16
Vectorization
• A vector register is a register that’s made
up of many individual registers. that
simultaneously perform the same
operation on multiple sets of operands,
producing multiple results. In a sense,
vectors are like operation-specific cache.

• A vector instruction is an instruction that for(i=0; i <=MAX; i++)

performs the same operation Z[i] = X[i] + Y[i];
simultaneously on all individual registers
of a vector register.

17
What determines the degree of ILP?
• Dependencies: A dependence indicates what program components
(statements, loop iterations, etc.) may be executed ignoring the sequence of
events specified by the programmer without changing the output. Program
components that are not dependent on each other can be executed in parallel.
Dependencies are a property of programs.

• Hazards: When two instructions that have one or more dependences between
them occur close enough that changing the instruction order will change the
outcome of the program.

• Not all dependencies lead to hazards!

• The presence of a dependence indicates the potential for a hazard, but the
existence of an actual hazard and the length of any stall are properties of the 18
pipeline
Types of Dependencies
• Data Dependence: Flow Dependence (True Dependence)
• RAW: Read-After-Write

• Named Dependencies:
• WAR: Write-After-Read (Anti-Dependance)
• WAW: Write-After-Write (Output Dependence)

• Control Dependence:
• When following instructions depend on the outcome of a previous branch/jump

19
What is Dependency Analysis?
• Dependency analysis describes of how different parts of a program affect one
another, and how various parts require other parts in order to operate correctly.

• Dependency analysis is one of the major roles of a modern compilers

• A data dependency governs how different pieces of data affect each other.

• A control dependency governs how different sequences of instructions affect

each other.

20
Data Dependence and Hazards
• If two instructions are data dependent, they cannot execute simultaneously, be
completely overlapped or execute in out-of-order

• Instruction S2 is data dependent (aka true dependence) on Instruction S1

S1: X = A + B
S1 S2
S2: C = X + 1

• If data dependence caused a hazard in pipeline, then the hazard is called a

Read After Write (RAW) hazard

21
Loop-Carried Dependence
• A type of data dependence that occurs when the output of a loop iteration
depends on the output of a previous iteration
FOR i = 2 to MAX
a[i] = a[i-1] + b[i]
END FOR

• There is no way to execute iteration i until after iteration i-1 has completed, so
this loop can’t be parallelized.

22
Why do we care?
• Loops are very common in many programs.
• Also, it’s easier to optimize loops than more arbitrary sequences of
instructions: when a program does the same thing over and over, it’s easier to
predict what’s likely to happen next.

• Loops are the favorite control structures of High-Performance Computing. Both

hardware vendors and compiler writers build for optimizing loop performance
using instruction-level parallelism (superscalar, pipelining, and vectorization).

• Loop carried dependencies affect whether a loop can be parallelized, and

how much.

23
ILP and Data Dependencies, Hazards
• HW/SW must preserve program order: code must give the same results as if
instructions were executed sequentially in original order of the source program

• Importance of the data dependencies:

1. Indicates the possibility of a hazard
2. Determines order in which results must be calculated
3. Sets an upper bound on how much parallelism can possibly be exploited

• Goal: Exploit parallelism by preserving program order only where it affects the
outcome of the program

24
Named Dependence and Hazards
• Name Dependence: When two instructions use the same variable name (register or
memory location), but there is no flow of data between them associated with that
variable name.

• Anti-Dependence: Instruction S2 writes operand before Instruction S1 reads it

S1: A = X + B
S1 S2
S2: X = C + D
• Output-Dependence: Instruction S2 writes operand before Instruction S1 writes it
S1: X = A + B
... S1 S2
S2: X = C + D
• If anti-dependence caused a hazard in pipeline, then the hazard is called a Write
After Read (WAR) hazard
25
• If output-dependence caused a hazard in pipeline, then the hazard is called a
Write After Write (WAW) hazard
Control Dependencies
• Every program has a well-defined flow of control that moves from instruction to
instruction. Every instruction is control dependent on some set of branches (if
condition, switch case, function calls, I/O), and, in general, these control
dependencies must be preserved to preserve program order.
IF p1 THEN
S1
IF p2 THEN
S2
• S1 is control dependent on p1, and S2 is control dependent on p2 but not on p1.

• Control dependence need not be preserved

• willing to execute instructions that should not have been executed, thereby violating the
control dependences, if can do so without affecting correctness of the program
26
• Speculative Execution
Speculation
• Greater ILP: Overcome control dependence by hardware speculating on
outcome of branches and executing program as if guesses were correct
• Speculation  fetch, issue, and execute instructions as if branch predictions were
always correct
• Dynamic scheduling  only fetches and issues instructions

• Essentially a data flow execution model: Operations execute as soon as their

operands are available

• Speculation is rampant in modern superscalars

27
Speculation
• Different predictors
• Branch Prediction
• Value Prediction
• Prefetching (memory access pattern prediction)

• Inefficient
• Predictions can go wrong
• Need to flush out wrongly predicted data
• Wrong predictions consume power

28
Limits to Pipelining
• Hazards prevent next instruction from executing during its designated clock
cycle

• Structural hazards: attempt to use the same hardware to do two different

things at once

• Data hazards: Instruction depends on result of prior instruction still in the

pipeline

• Control hazards: Caused by delay between the fetching of instructions and

decisions about changes in control flow (branches and jumps).

29
Why Does Order Matter?
• Dependencies can affect whether we can execute a particular part of the
program in parallel.

• If we cannot execute that part of the program in parallel, then it’ll be SLOW.

30
Dependencies in Loops
• Dependencies in loops are easy to understand if loops are unrolled. Now the
dependences are between statement “instances”
FOR i = 1 to n
S1 a[i] = b[i] + 1
S2 c[i] = a[i] + 2

Iteration: 1 2 3 4 ...

Instances of S1: S1 S1 S1 S1

...

31
Instances of S2: S2 S2 S2 S2
Dependencies in Loops
• A little more complex example

FOR i = 1 to n
S1 a[i] = b[i] + 1
S2 c[i] = a[i-1] + 2

Iteration: 1 2 3 4 ...

Instances of S1: S1 S1 S1 S1

...

32
Instances of S2: S2 S2 S2 S2
Dependencies in Loops
• Even more complex example

FOR i = 1 to n
S1 a = b[i] + 1
S2 c[i] = a + 2

Iteration: 1 2 3 4 ...

Instances of S1: S1 S1 S1 S1

...

33
Instances of S2: S2 S2 S2 S2
Optimizing with Dependencies
• It is valid to parallelize/vectorize a loop if no dependences cross its iteration
boundaries:
FOR i = 1 to n
S1 a[i] = b[i] + 1
S2 c[i] = a[i] + 2

1 2 3 4 ...

S1 S1 S1 S1

...

S2 S2 S2 S2 34
Loop or Branch Dependency?
• Is this a loop carried dependency or a branch dependency?

FOR i = 1 to MAX
IF (x[i] != 0)
y[i] = 1.0/x[i]
END IF
END FOR

35
Compiler-Driven Parallelism
• Tricks that compilers play for automatic parallelization
• Scalar optimizations
• Loop-level optimizations

36
Scalar Optimizations
• Copy Propagation
• Constant Folding
• Dead Code Removal
• Strength Reduction
• Common Subexpression Elimination
• Variable Renaming
• Loop Optimizations

• Not every compiler does all these, so it sometimes can be worth doing these
by hands
37
Copy Propagation

Before
x = y
z = 1 + x

Has data dependency

Compile

After
x = y
z = 1 + y
38
No data dependency
Constant Folding
Before After

add = 100 sum = 300

aug = 200
sum = add + aug

• Notice that sum is actually the sum of two constants, so the compiler can
precalculate it, eliminating the addition that otherwise would be performed at
runtime.

39
Dead Code Removal
Before After

var = 5 var = 5
PRINT *, var PRINT *, var
STOP STOP
PRINT *, var * 2

• Since the last statement never executes, the compiler can eliminate it.

40
Strength Reduction
Before After

x = y^2.0 x = y * y
a = c / 2.0 a = c * 0.5

• Raising one value to the power of another, or dividing, is more expensive than
multiplying. If the compiler can tell that the power is a small integer, or that the
denominator is a constant, it’ll use multiplication instead.

41
Common Subexpression Elimination
Before After

d = c * (a / b) adivb = a / b
e = (a / b) * 2.0 d = c * adivb
e = adivb * 2.0

• The subexpression (a / b) occurs in both assignment statements, so

there’s no point in calculating it twice.

• This is typically only worth doing if the common subexpression is expensive to

calculate.
42
Variable Renaming
Before After

x = y * z x0 = y * z
q = r + x * 2.0 q = r + x0 * 2
x = a + b x = a + b

• The original code has output dependency, while the new code doesn’t – but
the final value of x is still correct.

43
Loop Optimizations
• Hoisting Loop Invariant Code
• Unswitching
• Iteration Peeling
• Index Set Splitting
• Loop Interchange
• Unrolling
• Loop Fusion
• Loop Fission
• Inlining

• Not every compiler does all these, so it sometimes can be worth doing these 44
by hands
Hoisting Loop Invariant Code
• The code that does not change inside the loop is known as loop invariant. It
doesn’t need to be calculated over and over.

Before After

FOR i = 1 to n temp = c * d
a[i] = b[i] + c * d FOR i = 1 to n
e = g(n) a[i] = b[i] + temp
END FOR END FOR
e = g(n)

45
Unswitching
FOR i = 1 to n
FOR j = 2 to n The condition is
IF (t(i) > 0) THEN j-independent
a[i][j] = a[i][j] * t(i) + b(j)
ELSE
a[i][j] = 0.0
END IF
END FOR Before
END FOR
FOR i = 1 to n
IF (t(i) > 0) THEN
FOR j = 2 to n So, it can migrate
a[i][j] = a[i][j] * t(i) + b(j) outside the j loop
END FOR
ELSE
FOR j = 2 to n
a[i][j] = 0.0 46
END FOR
END IF After
END FOR
Iteration Peeling
FOR i = 1 to n
IF ((i == 1) OR (i == n)) THEN
x[i] = y[i]
ELSE
Before
x[i] = y[I + 1] + y[i - 1]
END IF
END FOR

• We can eliminate the IF by peeling the weird iterations.

x(1) = y(1)
FOR i = 2 to n-1 After
x[i] = y[I + 1] + y[i - 1]
END FOR
x(n) = y(n)
47
Index Set Splitting
FOR i = 1 to n
a[i] = b[i] + c[i]
IF ((i > 10) THEN
d[i] = a[i] + b[i – 10]
Before
END IF
END FOR

FOR i = 1 to 10
a[i] = b[i] + c[i]
END FOR
FOR i = 11 to n After
a[i] = b[i] + c[i]
d[i] = a[i] + b[i - 10]
END FOR
48
• Note that this is a generalization of peeling.
Loop Interchange
Before After

FOR i = 1 to nj FOR i = 1 to ni
FOR j = 1 to ni FOR j = 1 to nj
a[i][j] = b[i][j] a[i][j] = b[i][j]
END FOR END FOR
END FOR END FOR

• The array elements a[i][j] and a[i][j+1] are near each other in memory,
while a[i+1][j] may be far, so it makes sense to make the i loop be the
outer loop.

• This technique facilitates efficient exploitation of the phenomenon of locality 49

of reference.
Unrolling
FOR i = 1 to n
a[i] = a[i] + b[i]
END FOR Before

FOR i = 1, n, 4
a[i] = a[i] + b[i]
a[i+1] = a[i+1] + b[i+1]
a[i+2] = a[i+2] + b[i+2] After
a[i+3] = a[i+3] + b[i+3]
END FOR

• You generally shouldn’t unroll by hand. 50

Why Do Compilers Unroll?
• A loop with a lot of operations gets better performance (up to some point),
especially if there are lots of arithmetic operations but few main memory loads
and stores.

• Unrolling creates multiple operations that typically load from the same, or
adjacent, cache lines.

• So, an unrolled loop has more operations without increasing the memory
accesses by much.

• Also, unrolling decreases the number of comparisons on the loop counter

variable, and the number of branches to the top of the loop. 51
Loop Fusion
FOR i = 1 to n
a[i] = b[i] + 1
END FOR

FOR i = 1 to n
c[i] = a[i] /2 Before
END FOR

FOR i = 1 to n
d[i] = 1 / c[i]
END FOR

FOR i = 1, n
a[i] = b[i] + 1
c[i] = a[i] / 2 After
d[i] = 1 / c[i]
END FOR
52
• As with unrolling, this has fewer branches. It also has fewer total memory
references.
Loop Fission
FOR i = 1, n
a[i] = b[i] + 1
c[i] = a[i] / 2 Before
d[i] = 1 / c[i]
END FOR
FOR i = 1 to n
a[i] = b[i] + 1
END FOR

FOR i = 1 to n
c[i] = a[i] /2
END FOR After

FOR i = 1 to n
d[i] = 1 / c[i]
END FOR 53

• Fission reduces the cache footprint and the number of operations per iteration.
To Fuse or to Fizz?
• The question of when to perform fusion versus when to perform fission, like
many optimization questions, is highly dependent on the application, the
platform and a lot of other issues that get very, very complicated.

• Compilers don’t always make the right choices.

• That’s why it’s important to examine the actual behavior of the executable.

54
Inlining
Before After

FOR i = 1 to n FOR i = 1 to n
a[i] = func(i) a[i] = i * 3
END FOR END FOR

int func(x)
func = x * 3
RETURN func

• When a function or subroutine is inlined, its contents are transferred directly

into the calling routine, eliminating the overhead of making the call.
55
Task of the Compiler
• It transform program to remove dependencies

• Use dependence to reorganize computation for parallelism and locality.

• However, manual transformation by hand can sometimes be more useful.

56
Transforming Programs: Renaming
S1: A = X + B
S2: X = Y + 1
S3: C = X + B
S4: X = Z + B
S5: D = X + 1

S1: A = X + B
S2: X1 = Y + 1
S3: C = X1 + B
S4: X2 = Z + B 57
S5: D = X2 + 1
Transform Programs: Scalar Expansion
FOR i = 1 to n S1 S1 S1 S1
S1 a = b[i] + 1
S2 c[i] = a + d[i] ...
END FOR
S2 S2 S2 S2

FOR i = 1 to n S1 S1 S1 S1
S1 a1[i] = b[i] + 1
S2 c[i] = a1[i] + d[i] ...
END FOR 58
a = a1[n] S2 S2 S2 S2
Transform Programs: Scalar Expansion
• The rule is simple: it is valid to expand a scalar if it is always assigned before
it is used within the body of the loop and if either
• its final value at the end of the loop is known, or
• it is never used after the loop.

59
Final Message:
• Implicit parallelism is becoming increasingly valuable with the advancement in
hardware and compilers capabilities.

• Try to get maximum of what a compiler can do for you automatically (LEARN
compiler flags/options/directives). But keep ensured whether your BULL (the
compiler) is really pulling your cart FAST (not just dancing), even that to the
RIGHT direction.

• Although a number of compiler/coding techniques have been discussed – but

profiling and analyzing the benefit of a specific technique is a MUST TO DO.

• While optimizing the code, use profiling to find out HOT SPOTS or Bottlenecks
and then focus on those, one by one, also ensuring correctness. The 10-90 rule 60
often works. Algorithm transformation could be considered, also.