Communication is needed to move data between tasks. Divide computation into separate tasks. Data requirements of these tasks may be disjoint or they may overlap significantly An example of problem for which functional decomposition is appropriate is a search tree problem. Functional Decomposition A simulation of the earth's climate comprises atmosphere, ocean, hydrology, etc. Communication Tasks generated by above partitioning intended to execute concurrently, but not independently The computation to be performed in one task requires data from another.
Information flow is specified in communication phase.
In first two phases, we partitioned the computation to be performed into a set of tasks and introduced communication to provide data required by these tasks. In agglomerate stage, we consider if it is useful to combine tasks to provide smaller number of tasks Determine if worthwhile to replicate data or computation. Examples of Agglomeration Increasing Granularity In partitioning phase, efforts focused on exposing parallelism. Use a sum reduction followed by a broadcast takes in ring and for a tree. These are conflicting goals Example of Mapping Mapping Problem Mapping problem to minimize execution time is NP-complete, i.e. no polynomial time algorithm exists for optimal solution.