willy-rabe opened a new pull request, #2544: URL: https://github.com/apache/systemds/pull/2544
[SYSTEMDS-3168] Add optimized transposed dense-sparse and sparse-dense matrix multiplication kernels. ## Summary This PR adds specialized matrix multiplication kernels in `LibMatrixMult.java` for transposed multiplication cases involving dense-sparse and sparse-dense inputs: - A %*% t(B) - t(A) %*% B - t(A) %*% t(B) The new implementations avoid materializing transposed intermediates where possible and use format-aware execution paths to improve performance and reduce memory overhead. ## Testing New correctness and performance tests added to: - `src/test/java/org/apache/sysds/test/component/matrixmult/MatrixMultTransposedTest.java` - `src/test/java/org/apache/sysds/test/component/matrixmult/MatrixMultTransposedPerformanceTest.java` These validate correctness and measure performance improvements for the newly implemented kernels. ## Performance Evaluation The following benchmarks evaluate the execution time of the optimized transposed kernels compared to the baseline (explicit transposition followed by standard matrix multiplication). * **Environment:** Intel Core Ultra 5 228V CPU * **Setup:** 100 repetitions, 50 warmup iterations. * **Results:** Average execution time in milliseconds (ms) and corresponding speedups. ### 1. Sparse-Dense Transposed Kernels (A is Sparse, B is Dense) | Expression | Sparsity (A) | Matrix Size ($m=n=k$) | Baseline (Old) | Optimized (New) | Speedup | | :--- | :--- | :--- | :--- | :--- | :--- | | `t(A) %*% B` | 0.01 | 200 | 0.346 ms | 0.079 ms | **4.37x** | | `t(A) %*% B` | 0.01 | 500 | 2.014 ms | 0.421 ms | **4.78x** | | `A %*% t(B)` | 0.01 | 200 | 0.090 ms | 0.100 ms | 0.90x | | `A %*% t(B)` | 0.01 | 500 | 3.501 ms | 0.801 ms | **4.37x** | | `t(A) %*% t(B)`| 0.01 | 200 | 0.132 ms | 0.077 ms | **1.72x** | | `t(A) %*% t(B)`| 0.01 | 500 | 0.677 ms | 0.658 ms | **1.03x** | | | | | | | | | `t(A) %*% B` | 0.05 | 200 | 0.094 ms | 0.098 ms | 0.96x | | `t(A) %*% B` | 0.05 | 500 | 2.614 ms | 1.335 ms | **1.96x** | | `A %*% t(B)` | 0.05 | 200 | 0.148 ms | 0.169 ms | 0.88x | | `A %*% t(B)` | 0.05 | 500 | 1.258 ms | 2.346 ms | 0.54x | | `t(A) %*% t(B)`| 0.05 | 200 | 0.183 ms | 0.119 ms | **1.53x** | | `t(A) %*% t(B)`| 0.05 | 500 | 2.180 ms | 2.040 ms | **1.07x** | ### 2. Dense-Sparse Transposed Kernels (A is Dense, B is Sparse) | Expression | Sparsity (B) | Matrix Size ($m=n=k$) | Baseline (Old) | Optimized (New) | Speedup | | :--- | :--- | :--- | :--- | :--- | :--- | | `t(A) %*% B` | 0.01 | 200 | 0.348 ms | 0.119 ms | **2.92x** | | `t(A) %*% B` | 0.01 | 500 | 2.724 ms | 2.294 ms | **1.19x** | | `A %*% t(B)` | 0.01 | 200 | 0.312 ms | 0.272 ms | **1.15x** | | `A %*% t(B)` | 0.01 | 500 | 2.409 ms | 2.193 ms | **1.10x** | | `t(A) %*% t(B)`| 0.01 | 200 | 0.373 ms | 0.099 ms | **3.76x** | | `t(A) %*% t(B)`| 0.01 | 500 | 2.801 ms | 1.298 ms | **2.16x** | | | | | | | | | `t(A) %*% B` | 0.05 | 200 | 0.710 ms | 0.527 ms | **1.35x** | | `t(A) %*% B` | 0.05 | 500 | 6.420 ms | 7.472 ms | 0.86x | | `A %*% t(B)` | 0.05 | 200 | 0.581 ms | 0.465 ms | **1.25x** | | `A %*% t(B)` | 0.05 | 500 | 6.187 ms | 4.421 ms | **1.40x** | | `t(A) %*% t(B)`| 0.05 | 200 | 0.628 ms | 0.355 ms | **1.77x** | | `t(A) %*% t(B)`| 0.05 | 500 | 6.369 ms | 6.069 ms | **1.05x** | ```*** -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
