**ALCCS**

**FEBRUARY 2009**

**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)**