For a task graph without re-convergent fanout and with only end/begin type communications, the algorithm used in [CP96] can be directly used without going through the process decomposition phase. This algorithm would then produce the optimal hardware/software mapping for a tree-structured task graph (and a good solution for a DAG-structured task graph) under a given timing constraint (deadline) in pseudo-polynomial time. The only modification is to replace the end/begin type communication with a sending process S and to add the required arcs to the task graph.
The algorithm assumes that we are given the area vs. delay curves for different module alternatives (implementations) which match each node of the task graph. Then the algorithm performs a post-order traversal which adds the area vs. delay curves of the children of a node and the module alternatives for the node to build the area vs. delay curve of this node. This step will also use the lower bound merge to delete all inferior points. The post-order traversal will continue until the graph roots are reached. Then a pre-order traversal will commence at the roots using user specified arrival time constraint. The minimum area point on the area vs. delay curve of the root which satisfies the arrival time constraint will determine the module alternative to be used at the root. The pre-order then traverses the children of the root with the new arrival time constraint calculated as the arrival time at the root minus the delay of the module used at root. The recursive procedure will continue until all leaves have been visited.