About this previous year paper
PARALLEL ALGORITHM (NCS063)
Section-wise Solved Answers & Notes
SECTION – A (10 × 2 = 20 Marks)
Very short answers (2 marks each)
(a) Speed-up
Speed-up is the ratio of execution time of best sequential algorithm to parallel algorithm.
Speed-up=TsTp\text{Speed-up} = \frac{T_s}{T_p}Speed-up=TpTs
(b) SIMD
SIMD (Single Instruction Multiple Data) is a parallel model where same instruction operates on multiple data simultaneously.
(c) Hypercube connection
A hypercube is an interconnection network where each node is connected to log₂N neighbors, forming an n-dimensional cube.
(d) Time required for Bitonic sorting on PRAM
Bitonic sorting requires O((log n)²) time on PRAM.
(e) Parallel Prim’s MST algorithm time
Using p processors for a graph with n nodes, the time complexity is:
O(n2p)O\left(\frac{n^2}{p}\right)O(pn2)
(f) Task-throughput
Task-throughput is the number of tasks completed per unit time by a parallel system.
(g) Complexity of prefix sum in PRAM
Prefix sum can be computed in O(log n) time using PRAM.
(h) Common CRCW PRAM
CRCW PRAM allows multiple processors to read and write simultaneously, and common CRCW allows writing only if values are same.
(i) Data-parallel computation
A computation where same operation is performed on different data elements in parallel.
(j) Permutation vs Combination
| Permutation | Combination |
|---|---|
| Order matters | Order does not matter |
| nPr | nCr |
SECTION – B (Any 5 × 10 = 50 Marks)
(a) Butterfly Model
Butterfly network is a multistage interconnection network used in FFT and sorting.
It consists of log₂N stages and provides low communication delay.
(Diagram compulsory in exam)
(b) PRAM Computational Model
PRAM (Parallel Random Access Machine) assumes processors share a common memory.
Types:
• EREW – Exclusive Read Exclusive Write • CREW – Concurrent Read Exclusive Write
(c) Performance Measures of Parallel Algorithm
• Speed-up • Efficiency
• Cost • Scalability
Example:
Efficiency = Speed-up / Number of processors
(d) Bitonic Merge
Bitonic merge combines two bitonic sequences into one sorted sequence using compare-exchange operations.
Used in Bitonic sorting network.
(e) Cost-optimality
A parallel algorithm is cost-optimal if:
Cost=Parallel time×Processors=O(Ts)\text{Cost} = \text{Parallel time} \times \text{Processors} = O(T_s)Cost=Parallel time×Processors=O(Ts)
Example: Parallel prefix sum.
(f) Parallel Branch and Bound
Used for combinatorial optimization problems.
Search space is divided among processors, and sub-optimal branches are pruned in parallel.
(g) Hypercube vs Shuffle-Exchange Network
| Hypercube | Shuffle-Exchange |
|---|---|
| log₂N connections | Fixed shuffle pattern |
| Low diameter | Simple design |
| Scalable | Less scalable |
(h) Parallel Sorting Networks & Enumeration Sort
Sorting network is a fixed sequence of comparison operations.
Enumeration sort assigns rank to each element and places it accordingly.
SECTION – C (Any 2 × 15 = 30 Marks)
Q3 (i) Amdahl Effect & Amdahl’s Law
Amdahl’s Law states that speed-up is limited by the sequential portion of the program.
S=1(1−P)+PNS = \frac{1}{(1-P) + \frac{P}{N}}S=(1−P)+NP1
Where:
P = parallel fraction, N = processors
Q3 (ii) BFS & DFS (Parallel Graph Traversal)
Breadth-First Search (BFS) Explores graph level by level.
Parallel BFS assigns nodes of same level to different processors. Depth-First Search (DFS)
Explores deep paths first. Parallel DFS uses task splitting.
Q4 Parallel Alpha-Beta Search
Used in game tree search.
Prunes branches that cannot affect final decision, reducing search space.
Q5 Data Parallelism Data Parallelism
Same operation on multiple data items. Comparison:
| Data Parallelism | Task Parallelism |
|---|---|
| Same task, different data | Different tasks |
| SIMD style | MIMD style |
| Data Parallelism | Model Parallelism |
|---|---|
| Data split | Model split |
| Used in arrays | Used in ML models |