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)