Stateless vertex

A vertex is further classified according to the value of its execution delay for a particular input sequence. If a vertex requires one or more cycles to execute (execution delay > 0), then it is called a state vertex. Otherwise, it is called a stateless vertex (execution delay = 0). A graph with only stateless vertices is a stateless gnq>h. 

Proof The precise transition criterion states that for the control element of a state vertex v,- is enabled in the cycle after all the assertion of done signals from every control element in pred,tate vi). From Equation 8.1, a control element is enabled when the done signals of all its predecesscx are asserted, e.g. enahlci = rit ,6pred( j) If Vj, is a stateless vertex, then it assots... 

For fixed delay vertices, the property of stateless versus state is fixed e.g. a no-op vertex is always stateless and a load-register (takes one cycle) is always a state vertex. For data-dependent delay vertices, howev, this property depends on the value of execution delay for a particular input sequence. For example, an un-entered while loop (exit condition is true when the loop is first executed) does not require any clock cycles and therefore is stateless for that input sequence. 

The implementation of a control element is dependent on whether the corresponding vertex is stateless or state. When a vertex v,- is stateless for all input sequences (e.g. no-op or a combinational logic operation), its control element... 

When a vertex Vi is stateless for all input sequences, it asserts its done signal as soon as it is enabled. Otherwise, as described in the previous section, the control element is implemented as the two-state FSM shown in Figure 8.4. The FSM remains in the ready state (5[) until it has completed execution, after which it enters the wait state. The transition back from Sf occurs when the entire graph G, has completed execution, signaled by the assertion of donee. The transition conditions for the FSM are given below ... 

As an illustration, consider the sequencing graph of Figure 8.6, where a number in a vertex represents its execution delay/or a particular input sequence. Shaded vertices denote direct-sink vertices. The completion of execution of all direct-sink vertices results in the completion of the execution of the entire graph. Note that if the source vertex is direct-sink for a particular input sequence, then by definition the sequencing graph is stateless for that input sequence. 

A complication arises since the execution delay of a data-dependent vertex may change for different input sequences. In particular, the delay may become zero, making the vertex stateless. Therefore, it is impossible to always statically... 

Call - The stateless signal for a call vertex is asserted if the called graph is stateless ... 

The precise control implementation extends the approach described in the previous section by incorporating the mechanisms of look-ahead resetting and dynamically identifying stateless computations. The control element for a state vertex vi, shown in Figure 8.8, has two states as in the previous model ready Si and wait Sf. The transition conditions are now described as follows ... 

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. 

---