HPC by Omieeee.

HIGH PERFORMANCE COMPUTING

Unit I – Introduction to Parallel Computing

Introduction to Parallel Computing:
Motivating Parallelism,
Modern Processor:
Stored-program computer architecture, General-purpose Cache-based
Microprocessor architecture.
Parallel Programming Platforms:
Implicit Parallelism, Dichotomy of Parallel Computing Platforms, Physical
Organization of Parallel Platforms, Communication Costs in Parallel Machines.
Levels of Parallelism
Models:
SIMD, MIMD, SIMT, SPMD, Data Flow Models, Demand-driven Computation.
Architectures:
N-wide superscalar architectures, multi-core, multi-threaded.
Exemplar/Case Study:
Case study: Multi-core System
Mapping of Course Outcomes for Unit I:
CO1

Unit II – Parallel Algorithm Design

Global System for Mobile Communications (GSM) architecture,
Mobile Station, Base Station System, Switching subsystem, Security, Data
Services, HSCSD, GPRS – GPRS system and protocol architecture 2.3 UTRAN,
UMTS core network; Improvements on Core Network, 802.11 Architecture
802.11a, 802.11b standard.
Exemplar/Case Studies:
IPoC: A New Core Networking Protocol for 5G Networks.

1|Page
HPC by Omieeee.o

Unit I – Introduction to Parallel Computing

Que.1) Explain the impact of Memory Latency & Memory Bandwidth on

system performance. [6]
Ans :
Impact of Memory Latency & Memory Bandwidth on System Performance
In High Performance Computing (HPC), overall performance depends not only
on processor speed but also on memory system performance. Two key factors
are Memory Latency and Memory Bandwidth.

Memory Latency
Memory latency is the time delay between a memory request and the start of
data transfer from memory to processor.
Impact on HPC Performance:
• High latency increases processor stall time.
• Affects performance of serial and irregular applications (e.g., graph
algorithms).
• Reduces instructions per cycle (IPC).
• Poor latency leads to inefficient use of CPU cores.
• Particularly critical when cache misses occur.
Example:
If a processor waits 100 ns for memory access, thousands of CPU cycles are
wasted → reducing performance.
Techniques to Reduce Latency:
• Multi-level cache (L1, L2, L3)
• Prefetching
• NUMA-aware memory allocation
• Faster DRAM technologies

2|Page
HPC by Omieeee.o

Memory Bandwidth -
Memory bandwidth is the amount of data transferred between memory and
processor per unit time (GB/s).
Impact on HPC Performance:
• Limits performance of data-intensive applications (e.g., matrix
multiplication, simulations).
• Low bandwidth causes memory bottleneck.
• Affects parallel scalability.
• Determines how efficiently multiple cores can access memory.
Example:
If computation requires 200 GB/s but memory provides only 100 GB/s →
system becomes bandwidth-bound.
Techniques to Improve Bandwidth:
• High-speed memory (HBM, DDR5)
• Multi-channel memory
• Interleaving
• Increasing memory bus width

3|Page
HPC by Omieeee.o

Que.2) Write a note on Communication costs in parallel machines. [5]

Ans : Communication Costs in Parallel Machines (HPC)
In High Performance Computing (HPC), multiple processors work together to
solve large problems. During execution, processors must exchange data. The
time and resources required for data exchange is called communication cost.
Communication cost significantly affects overall system performance and
scalability.

1. Components of Communication Cost

Communication time is generally modeled as:

a) Startup Time (Latency)

• Time required to initiate communication.
• Includes overhead of message preparation and network setup.
• Dominates when messages are small.
b) Transfer Time (Bandwidth Cost)
• Time to transmit data.
• Depends on network bandwidth.
• Dominates when messages are large.

2. Factors Affecting Communication Cost

1. Network Latency – Delay in sending message.
2. Network Bandwidth – Data transfer rate.
3. Message Size – Larger messages take more time.
4. Network Topology – Mesh, Torus, Hypercube etc.
5. Contention – Multiple processors using network simultaneously.
6. Synchronization Overhead – Barriers and locks increase delay.

4|Page
HPC by Omieeee.o

3. Types of Communication in HPC

• Point-to-Point Communication (MPI Send/Receive)
• Collective Communication (Broadcast, Reduce, Scatter, Gather)
• Synchronous vs Asynchronous Communication
• Shared Memory Communication

4. Impact on Performance
• High communication cost reduces speedup and efficiency.
• Limits scalability of parallel programs.
• Causes processors to remain idle while waiting for data.
• In fine-grained parallelism, communication overhead may exceed
computation time.

