CS 5220

Applications of Parallel Computers

Intro to Message Passing

Please click the play button below.

Plan for this week

This week: distributed memory
- HW issues (topologies, cost models)
- Message-passing concepts and MPI
- Some simple examples
Next week: shared memory (and PGAS?)

The plan this week is to talk about message passing generally in this deck, and how it is supported in hardware. Then we'll talk a little bit about MPI programming in the next deck. Then we'll talk next week about shared memory programming in OpenMP.

I know I said this last week, but I think there's some pedagogical value to thinking about the message passing style of programming before thinking about shared memory. That's because the types of things you have to think about to get high-performance shared memory codes are often the same types of things you have to think through to get high-performance message passing codes. It's just that with MPI, you're forced into it in a way that you aren't always with OpenMP.

There are other types of programming models out there, too, things that sit somewhere between traditional message-passing and traditional shared memory. For that matter, MPI sometimes sits somewhere between those two traditions, thanks to the features in MPI-3! Anyhow, I hope to do something with one of the Parallel Global Address Space (PGAS) languages or libraries, too.

But for today: message passing!

Basic questions

How much does a message cost?

Latency: time to get between processors
Bandwidth: data transferred per unit time
How does contention affect communication?

This is a combined hardware-software question!

We want to understand just enough for reasonable modeling.

One of the basic questions in designing message-passing code for performance is how much a message will cost. Remember, the time for a message in isolation is a latency cost (time to get out of the caller, through the processors, and to the other system) together with a bandwidth cost (time per byte during the transfer). So we need to understand enough about the network to get a sense for how to think about these two terms.

Of course, life is more complicated than that! Often, there are many messages traversing the network simultaneously, and so we have to worry about congestion effects - we can't always assume the effective bandwidth that one processor gets is always equal to the max bandwidth the network provides. Also, there are several pieces to latency: the time to make it across the network wires is one part, but there's also the time to get a message through the operating system and into the network in the first place. And we can try to use the processor for other work when there just happens to be data going across the wires, but maybe not when the CPU is busy with the overhead to initiate the message. So maybe this is something that we should consider, too.

The point here, though, is not to turn you into networking experts. It is to give you a rough sense of what's possible so that you can understand how to think about modeling the performance of your code.

Thinking about interconnects

Several features characterize an interconnect:

Topology: who do the wires connect?
Routing: how do we get from A to B?
Switching: circuits, store-and-forward?
Flow control: how do we manage limited resources?

Let's start by thinking about the network hardware: we call this the network, or the network fabric, or the interconnect, depending on who is doing the talking. Several features characterize the interconnect, down at the bottom level. First, there's the topology: how are the wires, nodes, and switches connected to each other? Then, there are the rules for routing the messages: do we use the same path for every packet from a given source to a given destination, or can it change? And is it a shortest path, or are there other policies that come into play? We also have to decide whether we are going to set up a circuit and communicate on it for a while - the way that the old phone connections used to work - or if we are going to break our messages into packets and send them in a store-and-forward fashion, which is what happens in lots of modern networks. And then, if there may be more traffic sometimes than the network can gracefully handle, we have to have flow control mechanisms that let us share the bandwidth resources of the network.

Thinking about interconnects

Links are like streets
Switches are like intersections
Hops are like blocks traveled
Routing algorithm is like a travel plan
Stop lights are like flow control
Short packets are like cars, long ones like buses?

At some point the analogy breaks down...

Bus topology

One set of wires (the bus)
Only one processor allowed at any given time
- Contention for the bus is an issue
Example: basic Ethernet, some SMPs

Let's start with the simplest possible case: a bus topology. A bus is one set of wires that everyone connects to. In general, only one processor is allowed to send on the bus at a time, though everyone connected to the bus can see the message. So figuring out how to deal with contention, or the case of multiple processors that want to send simultaneously, is a big issue with buses. In fact, it's such a big issue that we rarely find buses with lots of nodes. The original Ethernet systems used buses, but mostly we use switched Ethernet these days. There are, however, buses that connect processors to memory on most machines. There are also buses to connect processors to peripherals: after all, USB is short for Universal Serial Bus.

Crossbar

Dedicated path from every input to every output
- Takes $O(p^2)$ switches and wires!
Example: recent AMD/Intel multicore chips
(older: front-side bus)

Bus vs. crossbar

Crossbar: more hardware
Bus: more contention (less capacity?)
Generally seek happy medium
- Less contention than bus
- Less hardware than crossbar
- May give up one-hop routing

Other topologies

Network properties

Think about latency and bandwidth via two quantities:

Diameter: max distance between nodes
- Latency depends on distance (weakly?)
Bisection bandwidth: smallest BW cut to bisect
- Particularly key for all-to-all comm

