Making Anchors Redundant

Since this calculation is done dynamically during execution, the synchronization logic for V is reduced. Furthermore, the maximal offset is reduced from 4 to 2 which results in a smaller number of registers needed by the offset generation for a. 

Before proceeding, we state the following theorem, which provides the basis for determining the validity of transfrmnations. They relate the concept of feasibility (satisfaction of constraints when 6(a) = 0, Va 4) to the concept of well-posedness (satisfaction of constraints for any 6(a), Va A). 

Theorem 9.2.1 Consider a well-posed constraint graph G(V, E). If a forward edge Cav from anchor a to vertex v with weight Wav = 6(a)- -k,k Q is added 

Proof This follows directly from Theorem 6.2.3. For the sufficient condition, if G is feasible and does not contain unbounded length cycles, then from Theorem 6.2.3 we know that G V,E) can be made well-posed. Now for the necessary condition. If G can be made well-posed, then it is feasible. Furthermore, Theorem 6.2.3 implies that no unbounded length cycles exist in G.  

This theorem ensures that a constraint graph can be made well-posed provided no positive cycles and no unbounded length cycles are created during control optimization. Furthermore, if it can be shown that the anchor containment property holds, then it follows that the resulting graph is well-posed. 

---

Removing redundant anchors - It is often the case that not all anchors in the anchor set are needed to compute the start time of an operation. This is due to the cascading effect of anchors that make some redundant in computing the start time. For a well-posed graph, we identify and remove the redundant anchors. Through redundancy removal, it is possible to obtain a smaller and faster control implementation because the start time depends on fewer offsets, and hence fewer synchronizations. 

Proof We prove by construction. The graph is travoaed in topological order starting from the source vertex. When an anchor a . 4 is traversed it is made redundant to all vertices to which is non-prime and irredundant. We claim that making a redundant in this manner will not cause a previous anchor c A in the ordering to become irredundant with respect to some vertex to which it is non-prime. 

The algorithm for lengthening visits each anchor a in the graph and lengthens the paths to vertices v, where a is a non-prime irredundant anchor of v, in order to make a redundant For a vertex v and a non-prime anchor a My)y a forward path />(6o, -, tn) is found where 6o = a, bn = v, and bi e for 0 < i < n. Furthermore the path contains the unbounded edge weights... 

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. 

We first serialize the anchors to make as many anchors of a vertex non-prime as possible. Since non-prime anchors can be make redundant by lengthening, this has the effect of reducing the synchronization cost of the final control implementation. This is particularly important for control-dominated designs because... 

---