5. Techniques to Reduce Communication Cost

• Increase computation-to-communication ratio
• Use message aggregation
• Overlap communication with computation
• Use efficient network topology
• Minimize synchronization points
• Optimize data partitioning

5|Page
HPC by Omieeee.o

Que.3) Explain with suitable diagram:

Ans :
i) SIMD Architecture
• SIMD stands for Single Instruction Multiple Data that is a specialized type of
computer architecture in which the processors perform all calculations on a
series of data at one time.
• This architecture is ideal for those applications that involve the same
operation to be done on large sets such as multimedia and scientific
simulations.
• The SIMD can be done on different types of hardware such as; the CPU with
simultaneous multiple data hardware such as the Intel SSE or the AVX and
the GPU hardware.
Advantages of SIMD
1. Efficiency: Specifically, SIMD is useful in operations that require the
application of similar operations in large sets such as images or matrices.
2. Parallelism: It refers to the technique involving the computation through
applying the same instruction to numerous data points to cut down the
time of processing large amounts of data.
3. Simpler control: Because only one instruction is issued to all of the data
points, there is little overhead with which to manage the tasks and ensure
that they are synchronized.

SMID MIMD

6|Page
HPC by Omieeee.o

ii) MIMD Architecture

• MIMD or Multiple Instruction, Multiple Data is a type of parallel processing
where in many processors handle various instructions on various data at the
same time.
• This architecture allows for a great degree of adaptability and the system
can be used for a wide range of applications, from realistic modeling to
multi-threaded program.
• MIMD systems find more application in the current multi-core processors
and distributed computational platforms.
Advantages of MIMD
1. Flexibility: MIMD is preferably suited to multitask since it can perform
different tasks concurrently. Due to it’s risky nature, it is best suited for
computations involving lots of processing power such as multi-threaded
processes.
2. Scalability: It must be noted that MIMD architecture is highly scalable in
nature since the presence of more processors could always be included to
tackle other activities without interfering with the existing operations.
3. Task variety: In MIMD system, while each of the processor can work on a
completely different operation, which is a desirable property in distributed
system or simulation.

7|Page
HPC by Omieeee.o

Que.4) What are the types of Dataflow Execution Models? [6]

Ans:
Types of Dataflow Execution Models in HPC
In the Dataflow execution model, instructions are executed only when all their
required input data becomes available.
Unlike the control-driven (Von Neumann) model, execution is data-driven.
It is widely used in parallel computing and HPC because it naturally exposes
parallelism.

Main Types of Dataflow Execution Models

1. Static Dataflow Model
Definition:
In the static dataflow model, each operation (node) can execute only once for
each input set, and there is a fixed number of data tokens on each arc.
Characteristics:
• Fixed data dependency graph.
• No multiple tokens allowed on edges.
• Simple control mechanism.
• Limited flexibility.
Limitation:
• Cannot efficiently handle loops and recursion.
Example:
Simple arithmetic expressions where each instruction executes once.

8|Page
HPC by Omieeee.o

2. Dynamic Dataflow Model

Definition:
In the dynamic dataflow model, multiple data tokens can exist on the same
arc, allowing multiple instances of an operation to execute simultaneously.
Characteristics:
• Supports loops and recursion.
• Multiple active instances of nodes.
• More flexible than static model.
• Better suited for parallel systems.
Advantage:
Improves parallelism and scalability.
Example:
Parallel matrix multiplication with repeated operations.

3. Synchronous Dataflow (SDF)

Definition:
Execution occurs in a predefined order where the rate of data production and
consumption is fixed.
Characteristics:
• Deterministic execution.
• Predictable behavior.
• Used in streaming applications.
Application:
Signal processing systems.

9|Page
HPC by Omieeee.o

Que.5) Write a short note on Level of Parallelism. [4]

Ans :
Level of Parallelism (LoP) refers to the degree to which a computational task
can be divided into smaller independent tasks that can execute simultaneously.
In High Performance Computing (HPC), higher levels of parallelism lead to
better performance and scalability.

Types of Parallelism (Levels)

1. Bit-Level Parallelism
• Improves performance by increasing processor word size.
• Example: 64-bit processor processes 64 bits at once instead of 32 bits.
• Enhances arithmetic computation speed.

2. Instruction-Level Parallelism (ILP)

• Multiple instructions executed simultaneously within a single CPU.
• Achieved using:
o Pipelining
o Superscalar architecture
o Out-of-order execution
• Improves processor throughput.

