Code: CS484                                           Subject: PARALLEL AND DISTRIBUTED SYSTEM

Flowchart: Alternate Process: MARCH 2010

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.  Discuss Gustafson’s law for scaled problems.  


             b.  Describe sequential consistency models in brief.


             c.  The labels in a d-dimensional hypercube use d bits.  Fixing any k of these bits, show that the nodes whose labels differ in the remaining d-k bit positions form a (d-k)-dimensional sub-cube composed of  nodes.


             d.  What do you understand by regular and nonregular interconnection networks?  Explain with examples.


             e.  What is the radius and diameter of a network?  Explain giving suitable examples.


             f.   Describe weak consistency models in brief.


             g. Define the Speedup and efficiency of a parallel machine.



Q.2       a.  Illustrate the permutation setup for a 8x12 Clos network for the permutation                p=[1 3 5 8 9 4 2 11].


             b.  Compare the Crossbar, Clos and Benes network for various performance characteristics.



  Q.3     a.  Write an algorithm for the addition of n numbers on a Hypercube and show its correctness with an example.  Obtain its complexity also.


             b. Discuss various conditions of parallelism.



  Q.4     a. Describe virtual memory developments for distributed system. 


             b. Describe various levels of parallelism in programs.                                                      (9+9)



 Q.5     a.  Describe parallelism profile in programs.


             b.  Discuss various transparency issues in distributed system?  Discuss various advantages of a distributed system.                                                                                                                               (9+9)            

  Q.6     a.  Explain the logical clock in distributed operating system.


             b. How will you find Concurrency among the modules? Discuss.



  Q.7     a. Discuss cache memory organizations for multiprocessor system.


             b. Discuss cache performance issues.                                                                                                               (12+6)