ALCCS

 

FEBRUARY 2009

 

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

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

 

NOTE:

      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)