3. Data-Level Parallelism (DLP)

• Same operation performed on multiple data elements simultaneously.
• Implemented using:
o SIMD architecture
o GPUs
• Common in matrix operations, image processing, simulations.

10 | P a g e
HPC by Omieeee.o

4. Task-Level Parallelism (TLP)

• Different tasks or threads executed in parallel.
• Used in:
o Multi-core systems
o Distributed computing
o MIMD systems
• Suitable for complex applications.

# Importance in HPC
• Determines achievable speedup.
• Improves resource utilization.
• Increases scalability of parallel systems.
• Helps reduce overall execution time.

Que.6) Explain the basic working principle of Superscalar Architecture. [6]

Ans :

11 | P a g e
HPC by Omieeee.o

A more aggressive approach is to equip the processor with multiple processing

units to handle several instructions in parallel in each processing stage. With
this arrangement, several instructions start execution in the same clock cycle,
and the process is said to use multiple issues.
• Such processors are capable of achieving an instruction execution
throughput of more than one instruction per cycle.
• They are known as 'Superscalar Processors'.
In the above diagram, there is a processor with two execution units; one for
integer and one for floating point operations.
The instruction fetch unit is capable of reading the instructions at a time and
storing them in the instruction queue. In each cycle, the dispatch unit retrieves
and decodes up to two instructions from the front of the queue. If there is one
integer, one floating point instruction and no hazards, both the instructions are
dispatched in the same clock cycle.
Example: A Dual-Issue Superscalar CPU
Imagine a processor with:
• Two Execution Units: One for integer math (like adding numbers) and
one for floating-point math.
• A fast instruction fetch unit that grabs two instructions at once and puts
them in a queue.
• A dispatch unit that decodes and sends up to two instructions per cycle.

12 | P a g e
HPC by Omieeee.o

Que.7) Explain N-wide Superscalar Architectures. [6]

Ans :

N-wide Superscalar Architecture

An N-wide superscalar architecture is a processor design that can fetch,

decode, issue, and execute N instructions per clock cycle, provided the
instructions are independent.
Working Principle
• The processor fetches N instructions per cycle.
• Instructions are decoded and checked for dependencies.
• Independent instructions are dispatched to N parallel execution units
(ALUs, FPUs, Load/Store units).
• Results are written back to the register file.
• Often uses out-of-order execution, register renaming, and branch
prediction.

13 | P a g e
HPC by Omieeee.o

Que.8) Describe UMA and NUMA multicomputer platforms. [5]

Ans :
Uniform Memory Access (UMA) -
• In UMA, where Single memory controller is used.
• Uniform Memory Access is slower than non-uniform Memory Access.
• In Uniform Memory Access, bandwidth is restricted or limited rather than
non-uniform memory access.
• There are 3 types of buses used in uniform Memory Access, which are:
Single, Multiple and Crossbar.
• It is applicable for general-purpose applications and time-sharing
applications.

Advantages of Uniform Memory Access (UMA)

1. Easy to Implement:
2. Low Latency
3. Low Cost
Disadvantages of Uniform Memory Access (UMA)
1. Limited Scalability
2. Limited Bandwidth
3. Limited Memory Capacity

14 | P a g e
HPC by Omieeee.o

Non-Uniform Memory Access (NUMA) -

• In NUMA, where different memory controller is used. Non-uniform Memory
Access is faster than uniform Memory Access.
• Non-uniform Memory Access is applicable for real-time applications and
time-critical applications.

Advantages of a Non-Uniform Memory Access (NUMA)

1. Improved performance
2. Scalability
3. Reduced memory contention
Disadvantages of Non-Uniform Memory Access (NUMA)
1. Complexity
2. Higher cost
3. Performance variability

15 | P a g e
HPC by Omieeee.o

Que.9) Explain Cache coherence in multiprocessor systems. [5]

Ans :
In multiprocessor system where many processes needs a copy of same memory
block, the maintenance of consistency among these copies raises a problem
referred to as Cache Coherence Problem.
This occurs mainly due to these causes:-
• Sharing of writable data.
• Process migration.
• Inconsistency due to I/O
There are two classes of protocols in use each of which uses different
techniques to track the sharing status.
1) Directory based
2) snooping

1) Directory based
The sharing status of a particular block of physical memory is kept in one
location called the directory. There are different types of directory based cache
coherence.
Associated with the memory or some other single serialization point, such as
the outermost cache in a multicore.

