# When analyzing a parallel algorithm, how do you take communication costs into account?

My question is related in spirit to "Is algorithmic analysis by flop counting obsolete?". Counting the number of computational operations in an algorithm is commonly used as a first-order model to aid in understanding the computational costs of an algorithm. However, the unit cost (in, say, time per operation) of data movement is greater than that of a processor cycle (see Peter Norvig's table of approximate timings for operations on a PC at this link). Is there any type of analysis for communication similar to the analysis done for computational operations? If not, is coding up an algorithm and running it the only (or most effective way) to determine the costs of communication?

• Do you mean "Can you do an $O(N^a)$ type analysis of communication costs?" If so, I think there is again the challenge—as mentioned in Norvig's table—of determining what kind of movement you're talking about, as I suspect that the prefactor is of huge importance here. Commented Jan 13, 2012 at 23:39
• Yes. I also suspect that the prefactor may be of huge importance here. I suspect the answer to this question is, "We know some strategies are bad because of personal experience," followed by lists of good and bad things. My experience with parallel computing is limited to a semester of a parallel computing class. I'd like to know how people who work on supercomputers figure out effective strategies for parallelism. I also suspect that GPU programming faces a similar hurdle with memory movement. Commented Jan 13, 2012 at 23:54
• For GPU computing, I think communication and memory accessing (the latter, of course, a big subject in the linked question) are equally important issues. Commented Jan 14, 2012 at 0:13
• Communication and memory access patterns are of fundamental importance when cosndiering GPUs as they work as co-procesing units. Either you move all data to reside on the GPUs to reduce the latency connected with transfers of data between a CPU (host) and a GPU (device) through a PCI express link. For algorithms with high arithmetic intensity (high flops/transfer rates) the GPUs can excel performance due to number of ALUs when operations are data-parallel. However, most algorithms would be memory bound algorithm because of the memory wall (increasing gap between processing speed and bandwidth) Commented Jan 14, 2012 at 8:50

## 4 Answers

It's fairly common to construct performance models of parallel codes that include FLOPS, memory bandwidth, and communications. A real world example of modelling performance of such a code is here, for the POP (v2) ocean code; it's just the first that came up in a google search. I've given a simple example of how it works in my answer to this question: How can I reduce the communication bottleneck of a parallel explicit finite difference scheme?

The communication part of these performance models generally count the number and size of messages, and use latency and bandwidth to estimate the time taken by point-to-point messages, with some logarithmic factor for collectives.

As with any modeling exercise, you can go nuts adding more terms to your model -- making communications on-node less expensive, and off-switch more expensive, including load imbalance, etc -- but even a fairly simple model gives you a fairly strong understanding of what is going on in your code, and allows you to quantitatively answer questions like "is infiniband vs. ethernet likely to make a difference for this simulation", etc.

As to your last question, "If not, is coding up an algorithm and running it the only (or most effective way) to determine the costs of communication?" -- experiment always trumps theory, of course, but theory can be a useful guide.

The Hockney model is an excellent simple model for communication: the time to send a single message of $m$ words from one process to another is

$$T(m) = \alpha + \beta m$$

where $\alpha$ is the so-called latency cost, and $\beta$ is the inverse bandwidth. Typically, the larger the machine, the larger $\alpha$ is. Clearly the Hockney model does not take into account more subtle issues like network congestion, but it's hard to stress exactly how much mileage one can get out of this model.

If you would like to see an analysis of various algorithms for MPI collective communication using the Hockney model, I highly recommend Collective Communication: Theory, Practice, and Experience. It discusses various algorithms for broadcast, reduce, scatter, gather, allgather, reduce-scatter, and allreduce on various network topologies.

This is a hard thing to do and there is nothing as general, well defined and powerful as complexity analysis that includes memory movement. Memory complexity is at least a start. Kung and others have done relevant work in this area (H. T. Kung. Memory requirements for balanced computer architectures. In Proceedings of the ACM Int’l. Symp. Computer Architecture (ISCA), Tokyo, Japan, 1986) and Jim Demmel's group at Berkeley has recently worked explicitly with complexity theory that include communication, but "memory movement " theory has far to go until it is as versatile as traditional complexity theory and analysis.

According to the book "Parallel Programming in C with MPI and OPENMP" (2004) by M.J. Quinn, you can think of parallel programs in the "task-channel" model. In it, the critical thing to understand is that "a task may only send one message at a time, but it can receive a message at the same time it is sending a message" (Quinn, 2004, pg 76). So, you only need to consider how many messages are sent simultaneously at each iteration. Also, communication is never instantaneous: there is always a latency period before even 1 bit is sent through a channel (think of it as though the processor needs to "warm up" before it can send a message). We can usually assume that this is a constant, independent of the message length. In general, we do not consider too many other "hardware-dependent" factors into the algorithm analysis such as bandwidth, network topology, or cache hit rate. This is part of the reason why a parallel implementation does not perform as predicted by the algorithm analysis. It is also not uncommon for programmers to not know these parameters about the machine they are testing their code on, which makes experimental testing much more convenient.