Allocation conflict graph

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. 

The above theorems imply that conflict-free allocation /(<) can be evaluated efficiently because the concurrency factor can be computed in polynomial time. This point is worth emphasizing. The conflict-free allocation indicates the degree of parallelism among the operations of a given resource type. It corresponds to the extent resource conflicts are present in a graph. If the conflict-free allocation satisfies the required resource constraints, then it is not necessary to allocate more resources than this amount to obtain an implementation that satisfies the timing constraints. 

---