Timing constraints constraint graph

Besides as a property of the hardware modules, time can come in as designer-specified constraints. These are added into the graph as sequence edges, labeled with the time constraints. A detailed coverage falls outside the scope of this chapter. 

Here, operations are grouped into clusters in order to exploit the structure present in the flow graph. The objective function is cluster similarity within the timing constraints imposed. Within the single clock cycle constraint, which... 

Scheduling receives the optimized data/control flow graph, a fixed CBB allocation, and a maximum timing constraint as input. The goal of scheduling... 

The CSTEP control step scheduler uses list scheduling on a block-by-block basis, with timing constraint evaluation as the priority function. Operations are scheduled into control steps one basic block at a time, with the blocks scheduled in executidepth-first traversal of the control flow graph. For each basic block, data ready operator are considered for placement into the current control step, using a priority function that reflects whether or not that placement will violate timing constraints. Resource limits may be applied to limit the number of operators of a particular type in any one control step. 

Uses an iterative graph-based technique scheduling technique that supports timing constraints, and operations with unbounded delays. 

Uses three graphs that share the same vertices, with each vertex representing either an operation or variable in the DSL program. A controlflow graph represents the predecessor-successor relationships between the vertices, a dataflow graph represents the data dependencies between the vertices, and a third graph represents timing constraints between the vertices. 

CSTEP schedules operators into control steps one basic block at a time. Basic blocks are scheduled in execution order using an execution-order traversal of the control flow graph. This guarantees that when a timing constraint is expressed on two operators that are in separate basic blocks, the first operator in the constraint is scheduled before the second operator is scheduled. This leaves the second operator to be evaluated for placement in terms of how placement affects the constraint. The ordered scheduling of basic blocks also ensures that inter-basic block data dependencies will be satisfied. 

Figure 7. An event graph fragment (top) demonstrating the effect of adding delay. The circuit on the left is generated by adding a delay element to meet a minimum timing constraint. If the delay were not required then the circuit would be reduced to the optimal circuit on the right (a simple buffer). ...

The behavioral specifrcation of a digital circuit consists of two parts its internal behavior (data-flow and operations) and its interface behavior (signaling conventions and their timing constraints). High-level synthesis systems use data-flow graphs to represent internal bdiavior. Event graphs are used to address the special nature of interface behavitv. 

The need to represent and synthesize circuits with interface timing constraints has led to the development of event graphs as described in the previous section. The nodes of these gr hs correspond to signaling events and the arcs specify how the events are ordered and separated in time. This model freely mixes synchronous and asynchronous interface behavior. However, only limited data-flow information is captured, namely, when input and ouQ)ut data values must be valid on the interface signal wires. 

Figure 6 Example of a constraint graph, with a minimum and a maximum timing constraint. The number inside a vertex rq>resents its execution delay.

Identify operation clusters - an opo on cluster represents a subset of vertices in the opoation set that are connected by a cycle in the constraint graph, i.e. a cyclic timing requirement is imposed on them. 

Conflict resolution, relative scheduling, relative control synthesis and optimization are formulated on a constraint graph model that is derived from the sequencing graph model under detailed timing constraints. Descriptions and analyses of these formulations are presented in subsequent chapters. 

This chapter is organized as follows. Section 4.1 describes the semantics of the sequencing graph model. Section 4.2 describes the derivation of a constraint graph model from a sequencing graph model under timing constraints. 

Consider a sequencing graph G, V,E,6). Let T vi) represent the start time of Vi, i.e. the time at which begins execution with respect to the source vertex of G,. Detailed timing constraints consist of the following ... 

The latency of a constraint graph is the minimum numb of cycles that is required to execute all operations subject to timing constraints. The latency is computed hierarchically in a bottom-up manner according to the following definition. 

The above theorems imply that conflict-free allocation /(<) can be evaluated efficiently because the concurrency factor can be computed in polynomial time. This point is worth emphasizing. The conflict-free allocation indicates the degree of parallelism among the operations of a given resource type. It corresponds to the extent resource conflicts are present in a graph. If the conflict-free allocation satisfies the required resource constraints, then it is not necessary to allocate more resources than this amount to obtain an implementation that satisfies the timing constraints. 

---