Shareable operations

Given a resource allocation a, a resource binding for a sequencing graph G, is an assignment of shareable operations V to specific instances of the allocated... 

Figure 5.3 Illustrating the relationship between shareable operations and allocated resources. The allocation is o (A) = 2 and a B) = 1, and the arcs represent the resource binding 0.

Before describing the design space exploration strategy, we introduce first the concept of concurrency factor to measure of the degree of parallelism among subsets of shareable operations Q Q V. This concept is used extensively in resource allocation and heuristic exploration of the design space. 

Definition 5.2.1 Given a cf-Merarchy G%, the concurrency factor of a subset of shareable operations Q C V is the maximum number of vertices in Q that can be executing simultaneously in It is denoted by cfactor Gni, Q)-... 

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. 

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. 

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. 

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. 

---