Memory-Hierarchy Tradeoffs - Models of Computation: Exploring the Power of Computing - page 539

We now derive an upper bound to Q . At the start of the pebbling of the middle interval

P t there are at most 2 S red pebbles on G ,atmost S original red pebbles plus S new red
pebbles. Clearly, the number of vertices that can be pebbled in the middle interval with first-
level pebbles is largest when all 2 S red pebbles on G are allowed to move freely. It follows
that at most ρ ( 2 S , G ) vertices can be pebbled with red pebbles in any interval. Since all
vertices must be pebbled with red pebbles, this completes the proof.

of

Combining Theorems 11.3.1 and 11.4.1 and a weak lower limit on the size of T ( L )
l

( p , G ) ,

we have the following explicit lower bounds to T ( L )
l

( p , G ) .

COROLLARY 11.4.1 In the standard MHG when T ( L )
l

( p , G ) ≥ β ( s l− 1 −

1 ) for β> 1 ,the

≤ l ≤ L :

following inequality holds for 2

β
β + 1

s l− 1
ρ ( 2 s l− 1 , G ) (

T ( L )
l

( p , G ) ≥ | V |−| In ( G ) | )

In the I/O-limited MHG when T ( L )
l

( p , G ) ≥ β ( s l− 1 −

1 ) for β> 1 , the following inequality

≤ l ≤ L :

holds for 2

β
β + 1

s L− 1
ρ ( 2 s L− 1 , G ) (

T ( L )
l

( p , G ) ≥ | V |−| In ( G ) | )

11.5 Tradeoffs Between Space and I/O Time
We now apply the Hong-Kung method to a variety of important problems including matrix-
vector multiplication, matrix-matrix multiplication, the fast Fourier transform, convolution,
and merging and permutation networks.

11.5.1 Matrix-Vector Product
We examine here the matrix-vector product function f ( n )
A

: R n 2 + n R n over a commutative

→

x

R

ring described in Section 6.2.1 primarily to illustrate the development of efficient multi-

level pebbling strategies. The lower bounds on I/O and computation time for this problem
are trivial to obtain. For the matrix-vector product, we assume that the graphs used are those
associated with inner products. The inner product u

· v of n -vectors u and v over a ring R

is defined by:

n

u · v = u i · v i

i = 1

The graph of a straight-line program to compute this inner product is given in Fig. 11.4 ,where
the additions of products are formed from left to right.
The matrix-vector product is defined here as the pebbling of a collection of inner product
graphs. As suggested in Fig. 11.4 , each inner product graph can be pebbled with three red
pebbles.

THEOREM 11.5.1 Let G be the graph of a straight-line program for the product of the matrix A
with the vector x .Let G be pebbled in the standard MHG with the resource vector p .Thereisa