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

which the upper bounds are simultaneously satisfied:

⎧
⎨ Θ( n log n ) l = 1

Θ n log n

log s l − 1 2

T ( L )
l

( p , F ( d ) , P )= ≤ l ≤ k

⎩

Θ( n ) k + 1 ≤ l ≤ L

Proof Proofs of the first two lower bounds follow from Lemma 11.3.1 and Theorem 11.5.4 .
The third follows from the fact that pebbles at every level must be placed on each input and
output vertex but no intermediate vertex. We now exhibit a pebbling strategy giving upper
bounds that match (up to a multiplicative factor) these lower bounds for all 1

≤ l ≤ L .

(See Fig. 11.9 .)
We define a non-decreasing sequence d =( d 0 , d 1 , d 2 , ... , d L− 1 ) of integers used be-
low to describe an efficient multi-level pebbling strategy for F ( d ) .Let d 0 = 1and d 1 =

log( s 1 −

1 )

≥

1, where s 1 = p 1 ≥ 3. Define m r and d r

≤ r ≤ L −

for 2 1by

m r =

log min( s r − 1, n )

d r− 1

d r = m r d r− 1

2 d r + 1when s r ≤ It follows that s r ≥ n + 1since a b/a ≤ b .Because log a ≥

(log a ) / 2when a ≥ 1andalso a b/a ≥ b/ 2forintegers a and b when 1 ≤ a ≤ b (see

Problem 11.1 ), it follows that d r ≥ log(min( s r − 1, n )) / 4. The values d l are chosen to

avoid memory fragmentation.
Before describing our pebbling strategy, note that because we assume at least one pebble
is available at each level in the hierarchy, it is possible to perform an I/O operation at each
level. Also, pebbles at levels less than l can be used as though they were at level l .
Our pebbling strategy is based on the decomposition of F ( d ) into FFT subgraphs F ( d k ) ,
each of which is decomposed into FFT subgraphs F ( d k − 1 ) , and so on, until reaching FFT
subgraphs F ( 1 ) that are two-input, two-output butterfly graphs. To pebble F ( d ) we apply
the strategy described in the proof of Theorem 11.5.4 as follows. We decompose F ( 2 )
into d 2 /d 1 stages, each containing 2 d 2 −d 1 copies of F ( 1 ) , which we pebble with s 1 = p 1
first-level pebbles using this strategy. By the analysis in the proof of Theorem 11.5.4 ,2 d 2 + 1
level-2 I/O operations are performed on inputs and outputs to F ( d 2 ) as well as another 2 d 2 + 1
level-2 I/O operations on the vertices between two stages. Since there are d 2 /d 1 stages, a
total of ( d 2 /d 1 ) 2 d 2 + 1 level-2 I/O operations are performed. We then decompose F ( 3 ) into
d 3 /d 2 stages each containing 2 d 3 −d 2 copies of F ( 2 ) . We pebble F ( 3 ) with s 2 pebbles at level
1 or 2 by pebbling copies of F ( 2 ) in stages, using ( d 3 /d 2 ) 2 d 3 + 1 level-3 I/O operations and
using ( d 3 /d 2 ) 2 d 3 −d 2 times as many level-2 I/O operations as used by F ( 2 ) .Let n ( 3 ) be the

2

number of level-2 I/O operations used to pebble F ( 3 ) .Then n ( 3 )
2

=( d 3 /d 1 ) 2 d 3 + 1 .

Continuing in this fashion, we pebble F ( r ) ,1

k ,with s r− 1 pebbles at levels l or
below by pebbling copies of F ( r− 1 ) in stages, using ( d r /d r− 1 ) 2 d r + 1 level- r I/O operations
and using ( d r /d r− 1 ) 2 d r −d r − 1 as many level- j I/O operations for 1

≤ r ≤

1. Let n ( r )
j
be the number of level- j I/O operations used to pebble F ( r ) . By induction it follows that
n ( r )
j

≤ j ≤ r −

=( d r /d j ) 2 d r + 1 .
For r k , the number of pebbles available at level r or less is at least 2 d + 1, which is

enough to pebble F ( d ) by levels without performing I/O operations above level k + 1; this

≥