Start time irredundant

By Theorem 6.2.5, the irredundant anchors are also relevant anchors. Therefore, there exists a maximal defining path p r,vi) of r IR(vi), where the w,) is equal to length r,Vi). By Theorem 6.2.3, length r,Vi) is equal to the minimum offset Let T "(vi) and be the start times... 

We conclude that r must be used to compute the start time of Vi. The same argument applies to every irredundant anchor, and hence IR(vi) is necessary to compute the start time of v,. ... 

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. 

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. 

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. 

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. 

Since only the irredundant anchors are necessary in the start time computation of a vertex, serializing the clusters can reduce the synchronization requirement by decreasing the number of irredundant anchors for a vertex. In order to define a lower bound on the synchronization cost, we present the following theorem. It applies to those graphs that are ordered. 

---