You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
{{ message }}
Repository navigation
SYRK does not scale with threads for K >> N (tall-skinny A.T @ A), slower than GEMM #6261
For tall-skinny matrices A of shape (K, N) with K >> N, ?syrk (computing A.T @ A) shows little to no speedup with multiple threads, while ?gemm on the same shapes scales well. As a result, SYRK is up to 2.5x slower than GEMM on a 16-core machine, although it is faster single-threaded, as expected from needing half the flops.
This shape is typical for Gram / Hessian matrices in statistics and machine learning (n_samples >> n_features). We found it in scikit-learn/scikit-learn#35283, where we tried to replace GEMM by SYRK for X.T @ diag(w) @ X.
Environment
OpenBLAS 0.3.34.106.0 (scipy-openblas64 as shipped in the numpy wheel), pthreads, detected architecture SkylakeX
CPU: AMD Ryzen 9 9950X3D (16 cores / 32 threads)
Linux, Python 3.13
Timings
From the scikit-learn benchmark, float64, time in ms. Both variants include the same single-threaded O(K * N) scaling of A beforehand, so the difference is GEMM vs SYRK.
K × N
threads
GEMM
SYRK
100,000 × 100
1
30.9
28.9
100,000 × 100
8
12.7
29.0
100,000 × 100
16
11.7
28.9
1,000,000 × 50
1
115.7
108.9
1,000,000 × 50
8
64.0
107.3
1,000,000 × 50
16
63.9
108.4
1,000,000 × 200
1
919.5
743.1
1,000,000 × 200
8
268.1
291.7
1,000,000 × 200
16
296.2
740.0
20,000 × 1,000
1
334.9
190.7
20,000 × 1,000
16
44.9
39.7
Observations:
For N = 50 and N = 100, the SYRK time is independent of the number of threads.
For 1,000,000 × 200, SYRK is faster with 8 threads, but with 16 threads it is back at the single-threaded time.
For larger N (20,000 × 1,000), SYRK scales fine.
float32 shows the same pattern.
Reproducer
numpy dispatches A.T @ A to ?syrk and A.T @ B to ?gemm.
Summary
For tall-skinny matrices
Aof shape(K, N)withK >> N,?syrk(computingA.T @ A) shows little to no speedup with multiple threads, while?gemmon the same shapes scales well. As a result, SYRK is up to 2.5x slower than GEMM on a 16-core machine, although it is faster single-threaded, as expected from needing half the flops.This shape is typical for Gram / Hessian matrices in statistics and machine learning (
n_samples >> n_features). We found it in scikit-learn/scikit-learn#35283, where we tried to replace GEMM by SYRK forX.T @ diag(w) @ X.Environment
scipy-openblas64as shipped in the numpy wheel), pthreads, detected architectureSkylakeXTimings
From the scikit-learn benchmark, float64, time in ms. Both variants include the same single-threaded
O(K * N)scaling ofAbeforehand, so the difference is GEMM vs SYRK.Observations:
float32 shows the same pattern.
Reproducer
numpy dispatches
A.T @ Ato?syrkandA.T @ Bto?gemm.