2) Snooping
Rather than keeping a state of sharing in a single directory, every cache that
has of copy of data from a block of physical memory could track the sharing of
the status of the block.
Snooping can also be used as the coherence protocol for a multichip
multiprocessor and some design support a snooping protocol on top of a
directory protocol with each multicore.

16 | P a g e
HPC by Omieeee.o

Que.10) What is a VLIW processor? Write any two advantages of VLIW. [4]
Ans :
Very Long Instruction Word (VLIW) is a type of processor architecture designed
to execute multiple operations in a single instruction cycle. Unlike conventional
processors that rely heavily on hardware to find parallelism, VLIW shifts this
responsibility to the compiler, which packs independent instructions into one
long instruction word.
• Execution units work simultaneously on different operations.
• Reduces the need for complex runtime scheduling.
• Improves instruction-level parallelism.
Features :
• The processors in this architecture have multiple functional units, fetch
from the Instruction cache that have the Very Long Instruction Word.
• Multiple independent operations are grouped together in a single VLIW
Instruction. They are initialized in the same clock cycle.
• Each operation is assigned an independent functional unit.
• All the functional units share a common register file.
• Instruction words are typically of the length 64-1024 bits depending on
the number of execution unit and the code length required to control
each unit.
• Instruction scheduling and parallel dispatch of the word is done statically
by the compiler.
• The compiler checks for dependencies before scheduling parallel
execution of the instructions.
Any Two Advantages of VLIW
1. Simpler Hardware Design
• No complex dynamic scheduling hardware required.
2. High Instruction Throughput
• Multiple operations executed per clock cycle.

17 | P a g e
HPC by Omieeee.o

Que.11) What are the applications of parallel computing? [4]

Ans : Applications of Parallel Computing in HPC
1. Databases and Data Mining
• Used for processing large volumes of structured and unstructured data.
• Enables fast query processing in distributed databases.
• Supports big data analytics and pattern discovery.
• Used in business intelligence, fraud detection, and recommendation
systems.
• Technologies: Distributed databases, Hadoop, Spark.
2. Real-Time Simulation of Systems
• Simulates physical and real-world systems in real time.
• Applications include:
o Flight simulators
o Weather forecasting
o Traffic control systems
• Requires high computational speed and accuracy.
3. Science and Engineering
• Used in complex scientific computations such as:
o Climate modeling
o Molecular modeling
• Helps solve large mathematical models and differential equations.
4. Advanced Graphics, Augmented Reality (AR) & Virtual Reality (VR)
• Parallel processing used in:
o 3D rendering
o Real-time graphics generation
o Gaming engines
o AR/VR environments
18 | P a g e
HPC by Omieeee.o

Unit II – Parallel Algorithm Design

Que.1) Explain any three decomposition techniques with example. [6]

Ans :
Decomposition techniques are used to break a complex problem into smaller,
manageable sub-problems so that they can be solved efficiently, especially in
parallel computing systems. This improves performance, scalability, and
resource utilization.
The main decomposition techniques are:

1. Recursive Decomposition (Divide and Conquer)

Description:
In this technique, a problem is divided into smaller sub-problems of the same
type. Each sub-problem is solved recursively, and their results are combined to
get the final solution.
Key Idea:
Break → Solve → Combine
Example:
Merge Sort Algorithm
• Divide the array into two halves.
• Recursively sort each half.
• Merge the sorted halves.
Advantages:
• Simple and structured approach
• Naturally supports parallel execution
• Efficient for large problems

19 | P a g e
HPC by Omieeee.o

2. Data Decomposition
In data decomposition, the data is divided into smaller parts, and each
processor works on a different portion of the data simultaneously.
Key Idea:
Same operation → Different data
Example:
Matrix Multiplication
• Matrices A and B are divided into smaller sub-matrices.
• Each processor computes a portion of the result matrix C.
• Results are combined to form the final matrix.
Advantages:
• High parallel efficiency
• Good load balancing
• Suitable for large datasets

3. Functional Decomposition
In functional decomposition, a system is divided into different functions or
tasks. Each function performs a specific operation independently.
Key Idea:
Different operations → Possibly same or different data
Example:
Software Development Process
• UI Design
• Backend Development
• Database Design
Each team works independently on different functions.
Advantages:
• Clear modular design
• Easy maintenance

20 | P a g e
HPC by Omieeee.o

Que.2) Describe mapping technique for load balancing. [5]

Ans :
Mapping Techniques for Load Balancing
Mapping techniques decide how tasks or requests are assigned to
servers/processors to ensure balanced load and better performance.

