To satisfy the type consistency constraint, we modify the dynamic programming algorithm as follows. First, we add binning strings to each node. The purpose of the binning strings is to ensure that the dynamic programming algorithm uses type consistent mapping solutions for nodes along different paths to any reconvergent fanout node. The computation of the binning strings relies on the notion of primary and secondary reconvergent nodes of a given node in the graph and uses the Floyd-Warshall algorithm [CLR90] to compute the transitive closure of a graph. Details are omitted due to lack of space. Second, in the solution of [CP96], the post-order and pre-order traversals are performed on the individual PO's sequentially. This approach may however lead to a type inconsistent solution. We thus add some dummy nodes and a root with zero cost and zero delay to merge different PO's into a single root.
As a result of the binning string computation, each node (subprocess) will have several bins, and each bin will have an associated tag which describes the implementations used for each process in the binning string of the node.