Large array decomposition for parallel processing by array base shifting.

摘要

The processing of large arrays on parallel systems has many applications. One of these is the solution of partial differential equations using the iterative calculation approach. This method is very computationally intensive, and, depending on the method of partitioning and computation can be very communication intensive. The last definitive work on this subject was done in 1991. The methods now commonly used need to be re-examined to see if there is a method of segmentation, computation and communication that can speed up such a solution on emerging popular MIMD and clustered systems by a significant factor. If so that method could be a large contribution to the present and future use of computers in these problems.; In array segmentation the problem of data communications arises at the boundaries of the segments. Values that must be used in calculation are in different machines and must be accessed to complete the calculations. The conventional approach is to exchange boundary values whenever they are needed, resulting in a high volume of short-length communications. The alternative, developed here, is to do all of the calculations in one segment until no further calculations are possible, then exchange a large piece of the original segment. This has the effect of decreasing the communications volume and increasing the average message length. In parallel machines with slow communications set-up, that results in a solution speed up of better than 3 to 1 and could result in a better than 5 to 1 speedup on clustered systems.