UGC NET CSE | June 2016 | Part 3 | Question: 53

Question

A Multicomputer  with 256 CPUs is organized as 16$\times$16 grid . What is the worst case delay(in hops) that a message might have to take

• A. 16
• B. 15
• C. 32
• D. 30

Answer 1

In the 16X16 CPU case, the worst-case delay happens when message passes through longest path which is the diagonal of the upper right corner to lower left corner or upper left corner to lower right corner.

Longest path is indicated in red color.

It passes through 2(N-1) = 2(16-1) = 30 hops

Comments

How this formula came 2(n-1)

Answer 2

In the 16X16 grid case, the worst-case delay is 15+15 =30 in hops that a message might have to take. The longest path in 16X16 grid is the diagonal of the upper right corner to lower left corner or upper left corner to lower right corner.