Skip to content

SYRK does not scale with threads for K >> N (tall-skinny A.T @ A), slower than GEMM #6261

Open

Description

@lorentzenchr

Summary

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.

from time import perf_counter

import numpy as np
from threadpoolctl import threadpool_limits


def best_time(func, n_repeat=5):
    func()  # warm-up
    times = []
    for _ in range(n_repeat):
        start = perf_counter()
        func()
        times.append(perf_counter() - start)
    return min(times) * 1e3


rng = np.random.default_rng(0)
print(f"{'K':>9} {'N':>5} {'threads':>7} {'gemm [ms]':>10} {'syrk [ms]':>10}")
for K, N in [(100_000, 100), (1_000_000, 50), (1_000_000, 200), (20_000, 1000)]:
    A = rng.standard_normal((K, N))
    B = A.copy()
    for n_threads in [1, 8, 16]:
        with threadpool_limits(limits=n_threads, user_api="blas"):
            t_gemm = best_time(lambda: A.T @ B)
            t_syrk