DOEACC Society 2006 DOEACC B Level BE5 Parallel Computing ( ) - Question Paper

BE5-R3: PARALLEL COMPUTING
NOTE:
Time: three Hours Total Marks: 100
1.
a) Is it possible for the avg. speedup exhibited by a parallel algorithm to be superlinear?
Justify your ans.
b) Comment on the statement: " Any computer with I/O channel is a multiprocessor".
c) elaborate various kinds of memory interleaving schemes? Which scheme is suitable for
pipelined vector processor?
d) Is a multi-programmed operating system running on a multiprocessor an implementation
of a parallel algorithm? Justify.
e) Distinguish ranging from implicit and explicit parallel computational models.
f) discuss the situations under which cache inherence issue can arise.
g) Comment on the statement: "Parallelism by message passing."
(7x4)
2.
a) describe interconnection network. How will you compare various interconnection
networks?
b) Write algorithms to configure the 2x2 switches of an 8x8 multistage shuffle-exchange
interconnection network in establishing routing path ranging from source port i and
destination port j. Use both XOR and destination tag routing schemes.
c) What do you mean by permutation capability of any interconnection network? How can
you increase the identical for any blocking interconnection network?
(5+8+5)
3.
a) Compare and contrast the subsequent 3 message passing OS models:
Node-addressed model, Channel-addressed model and Object-oriented model.
b) Is the computation on n! parallelizable? If no, then why? If yes, then how?
c) discuss the advantages and disadvantages of multithreaded UNIX kernel.
(8+6+4)
4.
a) discuss Bitonic sorting scheme and explain its complexities.
b) Suggest a suitable SIMD algorithm to multiply 2 (n x n) matrices using (n x n x n)
number of processors. presume suitable value of n. Comment on the time complexity of
your algorithm.
(9+9)
BE5-R3 Page one of two January, 2006
1. ans ques. one and any 4 ques. from two to 7.
2. Parts of the identical ques. should be answered together and in the identical
sequence.
5. Briefly discuss the subsequent performance measuring laws:
a) Fixed-work load speed up (Amdahl’s Law)
b) Fixed-time speed up (Gustafson’s Law)
c) Memory-bound speed up (Sun-Ni Law)
(6+6+6)
6. Consider the subsequent program segment:
DO I = 1, N
DO J = 2, N
S1: A(I,J) = B(I,J) + C(I,J)
S2: C(I,J) = D(I,J)/2
S3: E(I,J) = A(I,J-1) ** two + E(I,J-1)
Enddo
Enddo
a) Show all data dependences among the statements.
b) Show how to parallelize the loop scheduling the parallelizable iterations to concurrent
processors.
(8+10)
7.
a) Comment on the data-parallel paradigm in parallel computing environment with suitable
examples.
b) What is the worst-case time complexity of parallel quick-sort algorithm? Justify your
answer.
(10+8)
BE5-R3 Page two of two January, 2006

Earning:   Approval pending.