Communication lower bounds for distributed-memory matrix multiplication.
We present lower bounds on the amount of communication that matrix multiplication algorithms must perform on a distributed-memory parallel computer. We denote the number of processors by <i>P</i> and the dimension of square matrices by <i>n</i>. We show that the most widely used class of algorithms, the so-called two-dimensional (2D) algorithms, are optimal, in the sense that in any algorithm that only uses <i>O</i>(<i>n</i><sup>2</sup>/<i>P</i>) words of memory per processor, at least one processor must send or receive (<i>n</i><sup>2</sup>/<i>P</i><sup>1/2</sup>) words. We also show that algorithms from another class, the so-called three-dimensional (3D) algorithms, are also optimal. These algorithms use replication to reduce communication. We show that in any algorithm that uses <i>O</i>(<i>n</i><sup>2</sup>/<i>P</i><sup>2/3</sup>) words of memory per processor, at least one processor must send or receive (<i>n</i><sup>2</sup>/<i>P</i><sup>2/3</sup>) words. Furthermore, we show a continuous tradeoff between the size of local memories and the amount of communication that must be performed. The 2D and 3D bounds are essentially instantiations of this tradeoff. We also show that if the input is distributed across the local memories of multiple nodes without replication, then (<i>n</i><sup>2</sup>) words must cross any bisection cut of the machine. All our bounds apply only to conventional (<i>n</i><sup>3</sup>) algorithms. They do not apply to Strassen's algorithm or other <i>o</i>(<i>n</i><sup>3</sup>) algorithms.
INTRODUCTION
Although communication is a bottleneck in many computations running on distributed-memory
parallel computers and on clusters of workstations or servers, few communication
lower bounds have been proved. We know a great deal about the amount
of communication that specic algorithms perform, but we know little about how
much communication they must perform.
We present lower bounds on the amount of communication that is required to
multiply matrices by a conventional algorithm on a distributed-memory parallel
computer. The analysis uses a unied framework that also applies to the analysis
of capacity cache misses in a sequential matrix-multiplication algorithm.
We use a simple yet realistic computational model to prove the lower bounds. We
model a parallel computer as a collection of P processor-memory nodes connected
by a communication network. That is, all the memory is distributed among the
nodes, which can communicate across a network. Our analysis bounds the number
of words that must be sent and received by at least one of the nodes. The bounds
apply even if a processor-memory node includes several processors, which is fairly
common today in machines ranging from clusters of dual-processor workstations to
SGI Origin 2000 and IBM SP.
Aggarwal, Chandra, and Snir [5] presented lower bounds on the amount of communication
in matrix multiplication and a number of other computations. Their
bounds, however, assume a shared-memory computational model that does not
model well existing computers. Their LPRAM model assumes that P processors,
each with a private cache, are connected to a large shared memory. Furthermore, it
is assumed that when a computation begins, the caches are empty, and that when
the computation ends, the output must be returned to the main memory. The analysis
bounds the amount of data that must be transferred between the shared main
memory and the private caches. This bound for matrix multiplication essentially
quanties the number of compulsory and capacity cache misses in a shared-memory
multiprocessor. The LPRAM model does not model well systems in which all the
memory is physically distributed among processing nodes, e.g. clusters of worksta-
tions, or parallel computers such as SGI Origin 2000 and IBM SP.
This distinction between the LPRAM model and our model is highly relevant
to matrix multiplication lower bounds. Matrix multiplication is nearly always a
subroutine in a larger computation. In a distributed memory machine, the mul-
tiplicands are already distributed in some manner when the matrix multiplication
subroutine is called, and the product must be left distributed in the processors' local
memories when it returns. Thus, the LPRAM bound, which essentially shows that
each processor must
access
is irrelevant to distributed-memory
machines, since these elements may already reside in the processor's mem-
ory. The LPRAM lower bound does not depend on the amount of local memory;
if data is allowed to be stored and perhaps replicated in local memories when the
computation begins and ends, no communication may be necessary at all.
In contrast, our lower bounds allow any initial data distribution of the input ma-
trices, including data distributions that replicate input elements, as 3D algorithms
do. That is, our lower bounds do not even count the communication necessary to
perform the replication of input elements! (Except in Section 6 where we explicitly
forbid replication to analyze the communication across a bisection of the machine.)
That is, the lower bounds hold even when data is allowed to be replicated prior
to the invocation of the algorithm. Our bounds also allow any distribution of
We use standard asymptotic notation in this paper. More specically, we use the denitions
of [10]: (g(n)) is the set of functions f(n) such that there exist positive constants c 1 , c 2 , and
such that 0  c 1 g(n)  f(n)  c 2 g(n) for all n  n 0
; O(g(n)) is dened similarly using the
weaker condition 0  f(n)  c 2 g(n);
g(n)) is dened with the condition 0  c 1 g(n)  f(n).
The set o(g(n)) consists of functions f(n) such that for any c 2 > 0 there exists a constant n 0 > 0
such that 0  f(n)  c 2 g(n) for all n  n 0 .
COMMUNICATION LOWER BOUNDS FOR MATRIX MULTIPLICATION 5
the output matrix C. The only constraint that we place on the algorithm is that
upon completion, every element of C must reside in some processor's local memory
(possibly several).
We state and prove lower bounds in this paper using concrete constants rather
than asymptotic notation. We do so since in most of the bounds the amount of
communication depends on three parameters: the size of the matrices n, the number
of processors P , and the size of the local memory M . Asymptotic notation makes
it less clear which of the parameters must grow in order for the function to show its
asymptotic behavior. Also, the use of concrete constants claries the dependence of
the amount of communication on each of the three parameters. The constants that
appear in the statement of lemmas and theorems, however, were chosen to make
the proofs as simple as possible; they were not chosen to be as tight as possible.
Some of our bounds assume that the matrices involved are square, whereas others
apply to matrices of any shape. We restrict matrices to a square shape where we
feel that bounds for rectangular matrices would complicate the statement of the
results or the proofs unnecessarily.
Our analysis applies only to conventional matrix multiplication algorithms. It
does not apply to Strassen's algorithm [32] or other o(n 3 ) algorithms. Lower bounds
on the communication complexity of Strassen's and other non-conventional algorithms
are beyond the scope of this paper.
The rest of the paper is organized as follows. Section 2 presents a technical
tool that underlies our unied approach to communication and cache-tra-c
lower bounds. Section 3 presents the basic memory-communication tradeo that
shows that lack of memory increases communication. Section 4 uses this provable
tradeo to analyze so-called two-dimensional (2D) matrix-multiplication algorithms
[1, 9, 12, 13, 37]. These algorithms only use (n 2 =P ) words of memory per
processor, just a constant factor more than required to store the input and output
(some of these algorithms only use (3 words per processor, which
6 DROR IRONY, SIVAN TOLEDO AND ALEXANDER TISKIN
is the minimal amount required to store the input and output without compres-
sion). We show that the amount of communication that they perform per processor,
asymptotically optimal for this amount of memory. Section 5 uses
a more sophisticated argument to show that so-called three-dimensional (3D) algorithms
are also optimal. 3D algorithms [1, 5, 6, 12, 14, 19] replicate the input
matrices need (n words of memory per processor.
This allows them to reduce the amount of communication to only (n 2 =P 2=3 ) per
processor. We show that this amount of communication is optimal for the amount
of memory that is used. The argument in this case is somewhat more complex
since the continuous tradeo that we prove in Section 3 does not apply when the
amount of local memory per processor is more than n 2 =(2P 2=3 ). In Section 6, we
prove that if no replication of input elements is allowed,
then
must
cross the bisection of the machine. Finally, in Section 7 we use the basic lemma
that underlies all of our results to prove a well-known lower bound on the number
of cache misses (sometimes referred to as page faults or I/O's in the lower-bounds
literature). The main point of Section 7 is to show how other kinds of lower bounds
can be derived using our unied approach, and how the I/O and communication
lower bounds are related.
2. THE BASIC LEMMA
This section presents the technical lemma that underlies all the lower bounds in
this paper. The lemma shows that a processor that accesses at most N elements
of A, at most N elements of B, and contributes to the computation of at most N
elements of the product can perform at most O(N 3=2 ) useful arithmetic
operations.
Hong and Kung [17] proved a weaker form of this lemma. Their lemma only
considers access to elements of A and B, not to contributions to elements of C, so
it is too weak to be used in the proofs of our distributed-memory lower bounds.
COMMUNICATION LOWER BOUNDS FOR MATRIX MULTIPLICATION 7
Also, Hong and Kung stated their result using asymptotic notation, whereas we
state and prove ours using concrete constants. Formally, they proved the following
lemma (we dene the formal matrix-multiplication model below; Hong and Kung
used a similar directed-acyclic-graph model):
Lemma 2.1 (Hong and Kung [17]). Consider the conventional matrix multiplication
and C is m r. A processor with
a local memory (cache) of size M words must read and write at
least
words to and from secondary memory to compute the product.
Before we state and prove our lemma, we must dene precisely the kind of algorithms
that it applies to. Informally, we want to deal with algorithms that only
use element addition and multiplication, and that compute each element c ik as an
explicit sum of products a ij b jk . Thus, we rule out e.g. Strassen's algorithm [32],
which saves on computation by using element subtraction. Furthermore, we must
assume that no other computation involving values a ij , b jk , c ik is taking place.
Thus, we rule out e.g. the Boolean matrix multiplication algorithm of [33], which
does compute explicit sums, but still saves on communication and memory by using
an intermediate \compact" representation of the matrices.
Definition 2.1. Conventional matrix multiplication
B is n  r, and C is m r, is dened by a directed acyclic graph (dag) with
mn+ nr input nodes representing the elements a ij , b jk of matrices A, B;
mr output nodes representing the elements c ik of matrix C;
mnr computation nodes representing the elementary multiplications v
The arcs represent data dependencies; in particular, the input nodes have unbounded
outdegree (corresponding to the replication of inputs), and the output
nodes have unbounded indegree (corresponding to the combining of partial sums
into outputs). Thus, our denition covers a whole class of algorithms, which may
perform replication and combining in dierent order.
We are now ready to prove the basic lemma. Note that it holds for matrices of
any shape, as long as the shapes allow multiplication.
Lemma 2.2. Consider the conventional matrix multiplication
is mn, B is n  r, and C is m r. A processor that contributes to NC elements
of C and accesses NA elements of A and NB elements of B can perform at most
multiplications.
Proof. The lemma is an immediate corollary of the discrete Loomis{Whitney
inequality [26, 15, 8], which relates the cardinality of a nite set in Z D with cardinalities
of its d-dimensional orthogonal projections, 1  d  D. The application
of the discrete Loomis{Whitney inequality to matrix-multiplication lower bounds
was suggested by Paterson [29] (see also [34]).
2. Let V be a nite set of points in Z 3 , and let VA , VB ,
VC be the orthogonal projections of V onto the coordinate planes. The discrete
Loomis{Whitney inequality states that
In our notation, the number of elementary multiplications performed by the processor
is therefore at most (NANBNC ) 1=2 .
Lemma 2.2 is our main tool in proving communication lower bounds. In fact,
it is so important, that we would like to restate it in a dierent form. The new
COMMUNICATION LOWER BOUNDS FOR MATRIX MULTIPLICATION 9
version is slightly weaker than Lemma 2.2, but allows a more direct proof, which
we feel may benet the reader.
Lemma 2.3. Under the assumptions of Lemma 2.2, a processor can perform at
most
min
elementary multiplications.
Proof. The statement follows from Lemma 2.2 by the arithmetic-geometric mean
inequality. We now give an alternative, direct proof, based on an idea similar to
[17].
We denote by SA the set of elements (index pairs) of A that the processor accesses,
by SB the set of elements of B that the processor accesses, and by SC the set of
elements of C that the processor contributes to.
We rst show that (NB +NC ) N 1=2
A bounds the number of elementary multipli-
cations. We partition the rows of A into two sets: the set MA contains the rows of
A with at least N 1=2
A elements in SA and FA contains the rest of the rows. There
are at most N 1=2
A rows in MA .
Since each row of C is a product of the corresponding row in A and all of B,
there can be at most NBN 1=2
A elementary multiplications involving rows in MA .
Since each element of C is a product of a row of A and a column of B and since
each row in FA has less than N 1=2
A elements in SA , there can be at most NCN 1=2
A
elementary multiplications involving rows in FA .
A similar argument shows that (NA +NC ) N 1=2
B bounds the number of elementary
multiplications. We partition the columns of B into a set MB , consisting of
columns with at least N 1=2
B elements in SB , and a set FB containing the rest of the
columns.
Since each column of C is a product of A and the corresponding column of B,
there can be at most NAN 1=2
elementary multiplications involving columns in MB .
Since each element of C is a product of a row of A and a column of B, there can
be at most NCN 1=2
elementary multiplications involving rows in FB .
Finally, we show that (NA +NB ) N 1=2
C bounds the number of elementary mul-
tiplications. We partition the rows of C into a sets MC and FC as we did for
A.
Each row of C is a product of a row of A and all of B, so there can be at most
C elementary multiplications involving rows in MC . An element of A is used
in the computation of elements from one row of C. If that row of C contains less
than N 1=2
C elements in SC , then the element of A us used in less than N 1=2
cations. Hence, the number of elementary multiplications involving rows of C in FC
is less than NAN 1=2
C .
3. THE MEMORY-COMMUNICATION TRADEOFF
In this section, we prove a tradeo between memory and communication in matrix
multiplication algorithms. The analysis shows that reducing the amount of
memory forces an algorithm to perform more communication. We shall use this
provable tradeo in the next section to prove that 2D matrix-multiplication algorithms
are asymptotically optimal for the amount of memory that they use. These
algorithms use little extra memory beyond the storage required to store the matri-
ces, and hence, they lie at an extreme end of the memory-communication tradeo.
In Section 5 we shall extend the tradeo to deal with larger memory sizes, which
will enable us to prove that 3D algorithms are also asymptotically optimal for the
amount of memory that they use.
Lemma 3.1. Consider the conventional matrix multiplication
is mn, B is n r, and C is m r, on a P -processor distributed-memory parallel
COMMUNICATION LOWER BOUNDS FOR MATRIX MULTIPLICATION 11
computer. Consider a processor that has M words of local memory and performs
elementary multiplications. The processor must send or receive at least
Wp
words.
Proof. We decompose the schedule of the computation on the processor into
phases. Phase ' begins when total number of words sent and received so far by the
processor is exactly 'M . Thus, in each phase, except perhaps the last phase, the
processor send and receives exactly M words.
The number NA of elements of A that the processor may access during a phase is
at most 2M , since each one of these elements must reside in the processor's memory
when the phase begins, or else it must have been received from another processor
during the phase. The same argument shows that NB  2M .
We dene an element c ik of the product C as live during a phase if: (1) the
processor computes a ij b jk for some j during the phase, and (2) a partial sum
containing a ij b jk either resides in the processor's memory at the end of the phase
or is sent to another processor during the phase. The number NC of live elements
of C during a phase is at most 2M , since each live element either uses one word of
memory at the end of the phase or it is sent to another processor.
Lemma 2.2 shows that the number of elementary multiplications during a phase
is at most (NANBNC ) 1=2  2
. The total number of elementary multiplications
in the algorithm is W . Therefore, the number of full phases (that is phases
in which exactly M words are sent and received) is at least
Wp
Wp
so the total amount of communication is at least
Wp
Wp
which concludes the proof.
Note that the above proof not only allows the input values a ij , b jk to be pre-
distributed in multiple copies in dierent processors' memories (\free" input replica-
tion), but also ignores the need to collect and add together all individual processors'
contributions to an output value c ik (\free" output combining). Also note that our
lower bound degenerates to zero when M  W 2=3 =2. This is inevitable, since the
communication can indeed be zero, e.g. when
all inputs and outputs t into local memory. More generally, when
the only communication required is input replication and output com-
bining, which are not accounted for in our proof. However, in the latter case we
have M  3W 2=3 , therefore our threshold on M is only a constant factor away from
the best achievable.
The lemma that we have just proved concentrates on a single processor. The next
theorem takes a more global view. The running time is typically determined by the
most heavily loaded processor. Therefore, by showing that at least one processor
must perform a lot of communication, we can derive a lower bound on the amount
of time that the whole algorithm must spend on communication.
Theorem 3.1. (Memory-Communication Tradeoff) Consider the conventional
matrix multiplication and C is
r, on a P -processor distributed-memory parallel computer with M words of
local memory per processor. The total number of words that are sent and received
by at least one processor is at least
Proof. At least one of the processors must perform mnr=P multiplications. The
result follows from applying Lemma 3.1 with
COMMUNICATION LOWER BOUNDS FOR MATRIX MULTIPLICATION 13
The above lower bound degenerates to zero e.g. when
4. A COMMUNICATION LOWER BOUND FOR
ALMOST-IN-PLACE ALGORITHMS
Among the many existing parallel matrix multiplication algorithms, the recent
algorithm by McColl and Tiskin [27] is, to our knowledge, the only one whose performance
matches asymptotically the lower bound in the memory-communication
tradeo for any value of M . However, two classes of earlier algorithms do match
the lower bounds for specic values of M . At one end of the spectrum, we have
the so-called 2D algorithms, that use little extra memory beyond that required to
store the matrices. At the other end of the spectrum, we have the so-called 3D
algorithms, that use extra memory to replicate the input matrices and reduce com-
munication. We now specialize Theorem 3.1 to 2D algorithms; Section 5 analyzes
algorithms that use extra memory.
The rst distributed-memory parallel matrix-multiplication algorithm is probably
the one due to Cannon [9]. Cannon originally proposed the algorithm for a parallel
computer with connected as a two-dimensional mesh. The
generalization of Cannon's algorithm to larger block-distributed matrices is due
to Dekel, Nassimi, and Sahni [12]. The algorithm has also been generalized to
hypercubes and other interconnection topologies. Fox, Otto and Hey [13] describe a
dierent algorithm which, unlike Cannon's algorithm, uses broadcasts. Another 2D
algorithm was proposed by Agarwal, Gustavson, and Zubair [3], and independently
and almost simultaneously by van de Geijn and Watts [37]. This algorithm, called
SUMMA, uses many broadcasts of relatively small matrix pieces, which allows the
broadcasts to be pipelined and to occur concurrently with the computation.
The storage required by 2D algorithms is proportional to the size of the matrices,
so for square matrices the amount of memory per processor should only be proportional
to n 2 =P . Clearly, 3n 2 =P words per processor are necessary just to store
14 DROR IRONY, SIVAN TOLEDO AND ALEXANDER TISKIN
the multiplicands and the product. Most 2D algorithms (e.g., SUMMA) only need
storage beyond the storage required for the matrices. Simpler
2D algorithms, such as blocked implementations of Cannon's algorithm, require
additional words per processor, in order to store two blocks of A and two
blocks of B. (This can be reduced to o(n 2 =P ) by breaking up each communication
phase into many small messages, possibly resulting in an increased communication
overhead.) The next theorem shows that 2D algorithms are asymptotically optimal
in the amount of communication per processor: any algorithm that only uses
words of memory per processor must
perform
per processor. In order to keep the theorem simple, we state and prove it for square
matrices.
Theorem 4.1. (2D Communication Lower Bound) Consider the conventional
multiplication of two n  n matrices on a P -processor distributed-memory
parallel computer, where each processor has n 2 =P words of local memory. If
then at least one of the processors must send or receive at least
words.
Proof. By Theorem 3.1, the amount of communication in at least one of the
processors is bounded from below by
COMMUNICATION LOWER BOUNDS FOR MATRIX MULTIPLICATION 15
The inequality relies on the fact that P 1=2  4
5. EXTENDING THE TRADEOFF TO M  n 2 =(2P 2=3 )
The tradeo of Section 3 fails to provide meaningful bounds when M  n 2 =(2P 2=3 ).
In this regime, there may not even be a single full phase, in the sense of the proof
of Lemma 3.1. Since the proof of Lemma 3.1 does not take into account either the
amount of communication in the last phase, or the communication necessary for
input replication and output combining, it provides no useful bound in this case.
This section analyzes the amount of communication that must be performed when
including the communication necessary for output combining
(but still not for input replication). We show that in this regime, the amount of
communication per processor is
This bound matches, asymptotically,
the upper bounds achieved by 3D algorithms. By using input replication, these
algorithms reduce communication over the more traditional 2D algorithms.
Although Dekel, Nassimi and Sahni [12] were perhaps the rst to propose 3D
algorithms, their algorithms are not communication-e-cient: the total number of
words that are communicated is (n 3 ). Communication-e-cient 3D algorithms
were rst proposed by Berntsen [6], and by Aggarwal, Chandra, and Snir [5] at
about the same time (Berntsen's paper was submitted for publication in 1988; the
paper by Aggarwal, Chandra and Snir was presented at a conference in 1988).
Essentially the same algorithm as in [5] was proposed again later, independently,
by Gupta and Kumar [14], and by Johnsson [19]. Berntsen's algorithm is somewhat
more complex than the rest.
Aggarwal, Chandra and Snir also prove an
on the amount of
communication per processor that matrix multiplication algorithms must perform
on a shared-memory parallel computer. As explained in the Introduction, their
bound does not apply to matrix multiplication on a distributed memory machine.
The bound relies on the private caches of the processors being empty when the
computation begins; in contrast, on a distributed-memory machine, the matrices
are typically already distributed when a matrix multiplication subroutine is invoked.
The main result of this section hinges on the following lemma.
Lemma 5.1. Consider the conventional multiplication of two n  n matrices on
a P -processor distributed-memory parallel computer. Consider a processor that has
words of local memory and performs at least n 3 =P elementary multipli-
cations. Let
For any
the processor must send or receive at least
words.
Proof. If NA  ( then the theorem statement holds, since only
elements of A can reside in the processor's local memory when the computation
begins, so the rest must be received from other processors. The same
argument holds when NB then the
theorem statement holds again, since the processor must send contributions to at
least -n 2 =P 2=3 elements of C to other processors.
If all of NA , NB , and NC are less than ( then we claim that all
three quantities must be greater than
COMMUNICATION LOWER BOUNDS FOR MATRIX MULTIPLICATION 17
Let W be the number of multiplications that the processor performs. Using Lemma 2.2
and its notation, we have
(1)
From (1) and the fact that both NA and NB are less than (
so
and therefore
An identical argument shows that the expression in (2) also bounds NA and NB .
The number of elements of C that the processor can compute on its own without
any contributions from other processors is small. For every such c ik , the processor
must access the entire ith row of A and the entire kth column of B. If NA and NB
are less than ( then the processor can compute at most
=n
=n
elements of C on its own.
Suppose that the processor participates in the computation of c ik but does not
compute it on its own. If c ik resides on our processor at the end of the computation,
then our processor must have received a contribution to c ik from at least one other
processor. If c ik resides on another processor, our processor must have sent its own
contribution to some other processor. Either way, one word of data must either be
received or sent for each such c ik .
Therefore, the processor must send or receive at least
words to participate in the computation of the elements of C (subtracting (3) from
(2)). By the hypotheses on P and -, we have
The rst two inequalities are true since -  . The third holds since P  128
which implies that P 2=3  which in turn implies that
This shows that the number of words that must be sent or received is at least
claimed.
We can now state the main result of this section. Its proof is essentially the same
as that of Theorem 3.1 and is omitted.
Theorem 5.1. (3D Communication Lower Bound) Consider the conventional
multiplication of two n  n matrices on a P -processor distributed-memory
parallel computer, where each processor has n 2 =P 2=3 words of local memory. For
any
at least one processor must send or receive at least
min
words.
COMMUNICATION LOWER BOUNDS FOR MATRIX MULTIPLICATION 19
6. BISECTION-BANDWIDTH BOUNDS
This section analyzes the amount of data that must cross the bisection of a
distributed-memory parallel computer. We partition the memory-processor nodes
into two subsets and establish a lower bound on the amount of data that must cross
any cut that separates the subsets in the communication network of the computer.
We assume that each element of the input matrices is stored exactly once in the
distributed memory of the machine, and that the input is evenly split between the
subsets. Indeed, if we allow replication of the input matrices, the output can be
computed without any communication across the bisection. For example, most 3D
algorithms perform no communication across some bisection cuts in the network
following the initial data replication phase.
Another way to derive lower bounds on the communication across cuts is to apply
the lower bounds in Section 4 and 5 to groups of processors. These bounds also
bound the amount of communication that a group of p processors must perform with
the other P p processors in the machine. This communication must be transmitted
on any edge cut in the communication network between the two processor groups.
Hence, we can bound the amount of communication that must traverse cuts in the
network.
This technique, however, is unlikely to provide useful bounds for large p (say
our general memory-communication tradeo degenerates when
and the more specialized bounds (Theorems 4.1 and 5.1) only hold for large P .
Therefore, we need a specic bound on the communication across bisection cuts.
The theorem below assumes that matrices A and B are evenly distributed. The
proof can be easily modied to show that the same asymptotic bounds also apply
when each of the two processor subsets initially stores at most n 2 elements of A
and n 2 elements of B, for any constant  < 1=
2. For   1=
2, a more complex
proof would be required.
Theorem 6.1. Consider the conventional multiplication of two n  n matrices
on a P -processor distributed-memory parallel computer, where each input element
is initially stored in the local memory of exactly one processor. At least
words must be transferred across any cut that splits the input distribution of the
multiplicands A and B evenly.
Proof. Let
Consider a cut in the communication network that splits the nodes into two subsets,
each holding exactly n 2 =2 elements of A and n 2 =2 elements of B.
If more than -n 2 elements of A or more than -n 2 elements of B are transferred
across the cut, the theorem statement holds. Otherwise, we claim that each subset
of the machine can compute at most
elements of C on its own (that is, by summing products a ij b jk that are all computed
locally). Computing each such element requires access to an entire row of A and
an entire column of B. If at most -n 2 elements of A and B cross the cut, each
subset has access to at most
=n rows of A and columns of B, so it can
compute at most
elements of C on its own.
Hence, the other
COMMUNICATION LOWER BOUNDS FOR MATRIX MULTIPLICATION 21
elements of C must be computed by the two subsets of the machine together, which
means that at least that many words must cross the cut. Since
13 3)=4, we
have so the theorem statement holds.
7. THE I/O LOWER BOUND
In this section, we use Lemma 2.2 to bound the number of compulsory and
capacity cache misses in matrix multiplication. We establish a lower bound on the
number of words that must be transferred between a slow memory and a fast cache,
when arithmetic instructions can only access data in the cache.
The results themselves are not new, but they show how the proof technique
that we use for the parallel communication bounds can be applied to the analysis
of cache misses. Specically, the bounds that we prove here are asymptotically
the same as those proved by Hong and Kung [17] and again by Toledo [36]. Our
bounds, however, specify constants, unlike Hong and Kung's result which is stated
using asymptotic notation. The constants here are slightly stronger than those
given in [36], but the proof technique is similar. In eect, we are using Toledo's
proof technique but the use of Lemma 2.2 simplies the structure of the proof.
The lower bounds use a lax memory-system model that is equivalent to Hong
and Kung's red-blue pebble game. Therefore, they apply to any cache organiza-
tion. The lower bounds also match, asymptotically, the performance of recursive
matrix multiplication and of blocked matrix multiplication, assuming that the block
size is chosen appropriately and the cache is fully associative and uses the LRU replacement
policy.
Matrix multiplication algorithms whose asymptotic performance matches our
lower bound are as old as computers. Rutledge and Rubinstein [31, 30] described
the library of blocked matrix subroutines that they designed (together with Herbert
F. Mitchell) and implemented for the UNIVAC, a rst-generation computer
22 DROR IRONY, SIVAN TOLEDO AND ALEXANDER TISKIN
that became operational in 1952. McKeller and Coman [28] provided the rst
rigorous analysis of data reuse in matrix computations, including matrix multipli-
cations. They showed that blocked algorithms transferred fewer words between fast
and slow memory than algorithms that operated by row or by column. High-quality
implementations of I/O-e-cient matrix-multiplication algorithms are widely available
and frequently used [4, 2, 7, 11, 16, 20, 23, 21, 22, 24, 25, 38]
The proof of the next theorem is very similar to the proof of Lemma 3.1.
Theorem 7.1. Consider the conventional multiplication of two n  n matrices
on a computer with a large slow memory and a fast cache that can contain M words.
Arithmetic operations can only be performed on words that are in the cache. The
number of words that are moved between the slow memory and the fast cache is at
least
Proof. We decompose the schedule of the computation into phases. Phase '
begins when total number of words moved between the memory and the cache is
exactly 'M . Thus, in each phase, except perhaps the last phase, exactly M words
are transferred between the memory and the cache.
The number NA of elements of A that the processor may operate upon during
a phase is at most 2M , since each one of these elements must either reside in the
cache when the phase begins, or it must be read into the cache during the phase.
The same argument shows that NB  2M .
We dene an element c ik of the product C as live during a phase if the processor
computes a ij b jk for some k during the phase and if a partial sum containing a ij b jk
either resides in the cache at the end of the phase or is written to slow memory
during the phase. The number NC of live elements of C during a phase is at most
COMMUNICATION LOWER BOUNDS FOR MATRIX MULTIPLICATION 23
2M , since each live element either uses one word of cache at the end of the phase,
or is written to slow memory.
Lemma 2.2 shows that the number of elementary multiplications during a phase
is at most (NANBNC ) 1=2  2
. The total number of elementary multiplications
in the algorithm is n 3 . Therefore, the number of full phases (that is, phases
in which exactly M words are transferred) is at least
so the total number of words transferred is at least
which concludes the proof.
The next corollary shows that when the matrices are several times larger than
the cache, the number of cache misses is proportional to n 3 =M 1=2 . The constants
in the corollary are essentially an example; by picking a stronger bound on the size
of the matrices relative to the cache we could have proved a stronger bound on the
number of cache misses.
Corollary 7.1. (The I/O Lower Bound [17]) Under the conditions of Theorem
7.1, and assuming that M  n
the number of words that
must be transferred to and from the cache is at least
Proof. If M  n
32, so the number of words that must
be transferred is at least
n 2pD R A F T February 2, 2004
8. CONCLUSIONS
We have presented rigorous lower bounds on the amount of communication that
distributed-memory parallel matrix multiplication algorithms must perform. Our
bounds hold under a directed-acyclic-graph (dag) model of conventional matrix
multiplication with n-ary summation (that is, the dag allows summation in any
order). The bounds do not hold for o(n 3 ) matrix multiplication algorithms, such as
Strassen's, and they do not hold for cases where arbitrary computation on matrix
elements is allowed, even if all elementary products are computed explicitly.
The main signicance of our results is that they rigorously validate what most
algorithm-designers have long suspected: that 2D algorithms are asymptotically
optimal when little or no replication is allowed and that 3D algorithms are asymptotically
optimal when replication is allowed. Therefore, the search for more e-cient
algorithms must now concentrate on improving the constants involved and on eorts
to design non-conventional algorithms for specic domains which use compression
and other non-dag techniques.
Another important conclusion from this research is that 3D algorithms are somewhat
unlikely to become competitive. Our bounds show that the asymptotic reduction
in communication, relative to 2D algorithms, cannot exceed a factor of P 1=6 .
For typical machine sizes, this value is unlikely to be high enough to make replication
protable. We note that although some authors have found that 3D algorithms
are faster than 2D algorithms in practice [1], nearly all of the widely used existing
COMMUNICATION LOWER BOUNDS FOR MATRIX MULTIPLICATION 25
libraries implement 2D algorithms. We also note that an eort by the rst two
authors to design a 3D factorization algorithm suggested that the constants in the
3D algorithm were too high (the constants are higher for triangular factorization
than they are for matrix multiplication) [18].

Acknowledgments

. Thanks to the two anonymous referees for helpful comments
and suggestions. Sivan Toledo was supported in part by an IBM Faculty Partnership
Award and by grants 572/00 and 9060/99 from the Israel Science Foundation
(founded by the Israel Academy of Sciences and Humanities).



--R

A three-dimensional approach to parallel matrix multiplication
Exploiting functional parallelism of POWER2 to design high-performance numerical algorithms

Improving performance of linear algebra algorithms for dense matrices using algorithmic prefetch.
Communication complexity of PRAMs.
Communication e-cient matrix multiplication on hypercubes
Optimizing matrix multiply using PHIPAC: a portable
Geometric Inequalities.
A Cellular Computer to Implement the Kalman


Parallel matrix and graph algorithms.
Matrix algorithms on a hypercube.
The scalability of matrix multiplication algorithms on parallel computers.

The performance of the Intel TFLOPS supercomputer.
I/O complexity: the red-blue pebble game
Trading replication for communication in parallel distributed-memory dense solvers
Minimizing the communication time for matrix multiplication on mul- tiprocessors
Local basic linear algebra subroutines (LBLAS) for the Connection Machine system CM-200




Local basic linear algebra subroutines (LBLAS) for the CM-5/5E
An inequality related to the isoperimetric inequality.


Private communication
High order matrix computation on the UNIVAC.
Matrix algebra programs for the UNIVAC.
Gaussian elimination is not optimal.

The bulk-synchronous parallel random access machine

A survey of out-of-core algorithms in numerical linear algebra
Robert van de Geijn and Jerrell Watts.
Automatically tuned linear algebra software.
--TR
Communication complexity of PRAMs
Minimizing the communication time for matrix multiplication on multiprocessors
Improving performance of linear algebra algorithms for dense matrices, using algorithmic prefetch
Exploiting functional parallelism of POWER2 to design high-performance numerical algorithms
A high-performance matrix-multiplication algorithm on a distributed-memory parallel computer, using overlapped communication
A three-dimensional approach to parallel matrix multiplication
Optimizing matrix multiply using PHiPAC
The bulk-synchronous parallel random access machine
A survey of out-of-core algorithms in numerical linear algebra
Organizing matrices and matrix operations for paged memory systems
Introduction to Algorithms
High order matrix computations on the UNIVAC
Bulk-Synchronous Parallel Multiplication of Boolean Matrices
I/O complexity
Automatically Tuned Linear Algebra Software
A cellular computer to implement the kalman filter algorithm
communication;lower bounds;distributed memory;matrix multiplication