Relative scheduling

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 ease of presentation, relative scheduling is first described in Chapter 6, where resource conflicts are assumed to be resolved. Resource conflict resolution by appropriately serializing the operations subject to the timing constraints is presented in Chapter 7. Control generation from relative scheduling is described in Chapter 8. A novel approach to control optimization called resynchronization is described in Chapter 9. 

As synthesis research progressed, scheduling and binding techniques evolved to relax the basic block restriction by considering also the conditional control- 

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. 

---

Ku, D. and De Micheli, G. (1992) Relative scheduling under timing constraints Algorithms for highlevel synthesis of digital circuits. IEEE Trans Comput Aided Des, 11 (6), 696-718. 

The dependence of Tg on the degree of cure is shown in Figure 4a for schedule A (closed circles), schedule B (open squares) and for schedule B after heat-up (closed squares). For the latter samples AH(RTcure) + Ah(s) = AH(k) was assumed. The observation of different Tg s for identical relative (schedule A) and normalized (schedule B) degrees of cure precludes the interpretation that both reactions (a) and (b) occur at all... 

David Ku and Giovanni De Micheli, Relative Scheduling under Timing Constraints , Proc. of the 27th DAC, pages 59-64, June 1990. 

D. Ku and G. D. Micheli, Relative scheduling under timing constraints, in 27th Design Automation Cortference, ACM/IEEE, June 1990. 

Relative Schedule. With the resource conflicts resolved, scheduling is still necessary to assign the operations to control states in (vder to generate the control circuit for the final hardware. We use a novel technique called relative scheduling that uniformly supports operations with fixed and unbounded delays. We describe briefly the main results in relative scheduling. The interested reada is referred to [7] for further details. 

Firuiing the minimum schedule - Finally, the relative schedule can be computed by using an efficient algorithm called iterative incremental schedul-... 

The polynomial-time complexity of the above steps allows relative scheduling to be effectively integrated within the design space exploration. 

Relative scheduling a scheduling formulation that supports synchronizations and timing constraints,... 

Relative control synthesis a control generation approach that synthesizes conux)l circuits from a relative schedule as an interconnection of interacting finite-state machines, and... 

The relative scheduling formulation provides a theoretical basis for analyzing redundancy in the synchronization of a given operation. Using synchronization redundancy can reduce the size of the corresponding control circuit, and algorithms are presented to remove all redundancies in a schedule. 

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. 

The main algorithmic contributions of this research are described in the next four chapters. Ch ter 6 presents the relative scheduling formulation that includes description of the algorithms and analysis of their prqterties. Chapto 7 describes conflict resolution under timing constraints. Chapter 8 describes the generation of the control circuit from a relative schedule. Chapter 9 describes the control resynchronization optimization that reduces the area of the control implementation under timing and synchronization constraints. 

Relative scheduling. Once resource conflicts have been resolved, operations are assigned to control steps subject to synchronization and timing requirements. The formulation is based on relative scheduling. 

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. 

The sequencing graph model is the underlying representation for design space exploration, which is described in the next chapter. Relative scheduling, constrained conflict resolution, and relative control synthesis and optimization are all formulated based on the constraint graph model. 

Section 6.3 presents polynomial-time algorithms to check for well-posedness, make the constraints well-posed with minimal serialization, remove redundant anchors, and find the minimum relative schedule. Section 6.4 analyzes the properties of the algorithms. In particular, we show that the algorithms are guaranteed to yield a minimally serialized, well-posed, minimum schedule, if one exists. Finally, Section 6.5 summarizes the relative scheduling approach. 

Note that if there are no data-dependent delay vertices in the graph, then the start times of all operations will be specified in terms of time offsets from the source vertex, which reduces to the traditional scheduling formulation. We define the relative scheduling problem as follows. 

Definition 6.2.4 A relative schedule Q of a constraint graph G(V, E) is the set of offsets of each vertex Vi G V with respect to each anchor in its anchor set... 

---