To start designing algorithms for a cluster or a supercomputer,
you're going to need a machine model.
How about this one?
In this model,
a machine is a collection of nodes connected by some kind of network.
Each node consists of a processor connected to a private memory.
By private, I mean that the node can only directly read or
write its own memory.
It can't directly access the memory of other nodes.
I'll refer to this type of machine as a Distributed Memory machine.
Now this abstraction of private memories is critical.
It implies that to share data,
nodes will have to send messages to one another.
So for example, suppose this node wants to send data to this node.
The only way to do that is the sender or
source has to package up a message and then put it on the network.
So this message will have to find some path through the network to get
from the source node to the destination node.
In contrast to shared memory where we read and write shared variables,
this style of parallel communication is called message-passing.
Now this machine model has a few simple rules.
The zeroth rule of the model is you never talk about the model.
By that I mean, you need to master and internalize these rules.
Okay, so what are the real rules?
The first rule is that you should assume the network is fully connected.
That means there's always a path from any node to any other node in
the network.
The second rule is that the network links are bi-directional.
What does that mean?
Well, suppose I have two nodes in the machine, and
they're connected by a link.
Bi-directional means that the link can carry a message in
both directions at the same time.
So, while one message is going this way, another message can be going this way.
The third rule is that you will allow a node to concurrently perform at most,
1 send and 1 receive at a time.
This rule is important because it effects the cost of communication.
So for example suppose this node wants to send the message on
each of its outgoing links.
In order for this node to send four messages it's going to have to send them
one at a time by contrast it could do one send and one receive simultaneously.
The fourth rule is about the cost of a simultaneous send and
receive of n words.
So suppose this our computer, and
let's further supposed that this node wants to send a message to this node.
There are several different paths, here is one path and here's another.
Regardless of which path the message takes,
rule number four says the following.
The time to send the message if it contains n words, is
a constant alpha plus another constant beta times the size of the message.
In other words, the cost of sending the message is linear in the message size.
Now, it may seem strange that this cost, somehow,
is independent of the path that's taken.
Now, that's not entirely true.
And I'll clarify a little bit later in the lesson.
For the time being, let's accept the formula, as stated.
Now, the formula has two terms.
The first term is called the latency, and it has units of time.
It's a fixed cost that you pay no matter how large the message is.
The second term has a parameter beta.
Beta has a name.
We'll call it the inverse bandwidth.
It has units of time per word.
You'll think a little bit more about where this cost model really comes from
momentarily, so just sit tight.
One subtlety is, that this fourth rule really only applies when there
are no messages competing for links.
So we have a fifth rule which tells us what to do when
messages are trying to go over the same link, at the same time.
This situation is called congestion.
This rule says if there are k messages simultaneously competing for
a link, then in terms of the cost of the message,
will change only the beta term and in particular we'll multiply it by k.
For instance, let's consider this link that connects these two nodes.
The last rule governs what happens if two messages try
to go over the same link simultaneously.
So suppose there's a red message going this way and
a blue message going this way.
The last rule says that the effective cost of this operation is the same as if
the data transmission part, which is the beta term, is serialized over the link.
So if these two messages are being transmitted in parallel
Instead of observing a parallel execution time of alpha plus beta n,
supposing that the messages are the same size n.
What you'll see instead is a cost of alpha plus beta times n times 2.
Okay, so take a second to look at these rules and commit them to memory.