A New Parallel Algorithm for Sinkhorn Word-Movers Distance and Its Performance on PIUMA and Xeon CPU
Preprint
Abstract
The Word Movers Distance (WMD) measures the semantic dissimilarity between two text documents by computing the cost of optimally moving all words of a source/query document to the most similar words of a target document. Computing WMD between two documents is costly because it requires solving an $O(V^3log(V))$ optimization problem where $V$ is the number of unique words in the document. Fortunately, WMD can be framed as an Earth Mover's Distance (EMD) for which the algorithmic complexity can be reduced to $O(V^2)$ by adding an entropy penalty to the optimization problem and solving it using the Sinkhorn-Knopp algorithm. Additionally, the computation can be made highly parallel by adopting a batching approach, i.e., computing the WMD of a single query document against multiple target documents at once. Sinkhorn WMD is a key kernel used in many ML/NLP applications. and usually gets implemented in Python. However, a straightforward Python implementation may leave significant performance on the table even though it may internally call optimized C++ BLAS routines. We present a new sparse {P}arallel {A}lgorithm for {S}inkhorn-Knopp {W}ord-movers {D}istance to compute the semantic distance of one document to many other documents by adopting the $O(V^2)$ EMD algorithm. We algorithmically transform $O(V^2)$ dense compute-heavy EMD version into an equivalent sparse one using new fused SDDMM-SpMM (sparse selection of dense-dense matrix-, sparse-dense matrix-multiplication) kernels. We implemented and optimized this algorithm for two very different architectures -- the new Intel Programmable Integrated Unified Memory Architecture (PIUMA) and Intel Xeon CPUs. We show that we were able to reach close to peak performance on both platforms.
Keywords
All Related Versions
This publication has 11 references indexed in Scilit:
- FusedMM: A Unified SDDMM-SpMM Kernel for Graph Embedding and Graph Neural Networks2021
- Sparse GPU Kernels for Deep Learning2020
- Classifying Extremely Short Texts by Exploiting Semantic Centroids in Word Mover's Distance Space2019
- BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding2019
- Word Mover’s Embedding: From Word2Vec to Document Embedding2018
- Deep Contextualized Word Representations2018
- Using Centroids of Word Embeddings and Word Mover's Distance for Biomedical Document Retrieval in Question Answering2016
- An Evaluation of High-Level Mechanistic Core ModelsACM Transactions on Architecture and Code Optimization, 2014
- The Sinkhorn–Knopp Algorithm: Convergence and ApplicationsSIAM Journal on Matrix Analysis and Applications, 2008
- A Faster Strongly Polynomial Minimum Cost Flow AlgorithmOperations Research, 1993