Example

We return to our call graph example to describe how the method will allocate the nodes. Consider fig. 4.1, where we allocate the call graph to three processors. The algorithm spots that the right hand sub tree, where all the paths begin with c, is completely independant and allocates it on the last third of the processors, in this case solely on processor 1. The remaining part has commutative directions so is allocated to the first two-thirds of the processors, namely processors 2 and 3. Within that, the allocation is done as if it were a list, paths with one a go onto processor 2, those with two go on processor 3. Similary for one and two bs. Clearly, from looking at the diagram, there should be a better mapping of the nodes to processors, as in fig. 4.2. This is the sort of distribution that we would want from a dynamic allocation scheme.

 

Figure 4.1:   Allocation of nodes in the call graph

 

Figure 4.2:   A better allocation of nodes for the call graph