Execution delay sequencing graph

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. 

Finally, Figure 4.8 shows the constraint graph derived from the sequencing graph of the encoder process in Figure 4.5. The execution delay of an expression... 

The execution delay of each vertex must be associated with a particular input sequence when there are vertices in the graph with data-dependent delay. The reason is because the time required to achieve synchronization and the number of iterations necessary for a data-dependent loop are known only in the context of a given input sequence. 

In traditional approaches, two vertices are disjoint if they are scheduled into different control steps. However, since our model supports data-dependent delay operations, these approaches cannot be used in general. Assume all operations have unbounded execution delay, then two operations are compatible if they have the same resource type and are joined by a directed path in the sequencing graph. 

Concurrency factor can be used to determine the minimum resource allocation that is necessary to avoid resource conflicts, where we assume the worst case of all operations having unbounded execution delays. We first consider a sequencing graph G, and a resource binding 0 defined on G,. The resource binding partitions the shareable operations V into one or more instance operation sets where elements within an instance operation set all share the same hardware resource. We define the conflict degree of the binding 0 as follows. 

Figure 8.3 A sequencing graph with execution delays, the control network, and cycle-per-cycle execution flow.

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. 

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. 

A control FSM is characterized by a set of states called control states. The FSM corresponding to a control implementation of G, is assumed to be initially in the reset state. Because the implementation is assumed to be non-pipelined, the FSM returns to the reset state after the last operation in the graph has completed execution. For a given input sequence, the control delay of the control implementation of G, is the numb of cycles to go from the reset state back to itself. 

---