1. Static Mapping
Description:
Fixed assignment of tasks to servers. Mapping does not change over time.
Advantages:
• Simple and easy to implement
• Predictable task distribution
Use Cases:
• Stable and predictable workloads
• Small-scale systems
• Fixed number of servers/clients

2. Dynamic Mapping
Description:
Assignments change based on current server load or network conditions.
Advantages:
• Handles changing workloads
• Better resource utilization
Use Cases:
• Large-scale web applications
• Cloud environments
• Fluctuating workloads

21 | P a g e
HPC by Omieeee.o

3. Hierarchical Mapping
Servers are organized in levels (tiers). Requests pass through higher-level nodes
before reaching specific servers.
Advantages:
• Scalable
• Fault tolerant
Use Cases:
• Large distributed systems
• Cloud computing
• Content Delivery Networks (CDNs)
4. Hash-Based Mapping
Uses a hash function to assign requests to servers.
Advantages:
• Simple and efficient
• Ensures consistent mapping
Use Cases:
• Distributed databases
• CDNs
• Peer-to-peer networks
5. Adaptive Mapping
Uses intelligent algorithms to continuously adjust mappings based on real-time
conditions.
Advantages:
• Highly efficient
• Optimizes resource utilization
Use Cases:
• Highly dynamic environments
• Real-time optimization systems

22 | P a g e
HPC by Omieeee.o

Que.3) Explain the classification of Dynamic mapping techniques. [5]

Ans :
Mapping strategies in Elasticsearch play an important role in defining how
fields in documents are mapped to data types in the index.
Dynamic Mapping
• Dynamic mapping allows Elasticsearch to automatically detect and
create mappings for fields in documents at index time.
• When we index a document with new fields, Elasticsearch dynamically
adds mappings for those fields based on their data types.
• This flexibility is useful when dealing with varying data structures.
Example: Indexing a Document with Dynamic Mapping
Suppose we have an index called products, and we index a document
representing a new product with additional fields.

PUT /products/_doc/1
{
"name": "New Product",
"price": 99.99,
"description": "A brand new product with
additional features",
"brand": "BrandX",
"stock_quantity": 100
}

Explanation:
• The document contains fields like name, price, description, brand, and
stock_quantity.
• Since these fields are not explicitly defined in the index mapping,
Elasticsearch dynamically creates mappings for them based on their data
types (text, float, keyword, and integer, respectively).

23 | P a g e
HPC by Omieeee.o

Que.4) What are the characteristics of tasks? [4]

Ans :
Characteristics of Tasks in Parallel Algorithm Design
In parallel algorithm design, tasks are the basic units of work executed
concurrently. Their characteristics determine the performance of the parallel
system.

1. Task Granularity
Refers to the size of a task.
• Fine-grained: Small tasks, frequent communication.
• Coarse-grained: Large tasks, less communication.
2. Task Independence
Tasks may be:
• Independent: Can execute simultaneously without waiting.
• Dependent: Require output from other tasks.
3. Communication Requirement
Tasks may need to exchange data. Efficient communication reduces overhead
and improves speedup.
4. Synchronization
Some tasks require coordination (barriers, locks, etc.) to maintain correctness.
5. Load Balance
Tasks should be distributed evenly among processors to avoid idle time.
6. Scalability
The task structure should allow performance improvement when the number
of processors increases.
7. Locality of Data
Tasks should access local data as much as possible to reduce memory access
time and communication cost.

24 | P a g e
HPC by Omieeee.o

Que.5) What are the characteristics of Inter-Task Interactions? [4]

Ans :
Characteristics of Inter-Task Interactions
1. Communication Pattern
Describes how tasks exchange data.
• Point-to-Point: One task communicates with another.
• Collective: One-to-many or many-to-many communication (broadcast,
reduction).
2. Frequency of Communication
• Frequent interaction: High communication overhead.
• Infrequent interaction: Better performance.
3. Volume of Data Exchange
The amount of data transferred between tasks. Larger data transfer increases
communication cost.
4. Synchronization Requirement
Tasks may need synchronization mechanisms like:
• Barriers
• Locks
• Message passing
More synchronization increases waiting time.
5. Dependency
• Data Dependency: One task depends on the result of another.
• Control Dependency: Execution order must be maintained.
Higher dependency reduces parallelism.
6. Communication Overhead
Time spent in data transfer instead of computation. Efficient algorithms try to
minimize this overhead.

