Information Technology Reference
In-Depth Information
11.5.2 Matrix-Matrix Multiplication
In this section we derive upper and lower bounds on exchanges between I/O time and space
for the n
n matrix multiplication problem in the standard and I/O-limited MHG. We show
that the lower bounds on computation and I/O time can be matched by efficient pebbling
strategies.
Lower bounds for the standard MHG are derived for the family
×
F n of inner product
graphs for n
n ma-
trices using just inner products to compute entries in the product matrix. (See Section 6.2.2 .)
We allow the additions in these inner products to be performed in any order.
The lower bounds on I/O time derived below for the I/O-limited MHG apply to all DAGs
for matrix multiplication. Since these DAGs include graphs other than the inner product trees
in
×
n matrix multiplication , namely, the set of graphs to multiply two n
×
F n , one might expect the lower bounds for the I/O-limited case to be smaller than those
derived for graphs in
F n . However, this is not the case, apparently because efficient pebbling
strategies for matrix multiplication perform I/O operations only on input and output vertices,
not on internal vertices. The situation is very different for the discrete Fourier transform, as
seen in the next section.
We derive results first for the red-blue pebble game, that is, the two-level MHG, and then
generalize them to the multi-level MHG. We begin by deriving an upper bound on the S -span
for the family of inner product matrix multiplication graphs.
LEMMA 11.5.1 For every graph G ∈F n the S -span ρ ( S , G ) satisfies the bound ρ ( S , G )
2 S 3 / 2 for S
n 2 .
Proof ρ ( S , G ) is the maximum number of vertices of G
∈F n that can be pebbled with
S red pebbles from an initial placement of these pebbles, maximized over all such initial
placements. Let A , B ,and C be n
×
n matrices with entries
{
a i , j }
{
b i , j }
{
c i , j }
,
,and
,
B .Theterm c i , j = k a i , k b k , j is
associated with the root vertex in of a unique inner product tree. Vertices in this tree are
either addition vertices, product vertices associated with terms of the form a i , k b k , j ,orinput
vertices associated with entries in the matrices A and B .Eachproductterm a i , k b k , j is
associated with a unique term c i , j and tree, as is each addition operator.
Consider an initial placement of S
i , j
n .Let C = A
×
respectively, where 1
n 2 pebbles of which r are in addition trees (they
are on addition or product vertices). Let the remaining S
r pebbles reside on input
vertices. Let p be the number of product vertices that can be pebbled from these pebbled
inputs. We show that at most p + r
1 additional pebble placements are possible from the
initial placement, giving a total of at most π = 2 p + r
1 pebble placements. (Figure 11.5
a 2,1 b 1,1 a 2,2 b 2,1
a 2,1 b 1,2 a 2,2 b 2,2
a 1,1 b 1,1 a 1,2 b 2,1
a 1,1 b 1,2 a 1,2 b 2,2
(b)
(d)
(a)
(c)
Figure 11.5 Graph of the inner products used to form the product of two 2 × 2matrices.
(Common input vertices are repeated for clarity.)
 
Search WWH ::




Custom Search