OptiCPD: Optimization For The Canonical Polyadic Decomposition Algorithm on GPUs

Tensor decomposition is a key operation in many data analytics and machine learning applications for extracting previously unknown patterns from sparse and/or multivariate data. The Canonical Polyadic Decomposition/Parallel Factors Analysis (CPD/PARAFAC) method, which is based on a combination of sparse and dense linear algebra operations, has received a lot of attention recently and is used in a variety of applications. The Alternate Least Squares Algorithm (ALS) is a numerical optimization algorithm that is used in the CPD/PARAFAC decomposition. It consists of several operations, including MTTKRP (Matrix times Tensor Khatri Rao Product), tall and wide matrix multiplication, and the computation of the pseudo-inverse of the resultant dense matrix. In recent days, GPUs are being used for high-performance computing applications instead of multi-core CPUs. A predominant challenge faced by the GPUs with respect to multicore CPUs is effective resource utilization for the CPD/PARAFAC-ALS algorithm with different levels of complexity and parallelism. To address this challenge we characterize the performance of CPD/PARAFAC-ALS on AMD MI100 GPU and propose OptiCPD as an optimal scheduling mechanism for the CPD/PARAFAC algorithm. Using OptiCPD we were able to achieve an average speedup of 7.5x for certain tensor benchmarks with respect to the existing baseline.