Performance Analysis and Optimization of the Vector-Kronecker Product Multiplication

Alexandre Azevedo (1, 2) , Cristiana Bentes (1, 3) , Maria Clicia Castro (1, 4) , Claude Tadonki (5, 6)

1 UERJ - Universidade do Estado do Rio de Janeiro [Brasil] = Rio de Janeiro State University [Brazil] = Université d'État de Rio de Janeiro [Brésil]
2 Computational Sciences Program
3 Department of Systems Engineering
4 Department of Informatics and Computer Science
5 Mines Paris - PSL (École nationale supérieure des mines de Paris)
6 CRI - Centre de Recherche en Informatique

The Kronecker product, also called tensor product, is a fundamental matrix algebra operation, used to model complex systems using structured descriptions. This operation needs to be computed efficiently, since it is a critical kernel for iterative algorithms. In this work, we focus on the vector-kronecker product operation, where we present an in-depth performance analysis of a sequential and a parallel algorithm previously proposed. Based on this analysis, we proposed three optimizations: changing the memory access pattern, reducing load imbalance and manually vectorizing some portions of the code with Intel SSE4.2 intrinsics. The obtained results show better cache usage and load balance, thus improving the performance, especially for larger matrices.

Domaines: Algorithme et structure de données [cs.DS]; Calcul parallèle, distribué et partagé [cs.DC]; Analyse numérique [cs.NA]

Alexandre Azevedo, Cristiana Bentes, Maria Clicia Castro, Claude Tadonki. Performance Analysis and Optimization of the Vector-Kronecker Product Multiplication. 11th Workshop on Applications for Multi-Core Architectures (WAMCA 2020), in conjunction the 2020 IEEE 32nd International Symposium on Computer Architecture and High Performance Computing (SBAC-PAD), Sep 2020, Porto, Portugal. ⟨10.1109/SBAC-PAD49847.2020.00044⟩. ⟨hal-02958782⟩