High performance streaming tensor decomposition

We present a new algorithm for computing tensor decomposition on streaming data that achieves up to 102× speedup over the state-of-the-art CP-stream algorithm through lower computational complexity and performance optimization. For each streaming time slice, our algorithm partitions the factor matrix rows into those with and without updates and keeps them in Gram matrix form to significantly reduce the required computation. We also improve the scalability and performance of the matricized tensor times Khatri-Rao product (MTTKRP) kernel, a key performance bottleneck in many tensor decomposition algorithms, by reducing the synchronization overhead through the combined use of mutex locks and thread-local memory. For problems with constraints (e.g., non-negativity), we apply data blocking and operation fusion to the alternating direction method of multiplier (ADMM) kernel in the constrained CP-stream algorithm. By combining this ADMM optimization with the aforementioned MTTKRP optimization, our improved algorithm achieves up to 47× speedup over the original. We evaluate the performance and scalability of our new algorithm and optimization techniques using a 56-core quad-socket Intel Xeon system on four representative real-world tensors.