Performance modeling and prediction for linear algebra algorithms

This dissertation incorporates two research projects: performance modeling and prediction for dense linear algebra algorithms, and high-performance computing on clouds. The first project is focused on dense matrix computations, which are often used as computational kernels for numerous scientific applications. To solve a particular mathematical operation, linear algebra libraries provide a variety of algorithms. The algorithm of choice depends, obviously, on its performance. Performance of such algorithms is affected by a set of parameters, which characterize the features of the computing platform, the algorithm implementation, the size of the operands, and the data storage format. Because of this complexity, predicting algorithmic performance is a challenging task, to the point that developers are often forced to rely on extensive trial-and-error technique. We approach this problem from a different perspective. Instead of performing exhaustive tests, we introduce two techniques for modeling performance: one is based on measurements and requires a limited number of sampling tests, while the other needs neither the execution of the algorithms nor parts of them. Both techniques employ a bottom-up approach: we first model the performance of the BLAS kernels. Then, using these results we create models for higher-level algorithms, e.g. the LU factorization, that are built on top of the BLAS kernels. As a result, by using the hierarchical and modular structure of linear algebra libraries, we develop two techniques for hierarchical performance modeling; both techniques yielding accurate predictions. The second project is concerned with high-performance computing on commercial cloud environments. We empirically study the computational efficiency of compute-intensive scientific applications in such an environment, where resources are shared under high contention. Although high performance is occasionally obtained, contention for the CPU and cache space degrades the expected performance and introduces significant variance. Using the matrix-matrix multiplication kernel of BLAS and the LINPACK benchmark, we show that the underutilization of resources substantially improves the expected performance. For instance, for a number of cluster configurations, the solution is reached considerably faster when the available resources are underutilized. Finally, since the performance measurements of scientific applications show high fluctuation, we propose alternatives, such as expected performance, expected execution time, and cost per GFlop, to the standard definitions of efficiency