THEORY EXAMINATION (SEM–VI) 2016-17 PARALLEL ALGORITHM

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=Tp​Ts​​ 

(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

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

(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)+NP​1​

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: