Resource binding

The synthesis algorithm explores the different possible resource binding alternatives by iterating these three tasks. We describe now Hebe s formulation of the design space, and how it is explored in obtaining a desired implementation. 

Formulating the Design Space. More specifically, a resource pool is a set of hardware resources (e.g. implementations of models) with an upper-bound on the number of instances of each type of hardware resources that the user allows in the final implementation. A resource binding is a matching of the operations (i.e. the vertices of the sequencing graph) to specific resources in the... 

Figure S Examples of resource binding, where opmtions within a group are bound to the same resource instance.

Resource binding. Given a resource allocation, many possible bindings of... 

Resource conflict resolution. A resource binding implies a cotain configuration of hardware sharing. In general, resource conflicts can arise when a resource is accessed simultaneously by multiple op tions. These conflicts can be resolved by serializing operations bound to the same resource that can otherwise execute in parallel. Timing constraints must still be satisfied after conflict resolution. 

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.

Examples of different resource bindings for a sequencing graph containing 4 calls are shown in Figure 5.4 (b) through (e). All operations grouped by the... 

The design space of possible resource bindings for Figure 5.4 with allocation a = 2 is illustrated in Figure 5.5. There are seven different resource bindings in the design space. 

An analytical expression for the total number of possible resource bindings P( 0, a) for 0 operations and a allocated instances is the sum of the above expression over the entire set of partitions, as described below. 

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. 

Definition 5.2.2 The conflict degree of a resource binding 0 in a sequencing graph G, denoted by degree 0), is computed as ... 

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

Corollary 5.2.1 Given a sequencing graph G, and a resource allocation ac/(<) for each resource type t T, there exists at least one resource binding I3cf in the design space such that degree Pcj) = 0. 

With the design space formulated as a set of resource bindings for a given resource allocation, Hebe explores the design space to find a favorable implementation with respect to a particular design goal, such as minimal area ot minimal latency. Any valid implementation must satisfy both resource and timing constraints. 

The ranking is based on evaluating the candidate resource bindings with respect to a set of cost criteria. Three cost criteria are supported interconnect. 

Given a candidate resource binding that has been selected, resource conflicts under timing constraints need to be resolved to determine if the binding is valid. If it is valid, then scheduling is performed and the corresponding control logic... 

---