Well-posed timing constraint

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. 

Figure 6.4 Examples of ill-posed timing constraints (a) and (b), and well-posed constraint (c), where the double-circled vertices are anchors with data-dq)endent delays.

We now consider the consistency of constraints in the presence of data-dependent delay vertices. Intuitively, the data-dependent delay vertices create time gaps that cannot be resolved statically. Depending on the execution profile of these operations, a timing constraint may or may not be satisfied by a given schedule. We extend the analysis by introducing the concept of well-posed versus ill-posed timing constraints, in the presence of data-dependent delay operations. 

One final point about closed-loop process control. Economic considerations dictate that to derive optimum benefits, processes must invariably be operated in the vicinity of constraints. A good control system must drive the process toward these constraints without actually violating them. In a polymerization reactor, the initiator feed rate may be manipulated to control monomer conversion or MW however, at times when the heat of polymerization exceeds the heat transfer capacity of the kettle, the initiator feed rate must be constrained in the interest of thermal stability. In some instances, there may be constraints on the controlled variables as well. Identification of constraints for optimized operation is an important consideration in control systems design. Operation in the vicinity of constraints poses problems because the process behavior in this region becomes increasingly nonlinear. 

Section 6.3 presents polynomial-time algorithms to check for well-posedness, make the constraints well-posed with minimal serialization, remove redundant anchors, and find the minimum relative schedule. Section 6.4 analyzes the properties of the algorithms. In particular, we show that the algorithms are guaranteed to yield a minimally serialized, well-posed, minimum schedule, if one exists. Finally, Section 6.5 summarizes the relative scheduling approach. 

Definition 6.2.6 A timing constraint is well-posed if it can be satisfied for all values of execution delays of the data-dependent delay vertices. 

Conversely a timing constraint is said to be ill-posed if it cannot be satisfied for some values of the data-dependent delays. A constraint graph G V, E) is well-posed if every constraint implied by the edges E is well-posed. From the definition of feasible constraints, if a graph is well-posed, then it is also necessarily feasible. The contra-positive also holds specifically, if a graph is unfeasible, then it is ill-posed. Because of the observation that no schedule exists for unfeasible constraint graphs, we assume in subsequent analysis the constraint graphs to be feasible, unless otherwise indicated. 

Consider, howevCT, the situation in Figure 6.4(b) if we introduce a forward edge from 02 to t ,- with data-dependent edge weight equal to 6(02), as shown in Figure 6.4(c). In this case the constraint will become well-posed. The reason is because by the time v,- begins execution (after the completion of both a 1 and 02), all the data-dependent delays in the fan-in of vj is already known, i.e. (02) is common to both T vi) and T vj). The satisfiability of the constraint can... 

Now we prove the sufficient condition. Assume G(V, E) is well-posed and there exist an edge e - E for which A(v<) is not a subset of A(vj). By definition of anchor sets, Cij cannot be a forward edge, and hence must be a backward edge that is derived firom a feasible maximum timing constraint Since all constraints implied by G are well-posed, it follows from Lemma 6.2.1 that i4(v ) C A(vj). This results in a contradiction. Thoefore, the crit on A(vi) C A(vj) must be satisfied for all edges in the graph. ... 

Remove Redundant Anchors - At this point, the constraint graph is well-posed. We then identify and remove the redundant anchors that are not needed to compute the start times. 

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. 

In relative scheduling, the start time of an operation is defined as time offsets with respect to the completion of anchors. Constraints are feasible or well-posed depending on whether they can be satisfied under restricted or general input conditions, respectively. Redundancy of anchors was introduced to simplify the start time of operations by removing redundant anchor dependencies. This can lead to a more efficient control implementation because operations need to be synchronized to a fewer number of signals. Analysis of these properties was presented in this chapter. 

Lemma 9,2.1 Consider a vertex v V of a well-posed graph, a non-prime anchor a A v), and a prime anchor b G -i4(w). The anchor a can always be made redundant with respect to v by lengthening the minimum timing requirements from a to h and from b to v. Furthermore, the resulting constraint graph remains well-posed. 

In (x-der to assign v to the link a maximal timing constraint e i, is added. If a path of positive length from 6 to v exists, then w f, = — lp l>, w), otherwise Wvi, = —0. The value of the weight ensures that no positive cycle is formed. Note that is bounded, because if kv is unbounded, then a cannot be a prime anchor of v, which contradicts our assumption. Since no forward edges are added, the anchor sets for all vertices remain unchanged. Since G is well-posed, no anchor sets have been modified, and no positive cycles have been introduced, G is well-posed. 

---