Irredundant anchor set

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 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. 

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. 

We use the full anchor set A(v) for control generation in this section. The extension to use the irredundant anchor set IR v) is straightforward and can be achieved by replacing A v) with IR v) for each vertex v V. 

The irredundant anchor set IR v) of a vmex v is the minimum set of synchronizing points affecting the activation of v. In Figure 9.1(b) the irredundant anchor sets are IR v) = 6 and IR b) = a. The proof stating the equivalence of start times computed with and without the redundant anchors is given in Chapter 6. 

If there is a single irredundant anchor in the anchor set A(v), then we can simplify the generation of activate by directly asserting it based on specific counter values. For example, if the delay of v is 2 and there is a single anchor a A v), then the activate signal is activate = Countera = 2) + Countera = 3), a significant reduction in complexity. 

By using only irredundant anchors in computing the start times, the control cost can be reduced by (1) reducing the size of the anchor sets, translating to lower synchronization costs, and by (2) reducing the maximal offset values, translating to fewer numbo of states in the corresponding FSM. 

---