Information Technology Reference
In-Depth Information
This algorithm performs one input operation on each entry of a i , q and b q , j to compute
c i , j . It also performs one output operation per entry to compute c i , j itself. Summing over
all values of i and j ,wefindthat n 2 output operations are performed on entries in C .Since
there are ( n/r ) 2 submatrices a i , q and b q , j and each is used to compute n/r terms c u , v ,the
number of in put operations on entri es in A and B is 2 ( n/r ) 2 r 2 ( n/r )= 2 n 3 /r .Because
r =
S/ 3
S/ 3
,wehave r
1, from which the upper bound on the number of
I/O operations follows. Since each product and addition vertex in each inner product graph
is pebbled once, O ( n 3 ) computation steps are performed.
The bound on T ( 2 )
2
) for the I/O-limited game follows from two observations.
First, the computational inequality of Theorem 10.4.1 provides a lower bound to T I ,the
number of times that input vertices are pebbled in the red-pebble game when only red
pebbles are used on vertices. This is the I/O-limited model. Second, the lower bound of
Theorem 10.5.4 on T (actually, T I ) is of the form desired.
( S , G ,
P
These results and the strategy given for the two-level case carry over to the multi-level case,
although considerable care is needed to insure that the pebbling strategy does not fragment
memory and lead to inefficient upper bounds.
Even though the pebbling strategy given below is an I/O-limited strategy, it provides
bounds on time in terms of space that match the lower bounds for the standard MHG.
THEOREM 11.5.3 For every graph G in the family F n of inner product graphs for multiplying
two n
×
n matrices and for every pebbling strategy
P
for G in the standard MHG with resource
vector p that uses p 1
3 first-level pebbles, the computation and I/O time satisfy the following
lower bounds, where s l = j = 1 p j and k is the largest integer such that s k
3 n 2 :
)=Ω n 3
T ( L )
1
( p , G ,
P
)= Ω n 3 / s l− 1 for 2
l
k
T ( L )
l
( p , G ,
P
Ω n 2
for k + 1
l
L
P
for G with p 1
Furthermore, there is a pebbling strategy
3 such that the following upper bounds
hold simultaneously:
T ( L )
1
)= O ( n 3 )
( p , G ,
P
)= O n 3 / s l− 1 for 2
l
k
T ( L )
l
O n 2
( p , G ,
P
for k + 1
l
L
In the I/O-limited MHG the upper bounds given above apply. The following lower bound on the
I/O time applies to every graph G for n
×
n matrix multiplication and every pebbling strategy
P
,
where S = s L− 1 :
)=Ω n 3 / S for 1
T ( L )
l
( p , G ,
P
l
L
Proof The lower bounds on T ( L )
l
( p , G ,
P
) ,2
l
L , follow from Theorems 11.3.1 and
11.5.2 . The lower bound on T ( L )
1
( p , G ,
P
) follows from the fact that every graph in
F n
has Θ( n 3 ) vertices to be pebbled.
 
Search WWH ::




Custom Search