Disjoint compatibility graph

The concurrency factor of Q can be computed by first constructing an undirected disjoint compatibility graph. Vertices of the disjoint compatibility graph, denoted by Gq = Q,Eq), correspond to elements of Q. Undirected edges Eq indicate when vertices are temporally disjoint, i.e. they cannot execute in parallel. 

Lemma 5,2.1 Given a sequencing graph Gm without conditional and loop vertices, the concurrency factor of a subset cf shareable operations Q CV is equal to the clique cover number of the corresponding disjoint compatibility graph Gq. 

Proof An edge in the disjoint compatibility graph Gq implies that two vertices cannot execute in parallel. Th fore, a clique in Gq corresponds to a subset of vertices that cannot execute in parallel. A clique cover partitions the elements of Q into cliques, and therefore the clique cover number for Gq is equal to the maximum number of elements in Q that can execute in parallel, which is in turn equal to the concurrency factor of Q. ... 

Returning to the example of Figure 5.6, the disjoint compatibility graph G q for the set Q = vi, V2, v, V4 is shown in Figure 5.7(b). A minimum clique cover is shown in (c) where operations within a clique are enclosed in ovals. The concurrency factor is equal to the clique cover number, which is 2. 

Figure 5.10 Derivation of the augmented disjoint compatibility graph from a graph G,- and impropriate weights (a) sequencing graph with weights, (b) disjoint compatibility graph, (c) augmented disjoint compatibility graph.

Proof The weight for a vertex is equal to the maximum number of vertices in Q that can be activated if the vertex is executed. Consider a vertex v and its mapping >l(v). In the augmented disjoint compatibility graph, no path exists between the elements of, 4(v). Furthermore, for any vertex w that is disjoint with respect to v, all elements in the mapping are also disjoint w.r.t. all elements in -4(u). Therefore, Gq captures the degree of parallelism among elements of Q, and we conclude that its clique cover number is equal to the concurrency factor cfactor Gm, 0)- II... 

Theorem 5.2.2 Given a sequencing graph Gm and its cf-hierarchy, the augmented disjoint compatibility graph Gq for a subset of shareable operations Q CV is a comparability graph. 

Proof Follows directly from the derivation of Gq from the corresponding disjoint compatibility graph Gq. The property of transitivi is not affected, and hence Gq is a comparability graph. ... 

In traditional approaches, two vertices are disjoint if they are scheduled into different control steps. However, since our model supports data-dependent delay operations, these approaches cannot be used in general. Assume all operations have unbounded execution delay, then two operations are compatible if they have the same resource type and are joined by a directed path in the sequencing graph. 

---