Properties of relative schedule

In this section, we analyze several properties of relative scheduling. The following theorem states the existence criterion for making a constraint graph well-posed. 

Lemma 6.23 A feasible constraint graph G(V, E) can be made well-posed if and only if no data-dependent length cycles exist in G. 

Proof We prove first the sufficient condition. If no data-dependent length cycle exists, we prove by induction that it is possible to satisfy the well-posedness condition for all edges. As the basis of the induction, consider the forward constraint graph ( /. By definition of anchor sets, G/ is well-posed. Now consider a backward edge e,j- e Ei. If A(u,) C A vj), the constraint is well-posed. Otherwise, there exists an anchor x 6 A(uj) but x A(vj). By assumption, there are no data-dependent length cycles. Therefore there must not be a path firom 

Theorem 6.2.3 Assume the constraint graph G V, E) to be well-posed. Then for all offsets T vi) e and cr vi) e 

Proof The proof uses an extension of the analysis presented in [LW83]. We show first that Vv, F is a relative schedule 

---