Distributed Memory Models

Question 1

What is the Private Memory Model?

Answer 1

A system of individual nodes with their own memory that other nodes
cannot directly access

Question 2

How do we get information from one node’s private memory to another’s?

Answer 2

Message Passing

Question 3

What are the 5 rules of the Private Memory Model?

Answer 3

Rule 1: Network is fully connected.

Rule 2: Link are bidirectional, i.e., can carry messages in BOTH directions at the same time

Rule 3: Nodes can send one message at a time, or receive one at a time (but they can send and receive one each at the same time)

Rule 4: The cost to send/receive n words, with no congestion, is T(n) = alpha + beta*n, where alpha is latency and beta is “inverse bandwidth” (time/word)

Rule 5: k-way congestion reduces bandwidth: T(n) = alpha + betank, where k is the number of nodes competing for the same link

Question 4

How do you calculate the time for pipelined message delivery?

Answer 4

t(n) = a + t(P-2) + tn, where

• a is software overhead for prepping message
• tn is time due to message size
• t(P-2) is the wire delay of message traveling over network
• t is time per link
• n is still number of words
• P is number of nodes traversed

Question 5

What is the wire delay of a message traveling over a network?

Answer 5

t(P-2), where P is the number of nodes traversed

Question 6

What is the cost to send/receive n words with no congestion?

Answer 6

T(n) = alpha + beta*n, where:

alpha = latency
beta = inverse bandwidth (time/word)

Question 7

What is the cost to send/receive n words WITH congestion (at least two messages competing for the same link, going in the same direction)

Answer 7

T(n) = alpha + betank, where:

alpha = latency
beta = inverse bandwidth (time/word)
k = number of nodes competing for the same link