(SEM VI) THEORY EXAMINATION 2017-18 PARALLEL ALGORITHMS

Parallel Algorithms (NCS-063)

Complete Section-Wise Explanation – B.Tech Semester VI

Introduction to the Subject

Parallel Algorithms study how problems can be solved faster by using multiple processors simultaneously instead of a single processor. As problem sizes and data volumes grow, sequential algorithms become slow and inefficient. Parallel algorithms divide work among processors so that tasks are performed at the same time, reducing overall execution time.

This subject focuses on:

Parallel processing concepts and models

Speedup, efficiency, and cost analysis

PRAM models and algorithm design

Parallel sorting and searching

Parallel graph and matrix algorithms

Combinatorial and backtracking problems

The question paper is divided into three sections: A, B, and C, and students must attempt all sections as per instructions.

SECTION A – Fundamental Concepts (Short Answers)

Pattern:
Attempt all questions
10 questions × 2 marks = 20 marks

Nature of Section A

Section A checks your basic conceptual clarity. Answers should be short, direct, and accurate, usually 2–3 lines. This section is very scoring if definitions are well prepared.

Explanation of Section A Topics

Basic Concepts of Parallel Processing
Parallel processing involves executing multiple instructions simultaneously using more than one processor. Key concepts include concurrency, synchronization, communication, and load balancing.

Sequential Model and Need for Parallel Model
The sequential model executes one instruction at a time on a single processor. As problem size increases, execution time becomes large, so parallel models are needed to improve performance and reduce computation time.

Utilization vs Efficiency
Utilization measures how effectively processors are kept busy, while efficiency measures how well parallel resources are used compared to an ideal case.

Sequential Bottleneck in Amdahl’s Law
The sequential bottleneck is the part of a program that cannot be parallelized. According to Amdahl’s Law, this limits the maximum achievable speedup.

Bitonic Sequence
A bitonic sequence is a sequence that first increases and then decreases, or vice versa. It is used in bitonic sorting networks.

Comparator
A comparator is a basic hardware or logical unit that compares two elements and swaps them if required. Comparators are the building blocks of sorting networks.

Matrix Operations
Matrix operations include addition, subtraction, multiplication, and transposition, which can be efficiently parallelized.

Matrix Transposition
Matrix transposition rearranges rows into columns. In parallel computing, it is used to improve memory access patterns and performance.

Minimum Cost Spanning Tree and Graph
A graph consists of vertices and edges. A minimum cost spanning tree connects all vertices with minimum total edge weight and no cycles.

Parallel Backtracking
Parallel backtracking explores different branches of a search tree simultaneously using multiple processors to reduce search time.

SECTION B – Parallel Models, Sorting & Analysis

Pattern:
Attempt any three questions
3 × 10 marks = 30 marks

Nature of Section B

Section B requires descriptive explanations and numerical analysis. Answers must be written in paragraph form, with diagrams or step-wise explanation where required.

Explanation of Section B Questions

Pyramid, Butterfly, and Shuffle-Exchange Networks

The pyramid network is hierarchical and offers better communication efficiency compared to mesh and tree models. Butterfly and shuffle-exchange networks are multistage interconnection networks that provide efficient communication with logarithmic depth and are commonly used in parallel machines.

Cost-Optimal Algorithm and Parallel Sum

A cost-optimal algorithm ensures that the total work done by all processors is proportional to the best sequential algorithm.
In parallel reduction for summing n numbers using n/2 processors, pairs of numbers are added simultaneously. Speedup, cost, and efficiency are calculated by comparing parallel execution time with sequential time.

Lower Bounds on Parallel Sorting & Odd-Even Transposition Sort

Lower bounds define the minimum time required to sort elements in parallel.
Odd-Even Transposition Sort works by alternating odd and even phases where adjacent elements are compared and swapped. The question requires step-by-step sorting of the given sequence using four processors.

Parallel Sorting Networks & Enumeration Sort

Parallel sorting networks use fixed comparator connections independent of input.
Enumeration sort assigns a rank to each element by counting how many elements are smaller than it, allowing elements to be placed in parallel.

Parallel Alpha-Beta Search & Branch and Bound

Parallel alpha-beta search speeds up game tree evaluation by exploring branches concurrently.
Parallel branch and bound solves optimization problems by pruning non-promising branches using multiple processors.

SECTION C – Models, Laws & Advanced Algorithms

Pattern:
Attempt any one part from each question
5 questions × 10 marks = 50 marks

This section has the highest weightage and requires deep conceptual understanding.

Question 3 – Models of Computation

RAM vs PRAM Model

The RAM model represents serial computation with a single processor and uniform memory access.
The PRAM model represents parallel computation with multiple processors sharing a common memory. Differences include concurrency, synchronization, and memory access rules.

PRAM Models and Prefix Sum

PRAM models include EREW, CREW, CRCW (common, arbitrary, priority).
Parallel prefix sum computes cumulative sums efficiently in logarithmic time using multiple processors.

Question 4 – Cost-Optimality & Amdahl’s Law

Cost-Optimal Prefix Sum & Brent’s Theorem

A cost-optimal prefix sum ensures total work remains minimal.
Brent’s Theorem states that a parallel algorithm can be simulated on fewer processors with limited slowdown. The theorem helps balance processor count and execution time.

Amdahl’s Effect and Amdahl vs Gustafson

Amdahl’s Law shows limited speedup due to serial fraction.
Gustafson’s Law argues that increasing problem size allows better utilization of parallelism, offering more optimistic scalability.

Question 5 – Parallel Merging & Bitonic Sort

Parallel Merging and EREW Model

Parallel merging divides input lists and merges them concurrently while avoiding simultaneous read/write conflicts under EREW rules.

Bitonic Merge Sort

Bitonic merge sort uses bitonic sequences and comparator networks to sort elements in logarithmic time. The question requires sorting the given sequence step by step.

Question 6 – Searching & Matrix Algorithms

Parallel Searching & CREW Model

Parallel searching divides the search space among processors. CREW allows concurrent reads but exclusive writes, improving search efficiency.

2-D Mesh SIMD & Matrix Multiplication

In a 2-D mesh SIMD model, processors are arranged in a grid. Parallel matrix multiplication assigns computations to processors based on row-column alignment.

Question 7 – Combinatorial Problems & Search Trees

Parallel Alpha-Beta Search and Combinatorics

Parallel alpha-beta search reduces computation time in game trees.
Permutations, combinations, and derangements represent different ways of arranging elements and are often solved using parallel algorithms.

Combinatorial Search Problems

Search problems are represented as trees where nodes represent states. Depth-first and breadth-first search algorithms explore trees differently, and parallelism speeds up exploration.