Sequencing graph model

Uses a sequencing graph model, called the Sequencing Intermediate orm (SIF), for scheduling and allocation. The vertices of the graph represent operations to be performed, and the edges represent predecessor / successor relationships (which are subject to the data dependencies between operations). 

The input to the structural synthesis phase consists of a sequencing graph model of the hardware behavior to synthesize, along with the following constraints, which can either be specified in the input hardware description, or entered in-tCTactively by the designs. 

Example Sequencing graph model Implementation Resources ... 

The input to Hebe consists of a sequencing graph model and the following constraints ... 

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. 

Section 4.3 describes the model of hardware resources used in synthesis. Section 4.4 summarizes the major features of the sequencing graph model. 

Table 4.1 Vertex types in the sequencing graph model representing HardwareC constructs.

The sequencing graph model is a simple yet powerful rq>resentation for synthesis. Both control-flow and data-flow dependencies are captured uniformly as edges in the sequencing graph. The main features of this model are summarized below. 

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. 

Synthesis across the hierarchy. As described in Chapter 4, the sequencing graph model supports two forms of hierarchy calling hierarchy, which refos to the nesting structure of model call vertices, and control-flow hierarchy, which refers to the nesting structure of conditionals and loops. 

Precise control implementation. As background for defining a precise control implementation, we describe first our model of the control implementation for the sequencing graph model. We assume a synchronous implementation of control that can be modeled on the whole as a synchronous finite-state machine (FSM) where transitions occur by the ass on of a clock signal at every cycle. The model of synchronous control as a FSM serves as an abstraction to reason about its properties in particular, it does not imply its physical realization in hardware, i.e. the control circuit may be physically implemented either as a single FSM or as a network of FSMs. 

The adaptive control approach takes as input a sequencing graph model G, without timing constraints and directly maps the graph model into a synchronous control unit consisting of a modular interconnection of interacting finite-state machines. As its name indicates, adaptive control takes into account the variations in the execution times of the operations caused by the changing input data. 

Read in SIF models. Sevoal SIF models can be read in during a single session. A SIF model corresponds to either a SIF structure model that describes a structural interconnection of models, or a SIF sequencing model that describes an imperative semantic algorithm in the sequencing graph model. 

Synthesis Algorithms. We have developed a sequencing graph model to capture the three requirements of ASIC designs. The model supports concurrency... 

---