B
APJ ABDUL KALAM TECHNOLOGICAL UNIVERSITY
SECOND SEMESTER M.TECH DEGREE EXAMINATION, MAY 2017
Computer Science and Engineering
(Computer Science and Engineering)
(07CS 6104 ADVANCED PARALLEL COMPUTING)
Max. Marks: 60 Duration: 3 Hours
Answer all six questions. Part of each question is compulsory.
Answer either part or part of each question
Q.no. Module 1 Marks
1a Discuss about Pipelining and Superscalar Execution with example. 4
Answer b or c
b
Compute the total cost of communicating a message between two nodes in
the case of store-and forward routing and cut-through routing.
5
c
Illustrate with example, the parallel program execution with the simple
three-state coherence protocol and the implementation of coherence
protocols using hardware mechanisms.
5
Q.no. Module 2 Marks
2a Explain the Scatter and Gather operation with suitable example. 4
Answer b or c
b
Discuss about One-to-all broadcast and all-to-one reduction in different
interconnection topologies. Use One-to-all broadcast and all-to-one
reduction for the multiplication of a 4 x 4 matrix with a 4 x 1 vector.
5
c Design a simple algorithm for all-to-all broadcast on a d-dimensional
hypercube and show all-to-all broadcast on an eight-node hypercube.
5
Q.no. Module 3 Marks
3a
Write down the important characteristics of Tasks and Inter task interactions
4
Answer b or c
b With the help of suitable examples, compare recursive decomposition and
data decomposition techniques.
5
c Categorize the schemes for static mapping of tasks onto processes for load 5
balancing. Show examples.
Q.no. Module 4 Marks
4a Write a note on Sources of Overhead in Parallel Programs. 4
Answer b or c
b
Analyse different algorithm models for structuring parallel algorithms.
5
c
Reducing the interaction overhead among concurrent tasks is important for
an efficient parallel program. Suggest some techniques for reducing the
interaction overhead.
5
Q.no. Module 5 Marks
5a Briefly describe the history of GPU computing.
5
Answer b or c
b Write a CUDA program for implementing multiplication of two matrices. 7
c
Describe various Synchronization Constructs in OpenMP. Compute the
cumulative sum of a list using the ordered directive.
7
Q.no. Module 6 Marks
6a Explain the concept of Parallel Random Number Generators. 5
Answer b or c
b Relate the sorting networks with bitonic merging networks. Illustrate the
procedure with example.
7
c Illustrate the Parallel Formulation of Prim's algorithm with example?
7