VIENNA-FORTRAN HPF EXTENSIONS FOR SPARSE AND IRREGULAR PROBLEMS AND THEIR COMPILATION/

Vienna Fortran, High Performance Fortran (HPF), and other data paralle l languages have been introduced to allow the programming of massively parallel distributed-memory machines (DMMP) at a relatively high leve l of abstraction, based on the SPMD paradigm. Their main features incl ude directives to express the distribution of data and computations ac ross the processors of a machine. In this paper, we use Vienna-Fortran as a general framework for dealing with sparse data structures. We de scribe new methods for the representation and distribution of such dat a on DMMPs, and propose simple language features that permit the user to characterize a matrix as ''sparse'' and specify the associated repr esentation. Together with the data distribution for the matrix, this e nables the compiler and runtime system to translate sequential sparse code into explicitly parallel message-passing code. We develop new com pilation and runtime techniques, which focus on achieving storage econ omy and reducing communication overhead in the target program. The ove rall result is a powerful mechanism for dealing efficiently with spars e matrices in data parallel languages and their compilers for DMMPs.