Input-Aware Sparse Tensor Storage Format Selection for Optimizing MTTKRP

doi:10.1109/TC.2021.3113028

2021-01-01

PRE

DOI：10.1109/TC.2021.3113028

原文链接

原文求助

摘要

En 中文

Canonical polyadic decomposition (CPD) is one of the most common tensor computations adopted in many scientific applications. The major bottleneck of CPD is matricized tensor times Khatri-Rao product (MTTKRP). To optimize the performance of MTTKRP, various sparse tensor formats have been proposed such as CSF and HiCOO. However, due to the spatial complexity of the tensors, no single format fits all tensors. To address this problem, we propose SpTFS, a framework that automatically predicts the optimal storage format for an input sparse tensor. Specifically, SpTFS leverages a set of sampling methods to lower the sparse tensor to fixed-sized matrices and sparsity features. In addition, SpTFS adopts both supervised learning based and unsupervised learning based methods to predict the optimal sparse tensor storage formats. For supervised learning, we propose TnsNet that combines convolution neural network (CNN) and the feature layer, which effectively captures the sparsity patterns of the input tensors. Once trained, the TnsNet can be used with either density or histogram representation of the input tensor for optimal format prediction. Whereas for unsupervised learning, we propose TnsClustering that consists of a feature encoder using convolutional layers and fully connected layers, and a K-means++ model to cluster sparse tensors for optimal tensor format prediction, without massively profiling on the hardware platform. SpTFS can use the above two models to predict the optimal tensor storage format for accelerating MTTKRP accurately. The experimental results show that both TnsNet and TnsClustering can achieve higher prediction accuracy and performance speedup compared to the state-of-the-art works.

Keyword:

Tensors

Sparse matrices

Hardware

Convolutional neural networks

Matrix decomposition

Unsupervised learning

Task analysis

Tensor computation

MTTKRP

sparse tensor storage format

convolutional neural network