PARALLEL COMPUTING

Chapter Two: Principles of Parallel Algorithm Design

Introduction to algorithm development process
 What is an algorithm?
 What are common parallel algorithm development processes?
 Understand how algorithms are transformed into parallel algorithms
 Identify where parallelism exists in a problem

Apply parallel algorithm design techniques

 Decomposition techniques
 Mapping techniques
 Scheduling and Computation Templates
 Objective:-Moving from the sequential mindset thinking of "do A, then B" to
the parallel mindset of "do A and B simultaneously.“
Main objective is to design algorithms that:
 Maximize parallel execution
Introduction  Minimize communication overhead
 Balance workload across processors

• What is an algorithm? And algorithm development process?

• Algorithm is a step-by-step procedure or a set of instructions used to solve a
problem or perform a task.
• Algorithm development is a critical component of problem-solving using computers.
• A sequential algorithm is a recipe or a sequence of basic steps for solving a given
problem using a serial computers(processors).
• Similarly, a parallel algorithm is a recipe that tells us how to solve a given problem
using multiple processors simultaneously.
• However, specifying a parallel algorithm (Identify independent operations) involves
more than just specifying the steps.
• Principles of parallel algorithm design are conceptual strategies used to structure a
problem so that multiple processors can cooperate efficiently through
decomposition, concurrency identification, mapping, communication management,
and load balancing.
 Introduction
• What is Spot independent tasks/data?
• Understand the problem, break, spot identify, parallel execute …….
• Identifying parallelism is finding parts of a problem that can be executed
independently and simultaneously without interfering with each other.
 Independent tasks: Operations that don’t depend on the result of others.
 Independent data: Different chunks of data that can be processed separately.
 Example1:-Parallel Sorting (Conceptual Assembly)
 Let’s say we want to sort an array: [34h, 12h, 56h, 23h]
 Step 1: Load values into registers
 Processor 1: LOAD AX, 34h
 Processor 2: LOAD BX, 12h
 Processor 3: LOAD CX, 56h
 Processor 4: LOAD DX, 23h
 Introduction
 Example1:-Parallel Sorting (Conceptual Assembly)
 Step 2: Local comparisons (independent tasks)
 Processor 1: CMP AX, BX ; compare 34h and 12h
 Processor 2: CMP CX, DX ; compare 56h and 23h
 Step 3: Swap if needed
 Processor 1: JG SWAP1 ; if AX > BX, swap; SWAP1: XCHG AX, BX=12H, 43H
 Processor 2: JG SWAP2 ; if CX > DX, swap; SWAP2: XCHG CX, DX=23H, 56H
 Step 4: Merge results
 Now we have two sorted pairs: [12h, 34h] and [23h, 56h].
 Next, processors compare across pairs:
 Processor 1: CMP BX, DX ; compare 34h and 23h
 Processor 2: CMP AX, CX ; compare 12h and 56h
 Step 5: Final sorted array; After swaps and merges, we get: [12h, 23h, 34h, 56h]
 Introduction
 Example2:-Parallel Lung Cancer Detection from 10,000 GB Data
 It is Large Problem
 A medical research center has10,000 GB of CT scan images
 Thousands of patients
 Each scan contains many slices of lung images
 Detect possible lung cancer tumors using an AI / image analysis algorithm.
 This problem is too large for a single processor, so we design a parallel algorithm.
 Breaking larger problem??
 We divide the large dataset into smaller parts.
 10,000 GB dataset → split across processors. If we have 100 processors:
 Processor 1 → 100 GB
 Processor 2 → 100 GB
 Processor 3 → 100 GB...
 Processor 100 → 100 GB
 Introduction
 Example2:-Parallel Lung Cancer Detection from 10,000 GB Data
 Identify Independent Tasks???
 Each processor can analyze its assigned CT scan images independently.

 Independent tasks:

 Processor 1Detect nodules in patient group 1

 Processor 2Detect nodules in patient group 2

 Processor 3Detect nodules in patient group 3

 Processor 4Detect nodules in patient group 4

 All of these run simultaneously.

 Parallel execution:
 Time T0CPU1 → analyzing CT scans
 CPU2 → analyzing CT scans
 CPU3 → analyzing CT scans
 CPU4 → analyzing CT scans...
 CPU100 → analyzing CT scans
 Introduction
 Example 3: Detecting Cyberattacks from Massive Network Traffic
 The Large Problem
 A national network monitoring system collects:10 TB of network traffic logs per day
 Millions of packets per second
 Data from routers, servers, and firewalls
 Objective:- Detect cyberattacks such as DDoS attacks, Malware traffic Intrusion
