Abstract
Fortran 90 provides a rich set of array intrinsic functions. Each of these array intrinsic functions operates on the elements of multi-dimensional array objects concurrently. They provide a rich source of parallelism and play an increasingly important role in automatic support of data parallel programming. However, there is no such support if these intrinsic functions are applied to sparse data sets. In this dissertation, firstly, we address this open gap by presenting an efficient library for parallel sparse computations with Fortran 90 array intrinsic operations. Our method provides both compression schemes and distribution schemes on distributed memory environments applicable to higher-dimension sparse arrays. This way, programmers need not worry about these low-level details. Sparse programs can be expressed concisely using array expressions, and parallelized with the help of our library. Our sparse libraries are built for array intrinsics of Fortran 90, and they include an extensive set of array operations such as CSHIFT, EOSHIFT, MATMUL, MERGE, PACK, SUM, RESHAPE, SPREAD, TRANSPOSE, UNPACK, and section moves. In addition, we also provide the complete complexity analysis for our sparse implementation. The complexity of our algorithms is in proportion to the number of non-zero elements in the arrays, and that is consistent with the conventional design criteria for sparse algorithms and data structures. In the process of our experiments and design, we found that the sparsity information of sparse arrays are very critical for performance issues, such as compression, distribution, and communication cost. It becomes crucial how we can obtain the sparsity information for arrays of our programs. In this dissertation, we provide a solution to this problem. We provide probabilistic inference schemes to estimate sparsity ratio of target arrays operated based on Fortran 90 array operations and intrinsics. We first present an inference scheme to estimate the sparsity ratio of the target array of an expression using array intrinsic functions of Fortran 90 assuming a uniform distribution of sparsity. Next, we discuss ths issues for the non-uniform distribution of sparse elements. We divide the problems into two categories, elementwise array operations and transformation array operations. For sparse arrays operated on elementwise array operations, we present a segmented inference scheme with the flavor of lattice calculus to predict the sparse structures of arrays. For the case of transformational array operations with non-uniform distributions, we abstractly interpret the probability of a element to be zero pointwise for each target array element, and then present a sampling algorithm to obtain the sparsity structures. Our work gives sparse inference schemes for the complete set of array operations and array intrinsics of Fortran 90 with uniform or non-uniform distributions. On the other hand, due to our sparse library uses a two-level design, this raises a very interesting optimization problem described in the following. In the low-level routines, it requires the input sparse array to be specified with compression/distribution schemes for each function. In the high-level representation, sparse array functions are overloaded for array intrinsic interfaces so that programmers need not concern about the low-level details. What are the strategies to transform the high-level representations to low-level routines by automatic selections and supplies of distribution and compression schemes for sparse data sets? In this dissertation, we propose solutions to address this optimization issue. The optimization problem is shown to be be NP-hard. We develop a heuristic algorithm based on annotated program graphs to select compression schemes and distribution schemes in two phases. At the first phase, we first reduce the graph into a coarse graph.Then a tree-pruning algorithm based on the optimal solution is usedon the reduced graph to perform selections for compression schemes.In the second phase, the distribution scheme is again selected based on the original annotated graph and pruning algorithms. The algorithm is shown to be practical. In addition, we present a generic matrix class in Java and a runtime environment with continuous compilations aiming to support automatic parallelization of sparse computations on distributed environments. Moreover, we also observe the performance of our sparse supports for array intrinsics of Fortran 90 built on top of PC-based networks of clusters.