Run-time data redistribution can enhance algorithm performance in distributed-memory machines. Explicit redistribution of data can be performed between algorithm phases when a different data decomposition is expected to deliver increased performance for a subsequent phase of computation. Redistribution, however, represents increased program overhead as algorithm computation is discontinued while data are exchanged among processor memories. In this paper, we present a technique that minimizes the amount of data exchange for BLOCK to CYCLIC(c) (or vice-versa) redistributions of arbitrary number of dimensions. Preserving the semantics of the target (destination) distribution pattern, the technique manipulates the data to logical processor mapping of the target pattern. When implemented on an IBM SP, the mapping technique demonstrates redistribution performance improvements of approximately 40% over traditional data to processor mapping. Relative to the traditional mapping technique, the proposed method affords greater flexibility in specifying precisely which data elements are redistributed and which elements remain on-processor.

Determining an appropriate data distribution among different memories is critical to the performance of data-parallel programs on distributedmemory machines. By analyzing the computational load of data arrays and the communication cornplexity of various data movement operations in a program, this paper suggests a first-order cost model for determining a small set of appropriate data distribution patterns among many possible choices. A new data distribution specification, name! y CYBLOCK, is proposed to enhance the expressiveness of data distribution specifications being proposed in High Performance Fortran. Cost analysis of two case studies: a linear system solver and a Purdue-set benchmark loop, are used to illustrate the proposed evaluation method. The model correctly predicts the relative performance of the case studies when implemented with various regular data distributions on an nCUBE- 2 multicomputer.

This paper examines some crtttcal tssues raised in the design of libraries for MPCS, such as scalability, portability, recompilation, and flexibility.we adUocate a layered structure of it brary design, comprising a high-level language layer, a machine-independent node layer, a machine-dependent node layer, and an object code layer for diflerent demands and requirements.We discuss the impact of various data decomposition strategies on program performance and the computation and communication analysts techniques employed at different layers.We also propose the concept of the range of scalability as a metric for selectzng the most appropriate implementation.A linear system solver based on the Gaussian elimination method is used as an example to illustrate various design alternates.nessee and Oak Ridge National Laboratory attempts to provide a scalable LAPACK package for dense and banded matrix computations [3].The ComPaSS library being developed at Michigan State University attempts to provide a set of scalable communication

The authors describe the initial implementation of the ComPaSS communication library to support scalable software development in massively parallel processors. ComPaSS provides high-level global communication operations for both data manipulation and process control, many of which are based on a small set of low-level communication primitives. The ComPaSS library is unique in that these low-level operations are provably optimal for a class of architectures representative of many commercial scalable systems-in particular, those using wormhole routing and n-dimensional mesh network topologies. The authors concentrate on the multicast component of the ComPaSS library, which is useful in several data parallel operations. The design of the multicast primitive is described, and an example of its use in a data parallel application is given. Improvements in performance resulting from use of the library on a 64-node nCUBE-2 are presented.>