The goal of the proposed work is to develop techniques to support the serial to parallel conversion of algorithms in such a way as to create parallel algorithms that minimize completion time. The techniques are based on a graph decomposition scheme that efficiently exploits possibilities for parallelism in the sequential algorithms and identifies concurrent activities for scheduling on available processors. Communication costs between processors impact heavily on the execution time of parallel programs. Algorithm degradation can be severe due to communication costs both in terms of resource utilization and waiting delay. A higher degree of concurrency necessarily requires a greater communication cost. The graph decomposition method for determining the parallel equivalent algorithm attempts to find the balance between these two conflicting criteria. It is based on both processor execution costs and interprocessor communication costs and is designed to yield fast execution. As in previous approaches to this problem, a program is represented by a DAG (directed acyclic graph) where nodes represent code segments and edges represent data flow. The concept that make the graph decomposition approach unique is that the data flow graph is partitioned into a hierarchy of subgraphs called clans. Clan capture necessary ordering operations and extract opportunities for concurrency while reducing communication costs. Using this structure, the optimal size code segments that create a degree of concurrency which is optimal when communication costs are considered is determined.
