344 Chapter 6 Multiprocessor Software
■ Two additional nodes are added to represent the two processors. One such
node is the source of the graph (representing CPU 1) and the other is the sink
(representing CPU 2).
■ Edges are added from each non-sink node to the source and the sink. The
weight of an edge to the source is equal to the cost of executing that node’s
module on CPU 2 (the sink); the weight of an edge to the sink is equal to the
cost of executing that node’s module on CPU 1 (the source).
The cutset divides the intermodule connection graph into two sets, with the
nodes in each set being assigned to the same processor. The weight of a cutset is
the cost of an assignment of the nodes to the two processors as given by the cut-
set. To find the ...