ZAKI+: A Machine Learning Based Process Mapping Tool for SpMV Computations on Distributed Memory Architectures

Abstract

Smart cities and other cyber-physical systems (CPSs) rely on various scientific, engineering, business, and social applications that provide timely intelligence for their design, operations, and management. Many of these scientific and analytics applications require the solution of sparse linear equation systems, where sparse matrix-vector (SpMV) product is a key computing operation. Several factors determine the performance of parallel SpMV computations, including matrix characteristics, storage formats, and the rising complexity and heterogeneity of computer systems. There is a pressing need for new ways of exploiting parallelism, and mapping data and applications to the computing resources. We propose here ZAKI+, a data-driven machine-learning approach, allowing users to automatically, effortlessly, and speedily obtain the best configuration (the data distribution, the optimal number of processes, and mapping strategy) and performance for the execution of the parallel SpMV computations on distributed memory machines. We train and test the tool using three machine learning methods-decision trees, random forest, and Xtreme boosting-and nearly 2000 real-world matrices obtained from 45 application domains, including computer vision and robotics. ZAKI+ provides optimal process mapping and outperforms the MPI default mapping policy by a factor of 4.24. This is the first work where the sparsity structure of matrices has been exploited to predict the optimal mapping of processes and data in distributed-memory environments by using different base and ensemble machine learning methods. Various CPSs comprise compute-intensive machine learning applications, such as the SpMV, and hence, the process and data mapping contributions of this paper would be of paramount impact for the CPSs.

Keywords

• Cyber-physical systems
• SpMV
• sparse linear algebra
• sparse matrices
• machine learning
• MPI