Relative scheduling anchors

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.4 A relative schedule Q of a constraint graph G(V, E) is the set of offsets of each vertex Vi G V with respect to each anchor in its anchor set... 

First, we improve significantly the efficiency of the scheduling algorithm (Section 6.3.5) by focusing on a smaller number of anchors. Second, we can achieve a smaller and faster control implementation of a relative schedule because the start time depends on fewer offsets, and hence on fewer synchronizations. 

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. 

For an anchor a, at most La + 1 iterations are needed to find the minimum relative schedule because = 0, k> La. For all anchors, the algorithm will give the minimum relative schedule with at most L + 1 iterations. ... 

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. 

In relative scheduling, the activation of an operation is specified with respect to the completion of a set of anchors with data-dependent execution delays. In particular, the start time T v) for a vertex v e is defined in terms of the anchor offsets 12 = [Pg.214]

Given a relative schedule, the control implementation approach of Chapter 8 generates a control circuit to activate operations according to the schedule. The control circuit can be modeled as consisting of two components an offset control for each anchor A and a synchronization control for each vertex d G 1, as described below ... 

Since the precise transition and precise restarting criteria are both satisfied for a particular input sequence, and since statelessa and dsinka for all anchors are dynamically evaluated, the relative control implementation for G is precise with respect to the schedule 12(G). ... 

---