We can get a long way in performance modeling by characterizing networks by two numbers: the network diameter, and the bisection bandwidth.

The network diameter is the maximum number of hops between nodes, and the latency is generally maximal along these maximal-length paths. So we can build a pessimistic model of latency with just this one number, though it's sometimes useful to have more details about the distances between pairs of nodes. For some networks, the latency is dominated by the software stacks at the endpoints anyhow; in that case, we hardly care about these distinctions. But it depends.

The bisection bandwidth is the amount of bandwidth that we'd need to cut in order to partition into two equal-size subsets of nodes. Bisection bandwidth tells us something about the limiting bandwidth we'd see in all-to-all communication patterns, which is pretty much the worst-case scenario for contention.

MANY networks

In a typical cluster

Ethernet, Infiniband, Myrinet
Buses within boxes?
Something between cores?

All with different behaviors.

Modeling picture

DO distinguish different networks
Otherwise, want simple perf models
- Hockney model ($\alpha$-$\beta$)
- LogP and company
- And many others

All models are wrong, but some are useful.
-- George E. P. Box

$\alpha$-$\beta$ model (Hockney 94)

Crudest model: $t_{\mathrm{comm}} = \alpha + \beta M$

$t_{\mathrm{comm}} =$ communication time
$\alpha =$ latency
$\beta =$ inverse bandwidth
$M =$ message size

Works pretty well for basic guidance!

Typically $\alpha \gg \beta \gg t_{\mathrm{flop}}$. More money on network, lower $\alpha$.

LogP model

Like $\alpha$-$\beta$, but includes CPU time on send/recv:

Latency: the usual
Overhead: CPU time to send/recv
Gap: min time between send/recv
P: number of processors

Assumes small messages (gap $\sim \beta$ for fixed message size).

A lot of communication models build off the so-called LogP model (also from a mid-90s paper). LogP is an acronym standing for latency, overhead, gap, and number of processors. The gap is something like a bandwidth cost for smallish fixed-size messages; the real difference between LogP and the Hockney model is that LogP distinguishes between the time that messages take "in the system" (without intervention from the sender or receiver processors) and the overhead time that the processors at the send or receive ends have to spend on dealing with the messages - making system calls, copying data between buffers, and so forth. So this tells us a little more about the potential for overlapping communication and computation, though we still have nothing in the model to describe bandwidth effects.

And many others

Recent survey lists 25 models!

More complexity, more parameters
Most miss some things (see Box quote)
Still useful for guidance!
Needs to go with experiments

Ping-pong

Process 0:

for i = 1:ntrials
  send b bytes to 1
  recv b bytes from 1
end

Process 1:

for i = 1:ntrials
  recv b bytes from 0
  send b bytes to 0
end

Laptop experiment

Open MPI on dual-core MacBook Air

Laptop ping-pong times

$\alpha = 0.485$ microseconds; $\beta = 0.215$ s/GB

Graphite experiment

Open MPI on old totient (now Graphite)

Two six-core chips per node, eight nodes
Heterogeneous network
- Crossbar between cores (?)
- Bus between chips
- Gig-E between nodes

Layout (P=24)

With --map-by core and --bind-to core

P 0-5: First chip, first node
P 6-11: Second chip, first node
P 12-17: First chip, second node
P 18-23: Second chip, second node

On chip (0-1)

$\alpha = 0.849$ microseconds; $\beta = 0.299$ s/GB

Cross chip (0-11)

$\alpha = 2.29$ microseconds; $\beta = 1.15$ s/GB

Cross node (0-23)

$\alpha = 63.1$ microseconds; $\beta = 1.99$ s/GB

Takeaways

Prefer larger to smaller messages (amortize latency, overhead)
More care with slower networks
Avoid communication when possible
- Great speedup for Monte Carlo and other embarrassingly parallel codes!
Overlap communication with computation
- Models tell roughly computation to mask comm
- Really want to measure, though

All right, what should you take away from this?

First, message latencies are big, particularly for networks like Ethernet. if we don't want all our time to go to latency, we had better not send too many messages. As we discussed when talking about PDE solvers, a few bigger messages might be preferable to a larger number of smaller messages, even when we might need some redundant work in the former case. We can make pleasingly parallel codes fast because we don't need much communication, but we aren't always that lucky.

Second, we'd really like to overlap communication with computation when we can. A fairly rough model can tell us about how much work we have to have between messages in order to mask as much of the message cost as we possibly can - remember, there may be overhead costs that we just can't overlap. Even if we believe our models - and it isn't always wise to take them too seriously - an experiment or two is often worthwhile to try to sort out these types of effects.