Automatic computation and data decomposition algorithm with no communication

For distributed memory machines the speed that processor accesses local memories is much faster than its speed to access remote memories. Thus how to decompose data and computation properly to achieve maximum parallelism and minimum communication is a key issue of automatic parallel compilation. In this paper, the authors present an automatic decomposition algorithm based on constraint equations. Using the algorithm, a data and computation decomposition result with no communication can be achieved. By releasing these constraint equations, the authors get decomposition result with more parallelism. As the result may have communications, so an improved method to eliminate some communications by data replication is also presented.