Code: CS484†††††††††††††††††††††††††††††††††††††††††† Subject: PARALLEL AND DISTRIBUTED SYSTEM

Time: 3 Hours††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††† †††††††† Max. Marks: 100



      Question 1 is compulsory and carries 28 marks. Answer any FOUR questions from the rest.Marks are indicated against each question.

      Parts of a question should be answered at the same place.



Q.1 †††††††††† ††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††† (7 x 4)

†††††††††††† a.What is the relation between Computing Energy, Speedup and Efficiency? Explain.


†††††††††††† b.Discuss various conditions in which pipelined execution of a job is stalled for an instruction pipeline.


†††††††††††† c.Discuss various forms of memory interleaving.List advantages & disadvantages of these schemes.


†††††††††††† d.What do you understand by single and multistage interconnection networks? Explain with examples.


†††††††††††† e.State and prove 0-1 principle.


†††††††††††† f.†† What are the PRAM models for parallel algorithms?


†††††††††††† g. List the difference between DOS and NOS.


Q.2†††††† a.Write an algorithm for the addition of n numbers on Perfect Shuffle network.Show its correctness with an example.

††††††††††††††††† †††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††

†††††††††††† b.Write an algorithm for the addition of n numbers on a Chordal ring of degree four and show itís correctness with an example.††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††† (9+9)


Q.3†††† a.Design an Omega network and explain its routing.


†††††††††††† b.What is the order of comparators used in a BITONIC-SORTER[n], where n is an exact power of 2? Show it.††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††† (9+9)


Q.4†††† a.Convert the task graph below into program fragment using

††††††††††††††††† (i)†† FORK-JOIN

††††††††††††††††† (ii)Cobegin-Coend†††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††





††††††† †††† b.What is a bitonic sequence? Design a sorter circuit and show that it sorts any arbitrary sequence.†††† (9+9)


Q.5†††† a.What are distributed objects and how these are implemented in distributed system?


†††††††††††† b.What are different models of distributed system? Discuss various advantages of a distributed system.†††††††††† (9+9) ††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††

Q.6†††† a.Write QuickSort algorithm for MIMD machine and explain.


†††††††††††† b.Explain the Bernstienís condition for exploiting concurrency among the modules.††††††† (9+9)


Q.7††††††††† Write short notes on


(i)                                                                                                                                                                                                                                                                    Semaphore

(ii)                                                                                                                                                                                                                                                                   Speedup of a parallel machine

(iii)                                                                                                                                                                                                                                                                        Minskyís Conjecture††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††† (6+6+6)