Operation set instance

The cardinality of 0(,) is denoted by 0(t,<). Instance operation sets partition V into groups, each of which is implemented by a particular allocated resource instance. Obviously, an instance operation set of (t, i) is a subset of the operation set of t, i.e. C 0(t), and the union of the instance operation sets for all... 

For each partition M there are a groups, where a block in this context is identical to an instance operation set defined earlier. The O operations are assigned to these blocks in turn. The number of possible assignments is computed... 

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. 

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. 

Figure 7.2 Illustrating hierarchical nature of instance operation sets Gi is the main graph containing vi, and Gi is the loq) body containing vj.

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. 

The objective in conflict resolution is to resolve the conflicts among elements of a candidate operation set 0(t,)(G), which is derived from a resource binding / and a constraint graph model G V, E). An ordering of the instance operation set is defined as follows. 

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

Definition 7.2.1 An operation cluster C of an instance operation set O is the maximal subset of vertices in O that is strongly connected, i.e. there exists a directed path between every pair of vertices in the operation cluster. C denotes the cardinality of C. 

Proof Elements of an instance operation set are strongly connected in the constraint graph. Since strong connectivity is an equivalence relation, two operation clusters cannot be connected by a cycle. This is the definition of partial order. 

This partial order over the operation clusters provides the basis for a conflict resolution strategy based on decomposition. Specifically, the problem of finding a valid ordering for an instance operation set is divided into two steps ... 

Proof Assume each operation cluster has a valid ordering. Since clusters are not connected by a cycle, the serialization of one cluster does not affect any cyclic constraints of the other operation clusters. Since each cluster is ordered and no constraints are violated by ordering among the clusters, the resulting ordering is valid for the entire instance operation set. ... 

Algorithms for conflict resolution is presented in this section. The input is a resource binding consisting of a number of instance operation sets. The instance op tion sets in / are selected in turn. For a given instance operation set O, its operation clusters are first identified using standard graph techniques... 

---