Deck 5: Communication Patterns and Algorithms in Distributed Systems

Question 1

In a broadcast and reduction on a balanced binary tree reduction is done in ______

A)recursive order
B)straight order
C)vertical order
D)parallel order

Answer 1

recursive order

Question 2

if "X" is the message to broadcast it initially resides at the source node

A)1
B)2
C)8
D)0

Answer 2

0

Question 3

logical operators used in algorithm are

A)xor
B)and
C)both
D)none

Answer 3

both

Question 4

Generalization of broadcast in Which each processor is

A)source as well as destination
B)only source
C)only destination
D)none

Question 5

The algorithm terminates in _____ steps

A)p
B)p+1
C)p+2
D)p-1

Question 6

Each node first sends to one of its neighbours the data it need to....

A)broadcast
B)identify
C)verify
D)none

Question 7

The second communication phase is a columnwise ______ broadcast of consolidated

A)all-to-all
B)one -to-all
C)all-to-one
D)point-to-point

Question 8

All nodes collects _____ message corresponding to ?p nodes to their respectively

A)?p
B)p
C)p+1
D)p-1

Question 9

It is not possible to port ____ for higher dimensional network

A)algorithm
B)hypercube
C)both
D)none

Question 10

If we port algorithm to higher dimemsional network it would cause

A)error
B)contention
C)recursion
D)none

Question 11

In the scatter operation ____ node send message to every other node

A)single
B)double
C)triple
D)none

Question 12

The gather Operation is exactly the inverse of _____

A)scatter operation
B)recursion operation
C)execution
D)none

Question 13

Similar communication pattern to all-to-all broadcast except in the_____

A)reverse order
B)parallel order
C)straight order
D)vertical order

Question 14

Group communication operations are built using which primitives?

A)one to all
B)all to all
C)point to point
D)none of these

Question 15

___ can be performed in an identical fashion by inverting the process.

A)recursive doubling
B)reduction
C)broadcast
D)none of these

Question 16

Broadcast and reduction operations on a mesh is performed

A)along the rows
B)along the columns
C)both a and b concurrently
D)none of these

Question 17

Cost Analysis on a ring is

A)(ts + twm)(p - 1)
B)(ts - twm)(p + 1)
C)(tw + tsm)(p - 1)
D)(tw - tsm)(p + 1)

Question 18

Cost Analysis on a mesh is

A)2ts(sqrt(p) + 1) + twm(p - 1)
B)2tw(sqrt(p) + 1) + tsm(p - 1)
C)2tw(sqrt(p) - 1) + tsm(p - 1)
D)2ts(sqrt(p) - 1) + twm(p - 1)

Question 19

Communication between two directly link nodes

A)cut-through routing
B)store-and-forward routing
C)nearest neighbour communication
D)none

Question 20

All-to-one communication (reduction) is the dual of ______ broadcast.

A)all-to-all
B)one-to-all
C)one-to-one
D)all-to-one

Question 21

Which is known as Reduction?

A)all-to-one
B)all-to-all
C)one-to-one
D)one-to-all

Question 22

Which is known as Broadcast?

A)one-to-one
B)one-to-all
C)all-to-all
D)all-to-one

Question 23

The dual of all-to-all broadcast is

A)all-to-all reduction
B)all-to-one reduction
C)both
D)none

Question 24

All-to-all broadcast algorithm for the 2D mesh is based on the

A)linear array algorithm
B)ring algorithm
C)both
D)none

Question 25

In the first phase of 2D Mesh All to All, the message size is ___

A)p
B)m*sqrt(p)
C)m
D)p*sqrt(m)