We address the development of efficient methods for performing data redistribution of arrays on distributed-memory machines. Data redistribution is important for the distributed-memory implementation of data parallel languages such as High Performance Fortran. An algebraic representation of regular data distributions is used to develop an analytical model for evaluating the communication cost of data redistribution. Using this algebraic representation and the analytical model, an approach to communication-efficient data redistribution is developed. Implementation results on the Intel iPSC/860 are reported.

Presents EXTENT (EXpert system for TENsor product formula Translation) which is a programming environment for the automatic generation of parallel/vector programs from tensor product formulas. A tensor (Kronecker) product based programming methodology is used for designing high-performance programs on various architectures. In this programming methodology, block recursive algorithms such as the fast Fourier transform and Strassen's matrix multiplication algorithm are expressed as tensor product formulas involving tensor product and other matrix operations. A tensor product formula can be systematically translated into parallel and/or vector code for various parallel architectures. A prototype system which generates programs for the Cray Y-MP, Cray T3D and Intel Paragon has been developed. Performance results for some generated programs are presented.>

Efficient generation of communication sets and local index sets is important for evaluation of array expressions in scientific languages such as Fortran-90 and High Performance Fortran implemented on distributed-memory machines. We show that for arrays affinely aligned with templates that are distributed on multiple processors with a block-cyclic distribution, the local memory access sequence and communication sets can be efficiently enumerated using closed forms. First, closed form solutions are presented for arrays that are aligned with identity template that are distributed using block or cyclic distributions.

We p~esent transposition a~gorithms fo?' matrices that do not fit in main memory.Transposition is interpreted m a permutation of the vector obtained by mapping a matriz to linear memoTy.A lgopithms am derived j%om factorization of this perm~tation, using a class of permutations related to the tensor prodwt.Using this formulation of transposition, we jirst obtain seveTal known aigo?'ithms and then we derive a new algorithm which Teduces the number of dish accesses TequiTed.The new algoTithm was compaTed to ezisting algorithms wing an implementation on the Intel iPSC/860.Thti comparison shows the benefits of the new aigoTithm.

The authors present an algebraic theory based on tensor products for modeling direct interconnection networks. This theory has been used for designing and implementing block recursive numerical algorithms on shared-memory vector multiprocessors. This theory can be used for mapping algorithms expressed in tensor product form onto distributed-memory architectures. The authors focus on the modeling of direct interconnection networks. Rings, n-dimensional meshes, and hypercubes are represented in tensor product form. Algorithm mapping using tensor product formulation is demonstrated by mapping matrix transposition and matrix multiplication onto different networks.>