Conflict-free resource allocation

We define the conflict-free allocation for a resource type t T, denoted by Qcf t), as the minimum allocation of resource type t required to avoid resource conflicts. We state the following theorem. 

Proof We will prove by contradiction. Assume there exists an allocation oiiower t) < oic/it) such that no resource conflicts will arise if aiower(t) resources of type t are allocated. Since aj<, /er(<) < cfactor G,0 t)), there exists at least one resource binding that is derived from the allocation aiower(t) where two operations bound to the same hardware resource may execute in parallel. This results in a resource conflict and hence contradicts the previous assertion that Qiower t) is a conflict-free allocation of t. Therefore, acj t) = cfactor(G,0 t)) is the conflict-free allocation of t. ... 

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. 

On the other hand, if the conflict-free allocation exceeds resource constraints, then additional hardware sharing is required. This results in resource conflicts that must be resolved. Conflict resolution is the subject of Chapter 7. 

Using the conflict-free allocation as guideline, a set of resource allocations ai,...,afc is specified either by the user manually or by the system automatically. Hebe supports both exact and heuristic strategies to explore the design space they are summarized below. 

---