Clique covering

Allocation is performed in two separate steps. First, a complete, functional initial data path is generated. The initial data path is then optimized in a second step. Optimizations are based on the well known clique covering [39], and coloring [19] approaches. 

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.8 Example of computing the concurrency factor by finding clique cover number.

The concurrency factor cfactor Guaf,Q) can be computed using the strategy presented in the previous section by first constructing a disjoint compatibility gr h and then finding its clique cover number. 

As before, weconstructfromG, (Vi, , ) adisjointcompatibilitygraphGQ = (VnztEz) induced by the subset of vertices with non-zero weights, denoted by V z C Vi. From Lemma S.2.2, Gq is a comparability graph because a transitive orientation exists for Gq. If all the weights are 1, then finding a minimum clique cover for Gq is sufficient to compute the concurrency fact( cfactor Gi, Q). 

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

Since Gq is a comparability graph, its clique cover number can be computed in polynomial time [GolSO]. We therefore conclude that given any arbitrary sequencing graph, the concurrency factor for any subset of shareable operations can be computed in polynomial-time. 

---