Shortest Path Techniques

Efficient extensions of the network flow techniques of the previous chapter to systems made up of four or more processors are not known. However, if the graph of a modular program is constrained in certain ways, it is possible to find the optimal assignment over a system made up of any number of processors in polynomial time. When the graph is constrained to be a tree, a shortest tree algorithm developed by Bokhari (81b) yields the optimal assignment. For the case of series-parallel graphs (which we will define below) an algorithm developed by Towsley (86) can be used. Both algorithms can take the speed of each processor to processor link into account. The tree algorithm can also be used to schedule precedence graphs in a distributed system in which costs vary with time so as to minimize the total cost of execution.