04. System Synthesis HW/SW Partitioning

• allocation

  • selection and providionong of processing (memory, communication) resources

• mapping:

  • assignment of functions (data, communicatoin) to resources

• scheduling:

  • determinatoin fo execution sequences and start times for tasks/proicesses under consideration of data dependencies in the task graph

• determine

  • type and number of CPU/DSP cores

  • size,type,instances of memories

  • standard and application specific hardware building blocks

  • I/O interfaces

  • interconnect structures

• assignment of entire sub-systems / tasks of the system model to HW/SW resources (HW/SW codesign)

• determine the

  • executoin sequences of tasks and communucation transactions between different resources

  • execution of sequences of tasks which have been mapped to the same resources

• directed, acyclic graph wiht set of vertices V and set of edges E

• each vertex represents a task (process, assignment, operation)

• each edge represents a data dependency between two verteces

• bipartite graph with set of vertices and edges

  • bipartit:= can be split into two subsets with no vertices inside itself

  • => divided into resources and tasks

• each vertex represents particular type of resource (e.g. CPU, ASIC, memory, bus)

• each edge denotes the relizability of a task on an instance of resource type (task -> resource type)

• cost function (c: V_T -> Z0) assigns a cost to each resource type

• weight function w:E_R -> Z0 assigns executoin time w_i,k of v_i (task) on r_k (resource) to each edge…

=> i.e. outside vertices: tasks

inside vertices: resources

cost in purple for resources

weigth of edges: execution time for specific task <-> resourece combination…

• graph with set of edges and vertices

• vertices represent function resource instances (i.e. CPU1, CPU2, ASIC, memory, bus,…)

• edge represents directed communicatoin channel

• allocation is a funciotn that assigns each resource a number of available resource instances

=> entire set of allocated resources plus associated communicatoin links correspond to the architecture graph…

• tuple (ß, y) of functions where:

• ß(task) -> resource type

• y(task) -> instance of resource type which executes the task

• Partition: assign each vertex of task graph to exactly one vertex of an architecture graph

  • => assigns tasks the resources…

• Problem objective: identify partition with lowest cost for a given target function

• Partition P = {p1, p2, …, pm)

• pi corresponds to set of all tasks vj mapped to the ressource qi (j != i)

• to be determined:

  • p1 U…U pm = V (all tasks mapped)

  • pi intersection pj = {} for all i,j: i =! j (no task mapped multiple times)

  • Target functoin (P) =

    • k1 x area(P) + k2 x latency(P) + k3 x power(P) = min