Page 346 - DSP Integrated Circuits

7.9 Resource Assignment 331

Figure 7.68 Two different clique selections leading to two and three PE requirements

There are several ways to select the vertices that should belong to a clique.
This freedom can be used to minimize the number of cliques in order to minimize
the number of resources. The problem is to find as large cliques as possible even
though the amount of work represented by each clique becomes larger. Generally,
the problem of finding an optimal set of cliques in a graph is NP-complete.
Sometimes it is more convenient to use another type of graph, which is called
an exclusion graph. In the exclusion graph we connect two vertices with an edge if
the corresponding processes can not share a resource. To perform resource
allocation we try to find sets of vertices that are not connected. All processes
corresponding to unconnected vertices may share a resource.

7.9 RESOURCE ASSIGNMENT

The resource assignment step involves selection of a particular resource from a
pool of resources to execute a certain process. Ideally this assignment should be
made at the same time as the scheduling, but this is not done in practice. Because
of the complexity of the problem, it is instead divided into separate scheduling,
allocation, and assignment steps.
The problem of assigning a class of processes to a corresponding set of
resources can be formulated as a scheduling problem, where processes with com-
patible lifetimes are assigned to the same resource. Graph coloring techniques
may be used to find optimal assignments. The aim is here to assign processes so
that several processes can share the same resource—i.e., to maximize the resource
utilization. Generally, the assignments should be made such that the total cost is
reduced. For example, communication costs should be included.

7.9.1 The Left-Edge Algorithm

We will use a heuristic list-scheduling method related to the well-known left-edge
algorithm commonly used in the VLSI design phase for routing wires. There the goal
is to pack the wires in a routing channel such that the width of the channel is mini-
mized. The width will here correspond to the number of resources. The algorithm
assigns processes to resources in such a way that the resources become fully uti-
lized. However, the left-edge algorithm does not always lead to an optimal solution.