Information Technology Reference
In-Depth Information
w ( x 1 , b ) different values. If w ( x 1 , b ) >S ,theoutputs Y 1 assume
more values than can be taken by the S pebbles in use just prior to the start of
|A|
outputs have at least
I
.Because
the values of variables in Y 1 are determined by the inputs pebbled in
I
, which are fixed, and
the values under the S pebbles, this contradicts the definition of f . It follows that x 1 can be
no larger than d ,where d is the largest value such that w ( d , b )
S . Thus the number of
I
, x 0 , satisfies x 0
( n
d ) .
inputs pebbled in
intervals in which b outputs are pebbled, the number of times
that inputs are pebbled, T I ,isatleast
m/b
Since there are
m/b
( n
d ) .
Grigoriev [ 121 ] established the above theorem for ( 1, n , m , p ) -independent functions. We
restate as a corollary a slightly revised version of his theorem for ( α , n , m , p ) -independent
functions.
COROLLARY 10.4.1 Let f : A
n
m be ( α , n , m , p ) -independent and let it be realized by a
→A
r
s
straight-line program over a basis
{
h :
A
→A
|
r , s
1
}
. Every pebbling of every DAG for f
requires space S and time T satisfying the inequality
α ( S + 1 )
T
mp/ 4
Proof An ( α , n , m , p ) -independent function on n inputs has a w ( u , v ) -flow satisfying
w ( u , v ) > ( v/α )
1for n
u + v
p ,where x 0 = n
u
0. Since b can be
freely chosen, let b =
α ( S + 1 )
.Thus, ( b/α )
1
S for ( n
d )+ b
p ,which
contradicts the requirement that w ( d , b )
S . It follows that ( n
d )+ b>p or that
( n
d )
p
α ( S + 1 )
. With the inequality
m/x
( m
x + 1 ) /x (see Prob-
lem 10.2 ), the following lower bound follows from Theorem 10.4.1 :
( m
α ( S + 1 )
+ 1 )( p
α ( S + 1 )
)
T
α ( S + 1 )
Since p
m ,if
α ( S + 1 )
p/ 2, the desired lower bound follows. On the other hand,
if
α ( S + 1 )
p/ 2,
α ( S + 1 )
T
mp/ 2since T
m .
n
m
It is possible that a function f :
A
→A
is not ( α , n , m , p ) -independent but a sub-
r
s
function g :
m . (Subfunctions are
defined in Section 2.4 .) As shown in Problem 10.18 , the lower bound for the subfunction g
applies to f .
Lower bounds on space-time exchanges can also be derived using properties of the graphs
to be pebbled. For example, if a graph contains a superconcentrator (defined in Section 10.8 ),
lower bounds on the product can be derived on ( S + 1 ) T in terms of the number of inputs of
thegraph.(SeeProblem 10.28 .)
As mentioned at the beginning of this section, Theorem 10.4.1 is much more general
that it appears. In Problem 10.20 the reader is asked to show that the lower bound holds for
“input-output-oblivious” finite-state machines, FSMs that compute functions but read their
inputs and produce their outputs at data-independent times. Problem 10.21 asks the reader to
establish that pebblings of straight-line computations can be translated directly into computa-
tions by finite-state machines.
A
→A
is ( α , r , s , p ) -independent for r
n and s
Search WWH ::




Custom Search