attempts, Suspicious login behavior
 Decomposition (Breaking the Problem)???
 We divide the large network traffic dataset into smaller parts.

 10 TB traffic logs → split across processors. If we have 50 processors:

 Processor 1 → analyze traffic from Server Group A
 Processor 2 → analyze traffic from Server Group B
 Processor 3 → analyze traffic from Server Group C...
 Processor 50 → analyze traffic from Server Group Z
 Introduction
 Example 3: Detecting Cyberattacks from Massive Network Traffic
 Identify Independent Tasks???
 Each processor can analyze its assigned traffic logs independently.
 Independent tasks:
 Processor 1----Detect abnormal traffic spikes
 Processor 2----Detect suspicious IP addresses
 Processor 3----Identify malware signatures
 Processor 4----Detect brute-force login attempts
 All processors work at the same time.
 Another way to parallelize: We can also split tasks by type of cyberattack detection.
 Processor Group 1 → DDoS detection
 Processor Group 2 → Malware detection
 Processor Group 3 → Intrusion detection
 Processor Group 4 → Phishing traffic analysis
 These tasks also run simultaneously. This is called task decomposition.
 Algorithm development
• Developing efficient parallel algorithms requires different approaches than
sequential programming. A comprehensive guide to creating parallel algorithms:-
1. Having common understanding of fundamental design principles
 Know key decomposition strategies; So, consider
i. Granularity: Balance between fine-grained (many small tasks) and coarse-grained
(fewer large tasks)
ii. Load balancing: Ensure even work distribution
iii. Locality: Minimize data movement between processors
iv. Synchronization: Reduce contention and waiting
2. Grasp some common parallel algorithm patterns
 a) Is the subproblems are embarrassingly parallel or perfectly penalizable
 Perfectly parallelizable problems with no dependencies such as
 Processor 1: MUL AX, AX ; AX = 34h * 34h
 Processor 2: MUL BX, BX ; BX = 12h * 12h
 Algorithm development
2. Grasp some common parallel algorithm patterns
 b) is pipeline suitable for the problem?
 Data flows through sequence of processing stages
 Example: Image processing pipelines
 c) Is divide and conquer suitable for the problem?
 Recursive decomposition into subproblems
 Example: Parallel quicksort, merge sort
 Out of order, switching, register renaming……..
3. Having some basic development process in your mind
i. Problem & Parallelism Analysis
 Understand the problems, computations and Identify parallelizable components
 Analyze data dependencies or Identify independent operations
 Determine computation-to-communication ratio
 Algorithm development
3. Development Process
ii. Parallel Algorithm Design---how parallelism will be organized
 Select appropriate parallel pattern (MapReduce pattern, Pipeline pattern, Divide-and-Conquer)
 Choose decomposition strategy (Data, Task, Hybrid)
 Design communication scheme (Point-to-point, Broadcast, Reduction, All-to-all)
 Architecture-Aware Mapping--Mapping tasks to real hardware—(Vector, superscalar,
Multicore CPU, GPU, Cluster, Supercomputer)
 Memory Hierarchy Awareness—(Registers, Cache, RAM, Distributed memory)

iii. Implementation Considerations--converts the design into working code.

 Synchronization
 Overlap computation and communication
 Handle boundary conditions
 Algorithm development
3. Development Process
iv. Performance Evaluation (Testing)
 Is the parallel algorithm actually faster and scalable?
 We measure performance using key metrics:
 Execution Time--Sequential execution time, Parallel execution time
 Speedup--Speedup tells us how much faster the parallel algorithm is compared to
sequential execution.
 Efficiency---Efficiency measures how well processors are utilized.
 Scalability---How performance changes when processors increase.
 Overhead---Parallel overhead explains why speedup is not perfect.
 Find Sources of overhead:- Communication, Synchronization, Load imbalance,

Memory contention
 This stage answers three main questions:-
 Is the parallel algorithm actually effective? Where is performance being lost?
 What type of optimization is required?
 Algorithm development
