Execution delay

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.

Number of cycles, unbound means unbounded execution delay. 

The execution delay for a sequential compound statement C, consisting of i,S2> ) ib statements is equal to the sum of the execution delays of the individual statements, e.g.,... 

The execution delay for a procedure (or function) call is equal to the execution delay of the called procedure. The execution delay for a conditional is equal to the execution delay of the selected branch. The execution delay of a loop is equal to the number of iterations times the execution delay of the loop body. 

A problem arises fw conditionals or loops because their execution delays depend on external signals and events that are not known statically. We further categorize the vertices based on this observation. 

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. 

Figure 4.3 Example of a conditional where the branches have different execution delay.

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. 

Minimum sequencing edge Sij E A forward edge Ef with weight o (e,j) = 6(v,), modeling a minimum timing constraint equal to the execution delay of v,-, e.g., vj should start at least after the completion of Vi. 

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. 

The execution delay of a call vertex is exactly equal to the latency of the called graph. 

The execution delay of a loop vertex is equal to the number of iterations midtipled by the latency of the loop body. 

The execution delay for an operation whose hardware resource is latched must be increased by one to account for the clock cycle required to latch the outputs. The delay (v) for a vertex v using a resource component r with delay delayr is ... 

Data-dependent delay operations. The execution delay of a vertex can be fixed or data-dependent. The latter type describes external synchronizations and loops. 

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. 

As stated earlier, the primary goal of this research is to develq) methods of synthesizing hardware from abstract specifications under both detailed timing and synchronization constraints. Detailed timing constraints ctg)ture minimum and maximum bounds on the start time of operations synchronization constraints model handshaking and coordination among concurrent computation threads, and are represented as operations with data-dependent execution delays. 

For a constraint graph G(V,a weight Uij is associated with each edge (uj, Vj) that is equal to the execution delay of the qjeration t ,-, denoted by (v>). Let us assume first that the weights are known this assumption will be removed in the next section. The scheduling problem may be defined as follows ... 

Scheduling problems are defined and solved on graphs with fixed delay operations. We extend this notion to graphs with data-dependent delay vertices. For a data-dependent delay vertex the execution delay is not known statically, and can assume any integer value from 0 to oo. For this reason, we define a subset of the vertices, called anchors, that serve as reference points for specifying the start times of operations. 

Let Ga Va,Ea) be the subgraph induced by 14, where the execution delays of all data-dependent delay vertices assume the minimum value of zero. 

Finding the set of offsets is identical to scheduling Ga(Va, Ef), where the constraint graph models both operation dependencies and timing constraints. If no such set exists, then the constraints are said to be inconsistent. Since the execution delay of a data-dependent delay vertex can be any integer greater than or equal to zero, a minimum offset o o(fi) is the minimum time after the completion of the anchor a before t)< can begin execution. 

In other words, an anchor a is in the anchor set of a vertex if the vertex can begin execution only cfter the completion of a. Note that since the graph is polar, the source vertex is contained in the anchor set of every vertex, and the anchor set of the source vertex is the empty set. The anchor set represents the unknown factors that affect the activation time of an operation. If we generalize the definition of the start time of a vertex in terms of fixed time offsets from the completion time of each anchor in its anchor set, then it is possible to completely charactmze the temporal relationships among the operations. In particular, the offsets of a vertex can be related to its start time when the execution delays 6(a), a G i4 of the anchors are known. The start time of a valex v,-, denoted by T vi), is defined recursively as follows ... 

Definition 6.2.6 A timing constraint is well-posed if it can be satisfied for all values of execution delays of the data-dependent delay vertices. 

Proof We wUl prove by contradiction. Assume G is well-posed but there exists a cycle with data-dependent length. Let the cycle be denoted by C. Since C has data-dependent length, this implies that there exists an anchor a on the cycle such that the length of the cycle is greater than or equal to the execution delay 6(a). Consider now the next vertex v that follows a on the cycle C. By definition of anchor sets, a is in the anchor set of v, i.e. a A(v). From Lemma 6.2.2, the anchor sets of all vertices on the cycle must be identical, implying that a is also in the anchor set of a itself. This results in a contradiction. Therefore, we conclude that no cycle of data-dependent length exists in G. ... 

This chapter describes algorithms for resource conflict resolution. Resource conflicts occur when multiple operations activate the same hardware resource simultaneously. When all operations in the hardware model have fixed execution delays, conflict resolution becomes part of the scheduling and resource binding tasks. In particular, operations scheduled to different control stq)s or belonging to mutually exclusive conditional branches can share their hardware resources. Consider for example the force-directed scheduling technique [PK89b]. Operations with similar resources are first scheduled to reduce their concurrency, then they are bound to hardware resources subject to this schedule. The binding step ensures that no resource conflicts will arise. This approach is, however, restricted to bounded delay operations. 

This section analyzes the topology of timing constraints in a constraint graph G V,E). We describe several concepts that are used in the conflict resolution formulation. Let the target instance operation set 0( ,j)(G) be denoted by G C V, where we dropped the terms t,i) and G for conciseness. The instance operation set O consists of fc = G vertices, denoted by o,-, i = 1,..., fc. Each vmex Oi O has an associated execution delay 6(o ) that can be fixed or data-dependent In the simplistic case of flat graphs, all elements of G are... 

---