25 | P a g e
HPC by Omieeee.o

Que.6) Explain in detail Parallel Algorithm Models. [6]

Ans :
Parallel Algorithm Models
Parallel algorithm models provide structured approaches for designing efficient
parallel programs.

1. Data Parallel Model

Same operation is performed on different parts of data.
• Data is partitioned among processors
• Same instruction executed on each partition
• Requires good load balancing
Example: Matrix multiplication, vector addition

2. Task Parallel Model

Different tasks/functions are executed in parallel.
• Tasks may be independent or dependent
• Suitable for heterogeneous systems
• May cause load imbalance
Example: Separate processors for input, processing, and output

3. Work Pool Model

Tasks are stored in a queue; processors dynamically take tasks.
• Dynamic load balancing
• Suitable for irregular problems
• Overhead for task management
Example: Parallel search algorithms

26 | P a g e
HPC by Omieeee.o

4. Master–Slave Model
One master assigns tasks to worker processors.
• Centralized control
• Simple implementation
• Master can become bottleneck
Example: MapReduce

5. Pipeline Model
Computation divided into stages.
• Each processor performs one stage
• High throughput
• Slowest stage limits speed
Example: Instruction pipeline

6. Divide and Conquer Model

Problem recursively divided into smaller sub-problems.
• Recursive decomposition
• Sub-problems solved in parallel
• Requires result merging
Example: Merge Sort

27 | P a g e
HPC by Omieeee.o

Que.7) Explain the different methods for Containing Interaction Overheads.

[5]
Ans: Methods for Containing Interaction Overheads
Interaction overheads occur due to communication, synchronization, and
coordination among tasks. Reducing these overheads improves performance
and scalability.

1. Increase Task Granularity

• Use coarse-grained tasks instead of very small tasks.
• Reduces frequency of communication.
• Less synchronization overhead.
2. Minimize Communication Volume
• Reduce the amount of data exchanged between tasks.
• Send only required data.
• Use efficient data structures.
3. Reduce Communication Frequency
• Combine multiple small messages into one large message.
• Avoid unnecessary interactions.
4. Overlap Communication with Computation
• Perform computation while waiting for data transfer.
• Use asynchronous communication techniques.
5. Improve Data Locality
• Assign tasks to processors where required data is already available.
• Reduces remote memory access and latency.
6. Efficient Mapping of Tasks
• Place frequently interacting tasks on nearby processors.
• Reduces communication delay.

28 | P a g e
HPC by Omieeee.o

Que.8) Explain with example (any two): [6]

Ans :
i) Recursive Decomposition
Explanation:
Recursive decomposition (Divide and Conquer) breaks a problem into smaller
sub-problems of the same type. Each sub-problem is solved recursively, and
their results are combined to obtain the final solution.
Example:
Merge Sort
• Divide the array into two halves.
• Recursively sort each half in parallel.
• Merge the sorted halves.
Key Point:
Suitable for problems that can be repeatedly divided into similar smaller tasks.

ii) Data Decomposition

Explanation:
In data decomposition, the data is divided into smaller parts, and the same
operation is performed on each part in parallel.
Example:
Matrix Multiplication
• Divide matrices into sub-matrices.
• Each processor computes a portion of the result matrix.
• Combine all partial results to form the final matrix.
Key Point:
Same computation, different data partitions.

29 | P a g e
HPC by Omieeee.o

iii) Exploratory Decomposition

Explanation:
Exploratory decomposition is used when the problem involves searching
through a large search space. Different processors explore different parts of the
solution space simultaneously.
Example:
Parallel Depth-First Search (DFS)
• Each processor explores a different branch of the search tree.
• If one finds the solution, others can stop.
Key Point:
Suitable for search-based problems like AI, game playing, and branch-and-
bound algorithms.

30 | P a g e
HPC by Omieeee.o

Que.9) Explain different schemes for Static Mapping. [5]

Ans:
Static Mapping Schemes
Static mapping assigns tasks to processors before execution and does not
change during runtime.

1. Block Mapping
Tasks are divided into equal contiguous blocks and assigned to processors.
Best for: Uniform workload.
2. Cyclic Mapping
Tasks are assigned in round-robin fashion.
Best for: Slight variation in task size.
3. Block-Cyclic Mapping
Small blocks of tasks are distributed cyclically.
Best for: Improved load balancing in large problems.
4. Graph-Based Mapping
Tasks are mapped based on communication patterns to reduce communication
cost.
Best for: Communication-intensive applications.

31 | P a g e