Analysis of adaptive control

In this section, we will prove that the implementation presented in the previous section is precise, i.e. the control delay is equal to the latency of the sequencing graph Gi V, E,) for all input sequences. Note that minimum and maximum timing constraints are not considered in this analysis. Therefore, the latency of Gg is the length of the longest weighted path from the source vertex to the sink vertex, where the weight of a vertex is equal to its execution delay. 

We begin by decomposing the definition of preciseness into two criteria, both of which must be satisfied by a precise control implementation. We say that a control element executes when it activates the corresponding operation, i.e. asserts the activate signal, and a control element completes execution when the corresponding operation completes execution. Let pred,tate( Vi) C V denote the set of state vertices such that a state vertex Vp is in pred,tate vi) if there is a path of stateless vertices from Vp-to-vj. 

Lemma 8.1.1 Given an input data sequence, the control delay of a synchronous control implementation of a sequencing graph G, without timing constraints is equal to its latency if the following two criteria are satisfied  

Precise transition For every state vertex Vi V, the control element is enabled in the cycle crfter the completion of execution of all state vertices inpred,tau vi). 

Precise restarting For all polar sequencing graphs in the hierarchy induced by G, the control element of the source vertex of a given graph is activated in the cycle following the completion of all its vertices. 

---

We present an overview of the basic strategy in Section 8.1.1. Two control implementations are presented. Section 8.1.2 describes a simplified scheme that supports data-dependent delay operations and multiple execution flows, but the resulting control is not precise. We extend the simplified scheme in Section 8.1.3 to obtain a precise control implementation. Analysis of adaptive control is presented in Section 8.1.4. 

---