22 Energy-Aware Memory Management for EMSs
is a recurrence equation to compute the Fibonacci sequence. There are two
disjoint cases that partition the computation into two distinct subdomains
whose union is {i |i ≥ 0}, the entire domain of the variable fib.
Definition 2.2 (Dependency) For a system of recurrences, we say that an
array variable f
i
at index point p ∈ D
i
(directly) depends on array variable
f
j
at index point q , (denoted by p
i
→ q
j
), whenever f
j
(q) occurs on the right-
hand side of the equation defining f
i
(p).
The transitive closure of this relation is called the dependency relation,
denoted by p
i
→ q
j
.
A dependence is called a uniform dependence if it is of the form z →
z +b, where b is a constant vector. It is called an affine dependence if