3. Development Process
vi. Performance Optimization
 Load balancing adjustments (Static vs dynamic load balancing techniques)
 Communication reduction
 Synchronization minimization
 After implementing a parallel algorithm, performance is often limited by
three major problems:
 Uneven workload
 Excessive communication
 Too much synchronization
 With performance optimization we can achieve:
 Maximum processor utilization
 Minimal waiting time
 Efficient data movement
 Algorithm development
3. Development Process
vi. Performance Optimization
 Communication Reduction Techniques
 Increase Computation per Communication---increasing the amount of local

processing done by processors before they communicate with others, in order to

reduce communication overhead and improve parallel performance.
 Data Locality Optimization:- Keep data close to where computation occurs.

 Communication Overlap; Perform computation while communication happens. A

processor continues doing useful computation while data is being sent or received
instead of waiting for communication to finish.
 Synchronization Minimization
 Synchronization occurs when processors must wait for each other.
 Reduce Barriers----Use fewer synchronization points in the algorithm.
 Use Asynchronous Execution---Processors do not wait for each other.
 Lock-Free Algorithms----Processors update data without blocking each other.
 Parallel Algorithm Design
 Dividing a computation into smaller computations and assigning them
to different processors for parallel execution are the two key steps in
the design of parallel algorithms.
 The principles of parallel algorithm design encompass
various techniques and concepts aimed at effectively
utilizing parallel computing systems to solve computational
problems efficiently.
 Some key principles include
 Decomposition techniques,
 Mapping,
 Scheduling, and computation templates
 Decomposition Techniques
 The first step in developing a parallel algorithm is to decompose the problem
into tasks that are candidates for parallel execution.
 Decomposition refers to breaking down a computational problem into
smaller, manageable tasks that can be executed concurrently.
 Tasks are programmer-defined units of computation into which the main
computation is subdivided by means of decomposition.
 Task = indivisible sequential unit of computation
 Simultaneous execution of multiple tasks is the key to reducing the time
required to solve the entire problem.
 Tasks can be of arbitrary size, but once defined, they are regarded as
indivisible units of computation.
 The tasks into which a problem is decomposed may not all be of the same
size.
 Decomposition Techniques
Granularity of Task Decompositions
 The number of tasks into which a problem is decomposed determines its
granularity.
 Decomposition into a large number of tasks results in fine-grained
