Iterative incremental scheduling

Procedure IncrementalOffset is applied to the source vertex, where ftrav v) is initialized to 0. Since each edge in / is traversed once, and each invocation of the IncrementalOffset procedure has worst case complexity of 0( v4 ). The worst case complexity for finding all longest paths is 0 A Ef ). 

The modified offsets (vj) are then updated in the schedule f . It is important to note that in the case of well-posed timing constraints, A(v,) C A(t j). After the readjustments, IncrementalOffset is reapplied, and the process repeats until all maximum timing constraints due to the backward edges are satisfied. A formal description of ReadJustOffset is given below. 

We comment now on the total computational complexity of the algorithm. The complexity of the IncrementalOffset isO(. 4 - / ). The complexity of the readjustment is 0 A jf ftl). Therefore, each iteration has computation complexity 0(. A IE I), proportional to the number of edges in the graph. The iterative incremental scheduling algorithm has worst case complexity 0((l -I-1) j4 ). Note that in practice the number of backward edges and the number of anchors A are usually small. 

---

Firuiing the minimum schedule - Finally, the relative schedule can be computed by using an efficient algorithm called iterative incremental schedul-... 

Figure 6.11 Execution trace for the iterative incremental scheduling algorithm.

We analyze in this section properties of the algorithms presented in Section 6.3. We prove first the makeWellposed algorithm can minimally serialize an ill-posed constraint graph in attempt to make it well-posed, if a well-posed solution exists. We then prove the iterative incremental scheduling algorithm can construct a minimum relative schedule, if one exists, in polynomial time. 

The iterative incremental scheduling algorithm constructs a minimum relative schedule, or detects the presence of inconsistent timing constraints, with at most i + 1 iterations. This is a very desirable property, since the number of maximum timing constraints i is in general small. The proof follows the outline in [LW83]. Note that in the sequel the full anchor set A(v <) for a valex Vi is used in the computation of the start time and offsets. By Theorem 6.2.4 and Theorem 6.2.6, the result is applicable when the relevant anchor set R vi) or the irredundant anchor set IR(vi) are used instead. 

Theorem 6.4.2 Let G V, E) be a well-posed constraint graph. Then the iterative incremental scheduling algorithm yields the minimum relative schedule after at most L + 1 iterations. 

After the operations within each clusters have been serialized, the clusters are linearly ordered compatible with the original partial order. This linear order can be constructed in linear-time with respect to the number of clusters. The order in which the clusters are visited and resolved is important Therefore, if the above steps fail to find a valid ordering, then this order can be changed and the above steps repeated. By Theorem 6.2.1 and Lemma 6.2.3, a solution to conflict resolution implies that a valid relative schedule exists. In this case, the binding is known to be valid and the iterative incremental scheduling algorithm can be performed to compute the time offsets. 

Proof Assume the consfraints are inconsistent, implying a positive cycle exists in the graph. Consider the offset [Pg.161]

---