Removing redundant anchors

The equivalence between irredundant start times and start times computed with the full anchor set, as stated by Theorem 6.2.4, makes possible the computation of start times based on irredundant anchors sets. This has advantages of improving the efficiency of the scheduling algorithm and reducing the cost of control. 

To compute the irredundant anchor sets, we first identify the relevant anchor sets using an algorithm called relevant Anchor, then identify the redundant anchors using algorithm minimumAnchor applied to every vertex of the given constraint graph G V,E). 

The worst case complexity of the algorithm is 0( A V ), since each vmex is traversed at most once for each anchor in the graph. 

The set of unmarked relevant anchors for v form the irredundant anchor set for V, which by Theorem 6.2.6 is the minimum anchor set for v. The worst-case complexity of the algorithm is dominated by computing the longest paths, which is 0(1 V ). The checking requires 0( i ) once the longest path lengths are known, where i2 is the size of the largest relevant anchor set in G. 

---

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. 

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. 

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. 

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. 

Thus we conclude that the offset sequencing constraints for some values of 6(a) and 6(6). In this case, we say that anchor a is irredundant with respect to v, which means that offsets from a must be used to compute T(v). 

---