decomposition and that into a small number of tasks results in a coarse-
grained decomposition.
 Task decomposition is being done here
 Rows → Tasks (Task 1, Task 2, Task 3, Task 4)
 Columns → Data elements or subtasks (0, 1. n
 Gray cells → Active computation for that task
 White cells → No computation for that task
 (y) → Output for each task
 Each task produces results after finishing computation
 Possibly total computation or aggregated result-Far-right
vertical bar
 synchronization happens after large computation
blocks → typical of coarse-grained decomposition
 Decomposition Techniques
Decomposition is the process of breaking a large problem into smaller sub-problems (tasks).
Degree of Concurrency
 Degree of concurrency refers to the number of tasks that can execute
simultaneously.
 It is a measure of parallelism in a system.
 Depends on:
 Number of independent tasks, Independent tasks = maximum possible parallelism
 Task dependencies,
 Available processors/cores
 Since the number of tasks that can be executed in parallel may change over program
execution, the maximum degree of concurrency is the maximum number of tasks at
any point during execution.
 The average degree of concurrency is the average number of tasks that can be
processed in parallel over the execution of the program.
 Decomposition Techniques
Critical Path
 The critical path is the longest sequence of dependent tasks in a task graph
(parallel program).
 It represents the minimum time required to complete the entire computation,
even if unlimited processors are available.
 Tasks on the critical path cannot be executed in parallel because they depend
on each other.
Critical Path Length
 The critical path length is the total execution time of all tasks along the

critical path. Critical Path Length: The length of the longest path
Critical path? (sum of task durations) or (sum of task weights)
Critical path length? from the start to the end of the graph, representing
the minimum time required to complete all tasks.
 Critical Path Length

 What are the critical path lengths for the two task dependency graphs?
 If each task takes 10-time units, what is the shortest parallel execution time for each
decomposition?
 How many processors are needed in each case to achieve this minimum parallel execution
time? What is the maximum degree of concurrency?
 Critical Path Length
 How to calculate Critical Path Length (CPL)
 Start at source tasks (tasks with no incoming edges).
 Compute the longest path to each task by adding task execution times along the path.
 The critical path length is the longest path from start to end.
 The critical path is the sequence of tasks along that longest path.
 Possible paths from start to end (Task 7 is final):
 Task 4 → Task 6 → Task 7
 CPL = 10 (Task 4) + 9 (Task 6) + 8 (Task 7) = 27
 Task 3 → Task 6 → Task 7; CPL = 10 + 9 + 8 = 27
 Task 2 → Task 5 → Task 7; CPL = 10 + 6 + 8 = 24
 Task 1 → Task 5 → Task 7; CPL = 10 + 6 + 8 = 24
 Critical Path Length (CPL) = 27
 Critical Path = Task 4 → Task 6 → Task 7 (or Task 3 → Task 6 → Task 7, same length)
 Critical Path Length
 What CPL tells us
 Critical Path Length (CPL) = 27 means:
 The minimum total time required to complete all tasks is 27 units (in whatever time units
the task values represent).
 Even if we have unlimited processors to run tasks in parallel, we cannot finish faster than
27, because tasks on the critical path depend on each other sequentially.
 Tasks not on the critical path (like Task 1, Task 2, or Task 5 in this case) can be executed
in parallel without delaying the total completion.
 Tasks Task 3 and Task 4 can be executed independently at the start.
 Task 6 depends on Task 3 or Task 4, so it cannot start until one of them finishes.
 Task 7 depends on Task 6, so it starts after 6 is done.
 Maximum parallelism is possible for tasks not on the critical path (Task 1, Task 2, Task 5).
 CPL highlights tasks that must be carefully scheduled because they determine the overall
speed of execution. The longest sequence of dependent tasks from start to finish.
 Critical Path Length (CPL) is the total time to execute all tasks along the critical path.
 Task Dependency Graph (DAG
Directed Acyclic Graph)
 A Task Dependency Graph (DAG) is a graphical representation used in parallel
programs to show tasks and their dependencies.
 DAG is a fundamental concept in parallel programs used to represent how tasks
relate to each other.
 Nodes or vertices: Represent individual tasks or units of work or computations.
 Edges or arrows: Represent dependencies between tasks.
 An edge from task A to task B means task B cannot start until task A is
completed. (Task A → Task B)
 Acyclic → no loops (you cannot come back to the same task)
 Maximum Degree of Concurrency: The maximum number of tasks that can be
executed concurrently (in parallel) at any point
 Total Amount of Work: The sum of the weights (or durations) of all tasks in the
graph.
 Task Interaction Graphs
 Subtasks generally exchange data with others in a decomposition.
 Interaction==communications or exchange of data among tasks or CPUs

 The graph of tasks (nodes) and their interactions/data exchange (edges) is referred to
as a task interaction graph.

 Note that task interaction graphs represent data dependencies, whereas task
dependency graphs represent control dependencies.
 Characteristics of Tasks & Interaction

Characteristics of Tasks
• Once a problem has been decomposed into independent
tasks, the characteristics of these tasks critically impact
choice and performance of parallel algorithms.
• Relevant task characteristics include:
• Task generation--How tasks are created (e.g., dynamically at runtime,
statically before execution, or in bursts/irregular).
• Task sizes---the computational complexity or runtime duration of tasks
(e.g., short vs. long-running)
• Size of data associated with tasks---The volume of input/output data
each task processes or produces.
 Characteristics of Tasks & Interaction
• Characteristics of Task Interactions
• tasks often need to communicate or exchange data to complete a
computation. Task interactions are classified into:
• Static interactions
 Static interactions occur when tasks and their communication patterns are
known in advance (a-priori) before execution begins.
 These are relatively simpler to code into programs.
 Characteristics:
 Communication structure is fixed and predictable
 Tasks know who to communicate with and when
 Easier to design, implement, and optimize
 Example:-
 Matrix multiplication where each processor exchanges data in a predefined pattern
 Parallel array processing (fixed partitioning)
 Characteristics of Tasks & Interaction

• Dynamic interactions
• Dynamic interactions occur when communication patterns are

not known in advance.

• Characteristics:

• Tasks decide at runtime (during execution) such as when to

communicate and with which tasks
• Interaction patterns are data-dependent or event-driven
• More complex to implement
• Harder to debug and optimize
• Higher communication and synchronization overhead
• Difficult in message passing systems (e.g., unpredictable send/receive)
• Example:- Graph algorithms (e.g., shortest path such as Dijkstra’s
Algorithm, BFS)
 Characteristics of Tasks & Interaction
• Regular interactions or communications (P1P4, P2P3)
• There is a definite pattern (in the graph sense) to the interactions.
• These patterns can be exploited for efficient implementation.
• Key features include:-
• Fixed Communication Topology--Interactions follow a predefined graph

structure (e.g., ring, mesh, star, pipeline, grid or binary tree),

• Predictable Data Flow--Data dependencies are known in advance

• Synchronous or Deterministic Phases--Tasks progress in coordinated steps

• Efficient Implementations----Topology-aware optimizations

• Irregular interactions or communications

• Interactions lack well-defined topologies such as No Fixed Communication
Pattern, Decentralized Coordination's……
 Decomposition Techniques
 So how does one decompose a task into various subtasks?
 While there is no single recipe that works for all problems, we present a

set of commonly used techniques that apply to broad classes of

problems.

 Such Decomposition Techniques include:

 Recursive decomposition

 Data decomposition

 Task decomposition

 Exploratory decomposition

 Speculative decomposition

 Hybrid decomposition
 Recursive Decomposition
 Recursive decomposition is used to broken down into smaller subproblems
in a recursive manner, and these subproblems are solved simultaneously (in
parallel).
 The decomposition process continues until the subproblems are small
enough to be handled directly by the processors, at which point the solutions
are combined to obtain the final result. Until stopping condition is met
 Generally suited to problems that are solved using divide-and-conquer
algorithms, where the problem is recursively split into smaller problems,
solved independently, and then merged or combined.
 Is Decimal-to-Binary Conversion a Recursive Decomposition?
 A given problem is first decomposed into a set of subproblems.
 These sub-problems are recursively decomposed further until a desired
granularity is reached.
 Recursive Decomposition
 Characteristics of Recursive Decomposition
 Divide: The problem is recursively divided into smaller subproblems.

 Conquer: Each smaller subproblem is solved independently (in parallel).

 Combine: The solutions to the subproblems are combined to form the

final result.
 Recursive decomposition is widely used in algorithms like Merge-sort,
Quicksort, Binary Search, and Matrix Multiplication.
 The key idea is to split the problem into tasks that can be executed
concurrently, taking advantage of multiple processing units (cores or
processors).
 In this below quicksort example, once the list has been partitioned around
the pivot, each sub-list can be processed concurrently (i.e., each sub-list
represents an independent subtask). This can be repeated recursively.
 Recursive Decomposition

Where is does dependency in Quicksort?

In this case do we give the tasks to d/t processors? or
Where parallelism comes in?

recursive subproblems (left and right partitions) are independent and can be processed in parallel.
 Data Decomposition
• Data Decomposition is a technique used to divide a large dataset into
smaller, independent chunks that can be processed simultaneously by
multiple processors or threads.
• The goal is to distribute the workload evenly to maximize efficiency
and minimize communication overhead. (Measured with speedup,
efficiency, performance & latency)
• Here, the problem is divided based on the data involved.
• Different portions of data are processed simultaneously by multiple
processors, and the results are merged to obtain the final output. Steps
• Identify the data on which computations are performed.
• Partition this data across various tasks.
• Data can be partitioned in various ways – this critically impacts performance of a
parallel algorithm.
• Data can be input, output or intermediate for different computations
 Data Decomposition
• The Owner Computes Rule is a parallel programming strategy where:
• "Each processor (or thread) is responsible for computing the values of
the data it owns."
• This minimizes communication overhead by ensuring that the
processor that stores a data element is also the one that computes its
new value.
• Data Partitioning types
– Partition output data
– Partition input data
– Partition input + output data
– Partition intermediate data
 Task Decomposition
• Task decomposition is the process of breaking a large problem or
computation into smaller tasks (units of work) that can be executed
independently or concurrently in a parallel computing system.

• Task decomposition is the process of breaking down a large, complex, or

daunting task into smaller, manageable, and actionable sub-tasks.
• It is used in project management, AI development, and software
engineering to increase efficiency, improve focus, and reduce overwhelm
by treating tasks as hierarchical steps.
• Focus: “What work should be done?” (not the data)
• Divide program into different functions/tasks
• Each task performs a distinct operation
 Exploratory Decomposition
• Exploratory decomposition is used to divide problems into
independent subproblems that are explored simultaneously, often in
search of a solution.
• This approach is commonly used in search-based optimization, or
decision-making problems where multiple possibilities must be
evaluated to find the best outcome.
• It is used when solution space is unknown
• Used to explore deferent possibilities in parallel
• These problems typically involve the exploration (search) of a state space of
solutions.
• Explore all possible paths to find a solution, because you don’t know which
path works.
• Example:-Puzzle solving like maze, chess are applicable here
 Exploratory Decomposition
• Ex:-The 15-puzzle is a classic example of exploratory decomposition
in parallel programs.
• What is the 15-Puzzle?
• A 4×4 sliding puzzle with 15 numbered tiles and one empty space.
• Move tiles to reach a target arrangement (usually ascending order from 1 to
15). And make the empty space out of the order or at the end
• Why it Uses Exploratory Decomposition
• Exploratory decomposition is used when:
• Solution space is unknown
• You don’t know which sequence of moves leads to the solution aim
• Tasks explore multiple possibilities in parallel
• Identify possible moves from current state
• Move tiles into empty space (up, down, left, right)
Exploratory Decomposition

The aim of the puzzle is to come from state a to state d

Exploratory Decomposition
 Speculative Decomposition
• Speculative decomposition is a parallelization strategy where multiple
processors execute possible future computations before knowing whether
they are actually needed.
• Perform tasks before knowing if they are in need, Guess and compute in advance
• This approach is used to reduce latency by predicting likely execution paths
and precomputing results. If the prediction is correct, the result is used
immediately; if not, the work is discarded.
• In some applications, dependencies between tasks are not known a-priori.
For such applications, it is impossible to identify independent tasks.
• two approaches:
• conservative (pessimistic) approaches, which identify independent tasks only when they
are guaranteed to not have dependencies, and,
• optimistic approaches, which schedule tasks even when they may potentially be
erroneous.
 Speculative Decomposition
• Do multiple possible things before knowing which one is needed, then keep
the right one.
• Discrete Event Simulation:-
• DES is a method for simulating systems over time where state changes occur at discrete
events.
• Processors speculatively execute events in parallel
• Rollback if the guessed order was wrong
• Examples: Network packet arrival; Customer arrivals in a bank; Job scheduling in a CPU
• Consider your day today as a discrete event system you get up, get ready,
drive to work, work, eat lunch, work some more, drive back, eat dinner, and
sleep.
• Each of these events may be processed independently, however, in driving to work,
you might meet with an unfortunate accident and not get to work at all.
 Speculative Decomposition
• Dependencies between tasks are not known a-priori.
• – Impossible to identify independent tasks

• Two approaches

– Conservative approaches, which identify independent tasks

only when they are guaranteed to not have dependencies
• May yield little concurrency

– Optimistic approaches, which schedule tasks even when they

may potentially be inter-dependent
• Roll-back changes in case of an error
 Speculative Decomposition

It shows a simulation of a network of nodes

(A, B, C, D, E, F, G, H, I)
A and B → inputs
C, D, E, F, G, H → intermediate processing
nodes
I → final output
 Hybrid Decompositions
• Best of all approaches
• Example Matrix Multiplication
• data decomposition + task decomposition
• Hybrid decomposition in matrix multiplication:

• Splits matrices into blocks (data)

• Assigns computation + communication tasks (tasks)

• Each processor:

• Computes part of result

• Exchanges data

• Combines results
 Hybrid Decompositions
• Often, a mix of decomposition techniques is necessary for
decomposing a problem e.g.,
Hybrid Decompositions
 Mapping Techniques
 Mapping = assigning tasks (from decomposition) to processors
 After dividing a problem → we decide where each task runs

 Mapping refers to the process of assigning tasks or data segments to specific

processors or computing elements in a parallel computing system.
 The goal of mapping is to distribute the workload evenly across the available
resources, ensuring efficient utilization and minimizing communication
overhead.

 In general, the number of tasks in a decomposition exceeds the number of

processing elements available.
 For this reason, a parallel algorithm must also provide a mapping of tasks to
processes.
 Mapping Techniques
 In order to achieve a small execution time, the overheads of executing
the tasks in parallel must be minimized.

 For a given decomposition, there are two key sources of overhead.

 The time spent in inter-process interaction is one source of overhead.
 The time that some processes may spend being idle.

 Some processes can be idle even before the overall computation is

finished for a variety of reasons.
 Uneven load distribution may cause some processes to finish earlier
than others.
 Mapping Techniques
 Both interaction and idling are often a function of mapping.
 Therefore, a good mapping of tasks onto processors must strive to
achieve the twin objectives of :
 (1) reducing the amount of time processes spend in interacting with each
other
 (2) reducing the total amount of time some processes are idle while the
others are engaged in performing some tasks.

 These two objectives often conflict with each other.

 Assigning all work to one processor trivially minimizes
communication at the expense of significant idling.
 Mapping Techniques
• Why mapping is important in parallel computing?
• Mapping is not just about assigning tasks to processors; it is about optimizing
the overall performance of a parallel system.
• Load Balancing: Tasks should be evenly distributed among processors to ensure
that the computational workload is well balanced.
• Each processor gets a fair share of work

• Minimizing Communication Overhead: If tasks or data segments require

communication or synchronization, mapping can be designed to
minimize the amount of communication required between processors.
• Mapping should reduce data transfer between processors
• Tasks that frequently communicate should be placed:
• On the same processor, or

• On nearby processors
 Mapping Techniques
• Why mapping is important in parallel computing?
• Efficient Resource Utilization: Mapping should make efficient use
of available resources by considering factors such as processor
capabilities, memory access, and communication channels.
• Mapping should consider system resources such as:
• Processor speed and capability

• Memory hierarchy and access

• Network/communication links

• Use all available resources effectively and efficiently

 Locality of Reference As a result,

 Keep related data and tasks close together  Faster memory access
 A processor should work mostly on its own local data  Reduced communication cost
 Avoid frequent access to remote memory  Improved cache performance
 Overall Mapping…..
• Mapping in parallel computing refers to the process of assigning tasks to
processors in a way that optimizes system performance.
• Effective mapping ensures load balancing, where tasks are evenly distributed
to:-
• avoid idle processors;
• minimizes communication overhead by placing frequently interacting tasks close
to each other; and
• promotes efficient resource utilization by considering processor capabilities,
memory, and communication channels.
• Additionally, good mapping enhances locality of reference, leading to improved
cache performance, where frequently used data remains in fast memory,
reducing access time.
• Overall, proper mapping improves efficiency, scalability, and execution speed
of parallel programs.
 Schemes for Mapping
• Mapping techniques used in parallel algorithms can be broadly classified into three
categories: static, dynamic and hybrid mapping.
• The parallel programming paradigm and the characteristics of tasks and the
interactions among them determine whether a static or a dynamic or hybrid mapping
is more suitable.
• Static Mapping:- distribute the tasks among processors prior to the execution of the
algorithm. Assigns tasks to processors before execution (compile-time).
• For statically generated tasks, either static or dynamic mapping can be used.
• Tasks are assigned to resources (processors, cores, GPUs, etc.) before execution
begins, and this assignment remains fixed throughout the program's execution.
• The choice of a good mapping in this case depends on several factors, including the
knowledge of task sizes, the size of data associated with tasks, the characteristics of
inter-task interactions, and even the parallel programming paradigm.
• Algorithms that make use of static mapping are in general easier to design and program.
 Schemes for Mapping
• Characteristics
• Fixed assignment (no change at runtime)

• Based on prior knowledge of:

• Task size

• Dependencies

• Low runtime overhead

• Mapping decided before execution starts

• Disadvantages of static mapping
• Poor load balancing if tasks vary
• Cannot adapt to runtime changes
• Not suitable for dynamic or irregular problems
 Schemes for Mapping
• Dynamic Mapping: distribute the work among processors during the
execution of the algorithm.
• If tasks are generated dynamically, then they must be mapped dynamically
too.
• If task sizes are unknown, then a static mapping can potentially lead to
serious load-imbalances.

• Algorithms that require dynamic mapping are usually more complicated,

particularly in the message-passing programming paradigm.

• Runtime Assignment: In dynamic mapping, the assignment of tasks to

processors (or processing units) happens during the execution of the
algorithm, rather than before.
 Schemes for Mapping
• Characteristics of dynamic mapping
• Tasks assigned on demand
• Done via:-
• Work sharing (central queue)
• Work stealing (idle processors take tasks)
• Adapts to runtime behavior
• Disadvantages
• Higher runtime overhead
• More complex implementation
• Possible communication and synchronization cost
 Schemes for Mapping
• Dynamic mapping is particularly useful when task sizes or dependencies are
not known in advance, as it can dynamically distribute tasks to ensure a
more balanced workload across processors.
• When to Use Dynamic Mapping
• Irregular or Unpredictable Workloads: When the workload is not
uniform or predictable, dynamic mapping can help to avoid bottlenecks
and improve performance.
• Dynamically Generated Tasks: If tasks are generated during the
execution of the algorithm, dynamic mapping is necessary to assign them
to processors.
• Task Size Variation: When the sizes or computational requirements of
tasks vary significantly, dynamic mapping can help to ensure that
processors are not overloaded.
 Schemes for Static Mapping
• When we say “schemas for static mapping”, it basically means different
strategies or structured approaches for assigning tasks to processors in a
parallel system when all tasks are known beforehand.
• A schema is just a method, pattern, or plan for how you make the
assignment.
• Common schemas for static mapping
• These are the standard approaches (or schemas) people use:
• Data Partitioning Schema
• Divide the data among processors; each processor works on its data portion.
• Task Graph Partitioning Schema
• Divide the task dependency graph among processors; try to balance load and reduce
communication.
• Hybrid Schema
• Combine data partitioning and task graph partitioning for complex tasks.
 Schemes for Dynamic Mapping
• Schemes for Dynamic Mapping
• Dynamic mapping is sometimes also referred to as dynamic
load balancing, since load balancing is the primary motivation
for dynamic mapping.
• Dynamic mapping: Tasks are assigned to processors on-the-fly,
during program execution.
• Useful when:
• Tasks are generated at runtime
• Task execution times are unpredictable
• Load balance is hard to achieve statically
• Dynamic mapping schemes can be centralized or distributed or
hybrid dynamic mapping.
 Schemas for Dynamic Mapping
• Schemas (strategies) for dynamic mapping
• These are common methods to assign tasks dynamically:
1. Centralized Dynamic Mapping
• One central scheduler or master decides which processor gets the next task.
• How it works:
• Tasks are put in a central queue.

• Processors request tasks when they are idle.

• The scheduler assigns the next available task.

• Pros: Simple, easy to implement, good for small systems.

• Cons: Scheduler can become a bottleneck for large systems.
• Example: A master node in parallel web crawling distributing URLs.
 Schemas for Dynamic Mapping
2. Distributed Dynamic Mapping
 No single master; processors themselves decide how to pick tasks.
 How it works:
 Each processor maintains its local task queue.

 Idle processors can steal tasks from other processors (“work

stealing”).
 Pros: Avoids central bottleneck, scales well to large systems.
 Cons: More complex to implement.
 Example: Work-stealing in multithreaded task libraries (like OpenMP or
Intel TBB).
 Schemas for Dynamic Mapping
3. Hybrid Dynamic Mapping
 Combines centralized and distributed approaches.
 How it works:
 A central scheduler handles coarse task distribution.

 Within each processor or cluster, processors dynamically share

tasks among themselves.

 Pros: Balances simplicity and scalability.
 Example: Large-scale simulations in scientific computing.
 Mapping vs Scheduling
 Mapping is about deciding which processor will execute which
task.
 It’s a task-to-processor assignment.
 The focus is “Where should each task go?”
 When it happens:
 Static mapping: Done before execution
 Dynamic mapping: Done during execution
 Example:-You have 4 tasks (T1–T4) and 2 processors (P1, P2).
 A mapping could be:P1 → T1, T3 and P2 → T2, T4
 Mapping vs Scheduling
 Scheduling is about deciding the order and timing of tasks on a
processor.
 It’s when and in what sequence a processor will execute its tasks.
 The focus: is “In what order and at what time should each task
run?”
 When it happens:
 Usually at runtime, but static schedules are possible if task times are known.
 Example:-Processor P1 has tasks T1 and T3.
 A schedule could be:-Execute T3 first, then T1 Or T1 first, then T3
Thank you…!!!