Abstract
In our recent work, we have been working on providing parallel sparse supports for array intrinsics of Fortran 90. Our supporting library uses a two-level design. In the low-level routines, it requires the input sparse matrices to be specified with compression/distribution schemes for array functions. In the high-level representations, sparse array functions are overloaded with Fortran 90 array intrinsic interfaces so that programmers need not be concerned about low-level details. This raises a very interesting optimization problem in the strategies to transform high-level representations to low-level routines by automatic selections and supplies of distribution and compression schemes for sparse arrays. We propose solutions to this optimization problem. The optimization problem is shown to be NP-hard. We develop a heuristic algorithm based on annotated program graphs, and the algorithm is shown to be practical. Experimental results on an IBM SP-2 show that the selection algorithms are effective in improving the performances of application programs that use sparse data sets.