Conflict Resolution Formulation

A resource binding is valid if it is possible to resolve its resource conflicts and still satisfy the required timing constraints. For a given resource binding recall that an instance operation set 0(t,i) of 0 is a subset of vertices that are bound to an allocated resource instance (t, t). Obviously, resource conflicts will occur if the vertices in 0( t,i) can execute in parallel. An implementable binding is defined as follows. 

Definition 7.1.1 An instance operation set 0 t,i) is implementable if the elements ofO(t,i) are disjoint in time, i.e. they do not execute concurrently. Given a 

From Section 5.2, the concurrency factor of an implementable instance operation set is 1 and the conflict degree of an implementable binding is 0. 

To address this issue, conflict resolution for an instance operation set G(t, ) in a sequencing graph Gm is performed hierarchically in a bottom-up manner. A candidate operation set 0(t,)(G) for each graph G in the cf-hierarchy G m is 

We consider in the rest of this chapter a single constraint graph model G that is derived from a sequencing graph with timing constraints, wh e conflict resolution has been performed on all graphs in its cf-hierarchy G. Therefore, the term instance operation set in the sequel refers to the candidate operation set of with respect to G. 

---

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... 

Relative scheduling provides the framewtx k for analyzing consistency of timing constraints, which is used extensively in the conflict resolution formulation. 

We use the constraint gr h model as the basis fw the formulation. Since the objective is to find an wdering that satisfies the timing constraints, an important observation is that constraint violatirais will occur only if overconstraint in the form of inconsistent cyclic timing relationships is introduced. The conflict resolution approach is as follows, fOT a given opoatirai set... 

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. 

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. 

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. 

In short, there is a scarcity of ideas about how abstract principles are constracted. The classical notions of induction and deduction have some psychological reality, but neither is tenable as the main source of new principles. The hypothesis that principles arise in the resolution of cognitive conflicts has not yet been formulated precisely within the information processing framework. 

---