Data-dependent delay operations

Relative control synthesis. Relative scheduling complicates the task of ctxi-trol generation. When th are no data-dependent delay operations, the schedule consists of a single sequence of control steps that can be synthesized by traditional control strategies. For example, the schedule can be implemented as a microprogrammed controller or as a single finite-state machine. In the general case, however, these traditional control schemes are inadequate. 

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. 

Organization of chapter. This chapter presents the formulation and algorithms for relative scheduling. Our approach can be described in a nutshell as follows. In relative scheduling, we support both operations with fixed delay and operations with data-dependent delay data-dependent delay operations represent points of synchronization. We uniformly model both types of operations as vertices in the constraint graph model. We assume in this cluq)ter that resource binding and conflict resolution have been performed prior to scheduling. 

We now consider the consistency of constraints in the presence of data-dependent delay vertices. Intuitively, the data-dependent delay vertices create time gaps that cannot be resolved statically. Depending on the execution profile of these operations, a timing constraint may or may not be satisfied by a given schedule. We extend the analysis by introducing the concept of well-posed versus ill-posed timing constraints, in the presence of data-dependent delay operations. 

We make the following assumptions. First, the cardinality of the operation cluster must be greater than one ( C > 1), since othowise the ordering is trivial. Second, each vertex Cj C must either be a data-dependent delay operation (i.e. anchor) or have non-zero fixed execution delay, i.e. (c ) > 0. Note that registers have already been introduced prior to conflict resolution to latch the outputs of the shared resource. For example, the execution delay for shared calls to a combinational adder is 1 cycle because of the latching delay. 

Intuitively, the time to execute a precise control implementation of hardware behavior depends solely on the execution of the operations and not on the transfer of control. This means that the time required by the control to activate a data-dependent delay operation is precisely equal to its execution delay. For example, if an extra cycle is needed to transfer control to a called procedure (as in the microcode-based implementation of [TLW+90]), then the control implementation is not precise by the above definition. On the other hand, a precise... 

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. 

The control network adapts to the changing execution delays of the operations. It has several advantages that include modularity, distribution of control, uniform handling of both fixed and data-dependent delay operations, and support for multiple concurrent execution flows. We describe now a simple adaptive control implementation that satisfies these requirements. Although it may not be precise in terms of control delay, we use this simple model to justify a more elaborate control scheme that is presented in the next section which satisfies the preciseness requirement... 

When all operations have fixed delays, the restarting periodicity can be hardcoded into the control because the latency of the graph is fixed. We say in this case that the control equations can be statically derived. Conv sely, when data-dependent delay operations are present, the control equations have to consider dynamically variations in the input signals. Since the latency of the graph may change, the hard-coded control approach cannot be used in gen. To resolve this difficulty, two mechanisms are used to construct a precise control implementation. The first mechanism is to use lookahead to ensure prqrer resetting of the control fca all input sequences. The second mechanism is to dynamically identify stateless operations. 

Computations that do not take any time to execute, such as stateless branches of conditionals, should immediately activate their successor op tions without taking a cycle to transfer conuol. It is therefore important to know when a given operation is stateless i.e. execution delay is zero for a particular input sequence. Since our model supports data-dependent delay operations, it is necessary to dynamically determine whether a particular operation is stateless. 

Although the control scheme is straightforward, the amount of combinational logic that is needed for the comparisons may be large. In the simple case without data-dependent delay operations, the control reduces to a s-ingle counter, which can be implemented using either microprogrammed controllers or state machines. 

---