Handling task graphs with processes that have re-convergent fanout and use midway communication during their lifetime is more difficult. This is because processes in the task graph have to be decomposed into subprocesses, and the communication processes which reflect the blocking/nonblocking communication mechanism have to be inserted. Furthermore, after the decomposition phase, the dynamic programming paradigm must be modified to ensure that the subprocesses which belong to the same original process are mapped to the same hardware or software component instance to maintain the logical coherence and performance. This is achieved in two steps; during scheduling, we ensure that the decomposed subprocesses which correspond to the same original process are mapped to the same HW or SW type with the same utilization factor. During the allocation and binding, we ensure that these subprocesses are further mapped to the same HW or SW component instance.
Theorem 1: Problem 1 is NP-complete.
In practice, the midway communication among coarse-grain processes occurs frequently. The dynamic programming approach of [CP96], may generate a point on the area vs. delay curve of a reconvergent fanout node x which requires inconsistent type assignments for some of the nodes in the transitive fanin cone of x. This is obviously wrong. In addition, using the original algorithm in [CP96], during the post-order graph traversal, we may drop some points which are actually required to generate the optimal solution.