Transposition-aware matrix multiplication

[daphne-eu]

In GitLab by @pdamme on Mar 1, 2022, 19:24

Matrix multiplications are at the heart of most ML algorithms and can be very expensive in terms of runtime. There are highly optimized routines (e.g., BLAS) for executing matrix multiplications. In many cases, one or both inputs are transposed matrices. Thus, linear algebra libraries like BLAS can efficiently process matrices without materializing the transposed representation. However, DAPHNE's MatMulOp is currently not aware of whether its inputs are transposed. Thus, an expression like C = t(A) @ B; would first transpose A before it calculates the matrix multiplication.

The task is to modify the existing MatMulOp such that it has two boolean flags indicating if the left/right-hand side input is transposed. The DaphneDSL parser shall initially create MatMulOps assuming non-transposed inputs, while a new compiler pass shall identify if an input to a MatMulOp is the result of a TransposeOp and rewrite the program accordingly. Finally, the runtime kernels of the MatMulOp must pass this information on transposition to the BLAS kernels they call internally. Implementation in C++.