Operation cluster

Definition. The explicit consideration of this stage is the simple ratio of the number of common values between the two operator clusters under consideration to the total number of values for each cluster of operators. Thus,... 

Comparison. Operator similarities are used as criteria for clustering in other programs, but operator clustering in APARTY is different from the operator similarities measured by other clustering programs which consider the similarity of exactly 2 operators. APARTYs operator clustering does not consider individual pairs of operators, but rather compares operator clusters. 

Identify operation clusters - an opo on cluster represents a subset of vertices in the opoation set that are connected by a cycle in the constraint graph, i.e. a cyclic timing requirement is imposed on them. 

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. 

Theorem 7.2.1 A partial order exists among the operations clusters of an operation set. 

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. 

The set of operation clusters is denoted by 77 = Ci, i= 1,..., 1771, where I 77 I is the number of operation clusters in O. The operation clusto form a partition over the elements of O because the property of strong connectivity is an equivalence relation. We illustrate the concept in Figure 7.3, where the dotted arcs represent backward edges with negative weights and the solid arcs represent forward edges with positive weights. There are two operation clusters Cl = A, B, C and 0% = 77, E in the example. A partial order is formed over the two clusters, i.e. ftom C to Cj. 

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

Figure 7.3 Example of an instance op tion set with 5 vertices A,B,C,D,E. Two operation clusters are framed C = A,B,C and C2= D,E. ...

Ordering among the operation clusters Find a linear order of operation clusters that is compatible with the induced partial order in i7, and... 

Ordering within each operation cluster Find a valid ordering for the vertices within each operation cluster. 

Theorem 7.2.2 If valid orderings exist for the vertices inside each operation cluster Ci G n,i =, then any ordering of operation clusters that is... 

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

We introduce in this section the concepts of orientation and polarization of an operation cluster. For conciseness, we consider one operation cluster C that contains C vertices, i.e. C = c< i = 1,..., C. ... 

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. 

Figure 7.4 Example of (a) an operation cluster with 5 vatices 4, B, C, D, E), (b) the corresponding orientation. The roots are A,B, and the leaves are...

Consider for example an operation cluster containing S vertices A,B,C,D,E. The orientation is obtained by retaining only the positively weighted edges. This is shown in Figure 7.4. 

Figure 7.5 Illustrating an operation cluster and its orientation V, a simple polarization V v, vs), and the extended polarization V vi,vs).

Figure 7.6 Four possible polarizations for an operation cluster where bold arcs represent the orientation.

Any valid ordering of an operation cluster must be compatible with one of its polarizations. There is a finite number of polarizations for a given orientation. The total number of possible polarizations for an orientation Vc is given by the expression ... 

Figure 7.6 shows an operation cluster with S votices. The bold arcs are due to the orientation and the shaded vertices denote root and leaf vertices in a polarization. There are 2 2 — 0 = 4 polarizations for this cluster. The concept of polarizations allows us to prune the search for a valid ordering. Since the simple polarization Vc r,l) is a restriction of the polarization Vcir,l), we use strictly V ir, 1) in the rest of the chapter. 

Proof A valid ordering within an operation cluster implies that all vertices are serialized to form a chain. Given a polarization (r, f), r is the first element of the chain and I is the last element of the chain. The minimum length of such a chain is equal to the sum of the execution delays of the vertices excluding the leaf /, i.e. ( )- necessary condition for a valid ordering is that no... 

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

Select a polarization Pc( >0- particular polarization with root r and leaf / is selected. If a cycle exists in the polarization or if the polarization violates the condition in Theorem 7.2.4, then it is discarded and another polarization is selected. If all polarizations are invalid, then the resource conflicts fm the given operation cluster cannot be resolved under timing constraints. 

Example. We illustrate the application of procedure Heuristicj>rder in Figure 7.8 to an operation cluster consists of 7 vertices vi,..., v , starting with the polarization V v, vi). The partial order Ord is constructed from the leaf v upwards to the root v i. At step 1, the candidates based on the partial order of the polarization (represented by bold arcs) are w4, v, ve. The slacks for these candidates are ... 

NiTPP-(piperidine)2. At that initial stage of the APS operation, clusters of six X-ray pulses with a combined duration of 14 ns were used to probe the intermediate structure before the rebinding of the ligands. By today s standards, the experiment was relatively straightforward with only nanosecond time resolution, however, the results demonstrated for the first time (1) the feasibility of XTA measurements at a synchrotron source for a dilute solution (ImM), (2) that structural determination with 100-ps resolution can be achieved using singlet X-ray probe pulses when they were available, (3) what the pros and cons are using the available solid state Ge detector array (Canberra) and (4) that the photodissociation intermediate is square-planar under the time resolution limit. 

---