BLAS and LAPACK
BLAS and LAPACK are dense numerical linear algebra packages. SCS uses these libraries in the following places:
To compute the eigen-decomposition for the semidefinite cone projection (see below), and the eigen-decompositions and singular value decompositions for the spectral cones
To solve the linear system in Anderson acceleration
To form and factorize the matrix in the dense direct linear solver
To compute the eigenvectors that the indirect linear solver uses for deflation
For the basic vector operations (norms, inner products, scaling and adding vectors), which are plain C loops otherwise
Compiling with BLAS / LAPACK is optional: SCS builds and runs without
them. A build without them cannot solve SDPs (the setup fails for a
semidefinite cone larger than \(1 \times 1\)), cannot include the spectral
cones or the parallel PSD projection, does not
apply Anderson acceleration (whatever the value of
acceleration_lookback), does not have the dense direct linear solver,
and runs the indirect linear solver without deflation. If you need none of
these then there is no need to use these libraries. To compile without these
libraries you can set the
compiler flag USE_LAPACK to 0, e.g., if
installing using make:
make USE_LAPACK=0
If you do want any of the above, then you will need to install BLAS and LAPACK libraries (these are pre-installed in most machines). If calling SCS from another language (Python, MATLAB etc.) then these libraries should be pre-installed and SCS will try to link against them. Otherwise you may need to install a copy yourself. A good library to start with is OpenBLAS, which contains both BLAS and LAPACK.
There are many different BLAS and LAPACK libraries that conform to the same API. Finding one that is optimized for your machine can make a big difference to the speed of the operations in practice. If the speed of the SDP projection or the acceleration step is a bottleneck you can experiment with faster libraries like MKL or ATLAS.
Projection onto the PSD cone
SCS projects each positive semidefinite (PSD) block onto the cone with a LAPACK
eigendecomposition, and rebuilds the block from the eigenvectors of its
positive eigenvalues with a BLAS product (syrk, or herk for a
complex block). For a real block the eigendecomposition is LAPACK’s
divide-and-conquer routine syevd (for a complex block see
Complex blocks). On most SDPs this is where most of the time
of an iteration goes, so the LAPACK library, and the
number of threads it runs on, matter.
What it costs and gains
Earlier versions of SCS used the MRRR routine syevr. Compared with it,
syevd:
is faster: on the SDPLIB problems the projection takes 29% to 51% less time per iteration (geometric mean over the problems) with OpenBLAS, NVPL, MKL and Apple Accelerate, and a whole iteration 28% to 47% less (OpenBLAS, NVPL and Accelerate). It gains most on blocks with exactly repeated eigenvalues, which
syevris slow on:thetaG11is projected 2.7 to 2.9 times faster. With the BLAS on one or four threads, no problem’s projection took more than 2.3% longer per iteration, exceptqap8on a slow core of a chip with fast and slow cores (11% to 16%).is as accurate or more: errors of \(2\) to \(4 \times 10^{-15}\) relative to the largest entry of the projection, against \(3\) to \(9 \times 10^{-15}\), on blocks with repeated eigenvalues.
needs more memory:
syevd’s work array has about \(2n^2\) entries for a block of size \(n\), wheresyevrneeded \(n^2\) for the eigenvectors, so the projection of a block takes about \(3n^2\) floating-point numbers instead of \(2n^2\). In double precision that is 600 MB instead of 400 MB for a block of size 5000.starts the threads of a multithreaded BLAS at smaller blocks: with the BLAS at its default, on all 20 cores of a chip with 10 fast and 10 slow cores, problems whose largest block has size 45 to 130 took up to 2.1 times as long in the projection as with
syevr(control7), and OpenBLAS kept 15 to 20 cores busy wheresyevrkept 3 to 12. Such problems are faster on one thread than at the default, with either routine: see Number of BLAS threads.
Complex blocks
SCS decomposes a complex (Hermitian) PSD block with heevd, the complex
counterpart of syevd, where earlier versions used heevr. We
compared the two in whole solves of 28 problems with complex blocks of size 2
to 300 (quantum fidelity, PPT relaxations, channel capacity, PhaseLift, phase
synchronization, complex max-cut and SCS’s tests), with Apple Accelerate, MKL,
NVPL and OpenBLAS. Both solved every problem, in the same number of
iterations, and over all of them took the same time (heevr 0.3% less,
shifted geometric mean). Compared with heevr, heevd:
is faster with MKL, NVPL and OpenBLAS:
heevrtook 1.15 to 1.25 times as long in the projection per iteration, and with MKL longer at every block size.is faster on blocks with nearly repeated eigenvalues: on the PPT relaxations, where about half of the eigenvalues come in pairs closer than \(10^{-8}\) relative to each other, the solves took 1.07 to 1.69 times as long with
heevr, with every library.is faster on small blocks:
heevrtook 1.07 to 1.43 times as long in the projection on blocks of size 64 or less, with every library.is slower on larger blocks with Accelerate: there
heevrtook 0.91 of the projection time on blocks of size 65 to 150 and 0.71 to 0.74 above. Problems with a block of size 200 to 300 took 1.2 to 1.5 times as long to solve withheevd, and all the problems together 1.1 times (shifted geometric mean). With NVPL,heevrtook 0.91 of the projection time on blocks larger than 150.needs more memory: the projection of a complex block of size \(n\) takes about \(6n^2\) floating-point numbers instead of \(4n^2\).
SDPLIB has no complex blocks.
If LAPACK does not converge
When LAPACK reports that the eigendecomposition of a block did not converge,
SCS decomposes the block again with the QR-based syev (heev
for a complex block). That is slower: forced on 11 SDPLIB problems, the
projection took 1.4 to 3.6 times as long, and the problems were solved as with
syevd. It has happened with Apple Accelerate, whose dsyevd did
not converge on one iterate of thetaG11 (a block of size 801), and whose
dsyevr did not converge on the block of
issue #531. If the QR-based
routine fails as well, the solve stops with status failure and the message
error in project_cones.
Very large blocks
LAPACK counts the entries of its work arrays in its own integers. With 32-bit
integers, the usual case, the \(1 + 6n + 2n^2\) entries that
syevd needs fit up to \(n = 32766\). For a larger block, the setup
fails with a message saying so. Use a BLAS and LAPACK with 64-bit integers
(the compiler flag BLAS64) for blocks that
large, and for blocks larger than \(n = 46340\) SCS’s own 64-bit
integers as well (the compiler flag DLONG): SCS indexes the entries
of a block with numbers up to \(n^2\), which then do not fit in 32 bits.
Number of BLAS threads
The projection of a PSD block is a LAPACK
eigendecomposition (syevd for a real block) and a BLAS product
(syrk or herk). A multithreaded BLAS can split these calls,
and SCS’s other BLAS calls (see the list above), over its own threads, by
default about one per core. Waking and synchronizing the threads has a fixed
cost. In our measurements the default made the projection of blocks of size
up to 300 slower than one thread did, with both libraries; a few threads
gained on blocks of size 500 and more, and on smaller blocks it depended on
the library. The number of threads is set by an environment variable of the
BLAS, so you can choose.
When to set one thread
Put the BLAS on one thread for an SDP whose PSD blocks are all of size 300 or less, in particular when several solves run at the same time, since each would start threads for every core. At their default, the two libraries we measured took 1.5 to 2.5 times as long as on one thread on blocks of size 37 to 300 (geometric means, see What we measured). On 4 threads NVPL was slower than on one as well (1.18 to 1.28 times), while OpenBLAS was faster on blocks of size 37 and more (0.69 to 0.88 of the time): with OpenBLAS, compare one thread with a few.
Use a few threads instead when
the problem has PSD blocks of size 500 or more. On 4 fast cores the projection took 0.85 (NVPL) and 0.47 (OpenBLAS) of its time on one thread at size 500, and 0.58 and 0.41 at sizes 800 to 2000. The default, all 20 cores of that machine, was slower than one thread at size 500 with NVPL (1.52), and with OpenBLAS gained less than 4 threads did (0.89 against 0.47), so compare a few thread counts, and on a machine with fast and slow cores count only the fast ones;
the linear system is large and solved with MKL Pardiso, which runs on MKL’s threads (see the threads paragraph of MKL Pardiso), or with the dense direct solver, which forms and factorizes its matrix with BLAS and LAPACK (not measured).
A problem with several PSD blocks can instead use threads across the blocks, with the BLAS on one thread inside each, in a build with the parallel PSD projection (off by default): see Parallel projection of PSD blocks.
Which variable to set
Set it to 1, or to the number of threads to use.
Your BLAS |
Set |
Notes |
|---|---|---|
OpenBLAS with a thread pool of its own: built with pthreads, its
default (the default |
|
When that is unset it reads |
A BLAS built with OpenMP: an OpenMP build of OpenBLAS, NVPL’s OpenMP
( |
|
An OpenMP build of OpenBLAS ignores |
MKL |
|
Takes precedence over |
Accelerate (macOS) |
Nothing |
|
Set the variable before the program starts (in Python, at the latest before importing NumPy or SCS): the libraries read it when they start. It holds for every call to that library in the process, including SCS’s dense direct linear solver and your own code.
In a build of SCS with OpenMP (USE_OPENMP; the pre-built Python wheels
are built without it), OMP_NUM_THREADS is also SCS’s own thread count,
and setting it to 1 stops SCS’s own threads too, the parallel PSD
projection included. With OpenBLAS’s own thread pool or
with MKL, set the library’s variable instead. An OpenMP build of OpenBLAS, or
NVPL, has no variable of its own, so OMP_NUM_THREADS is one budget for
SCS and the BLAS. Inside a parallel PSD projection the BLAS runs on one thread
by itself. Where a build with USE_PARALLEL_PSD projects the blocks one
after another (one block that holds most of the work, say), it sets the OpenMP
thread count, and MKL’s thread-local count, to one for the blocks of size 384
or less, so such a BLAS and MKL run on one thread there too, and on all the
threads only for larger blocks (see the serial projection). In a build without
USE_PARALLEL_PSD the BLAS runs on all the threads for every block. We
measured that case in a build of SCS without OpenMP: on control7 (blocks of
size 70 and 35), NVPL with OMP_NUM_THREADS=4 made the projection take
1.82 times as long as with 1, and a whole iteration 1.37 times. For such a
problem compare OMP_NUM_THREADS=1 with your thread count.
To check, watch the CPU use of the process during a solve (top). With the
BLAS on one thread and SCS built without OpenMP it stays near 100%; several
hundred percent on a problem with small PSD blocks means that the BLAS threads
are running.
What we measured
Time of the PSD projection (with syevd) per iteration on the 58
SDPLIB problems whose largest PSD block is of size 37 or more, relative to the
BLAS on one thread (geometric mean, range in brackets; below 1 is faster). The
machine is an NVIDIA GB10 with 10 fast and 10 slow ARM cores, the libraries
NVPL and a pthreads build of OpenBLAS 0.3.31. The runs on one and on 4
threads were pinned to fast cores; 20 threads is the default of both libraries
there.
Size of the largest PSD block |
NVPL, 4 threads |
NVPL, 20 threads |
OpenBLAS, 4 threads |
OpenBLAS, 20 threads |
|---|---|---|---|---|
37 to 124 (25 problems) |
1.28 [1.04, 2.12] |
2.55 [1.26, 9.43] |
0.88 [0.81, 0.96] |
1.50 [1.07, 2.24] |
150 to 300 (17) |
1.18 [1.06, 1.33] |
2.16 [1.98, 2.46] |
0.69 [0.61, 0.79] |
1.52 [0.93, 2.07] |
500 (8) |
0.85 [0.84, 0.86] |
1.52 [1.48, 1.58] |
0.47 [0.45, 0.49] |
0.89 [0.66, 0.96] |
800 to 2000 (8) |
0.58 [0.50, 0.66] |
0.79 [0.47, 1.14] |
0.41 [0.36, 0.46] |
0.45 [0.29, 0.69] |
control7 (blocks of size 70 and 35) took 0.39 ms per projection with NVPL on one thread, 0.70 ms on 4 and 3.65 ms on 20, and a whole iteration 1.14 ms, 1.56 ms and 5.10 ms.
The pthreads OpenBLAS on 4 threads was faster than on one on every problem with blocks of size 37 or more. At its default it was slower up to size 300 (1.50 times at sizes 37 to 124, 1.52 at 150 to 300) and kept cores busy for nothing: 9 problems with blocks of size 37 to 124 used 15 to 20 cores (1526% to 1998% CPU) where one thread was 1.07 to 2.17 times as fast, and truss8, whose blocks are of size 19 at most, used 337%. Those cores are taken from anything else on the machine, such as other solves.
The 20-thread columns include the slow cores and depend on where the system placed the threads: the 27 problems whose blocks are all smaller than 37 were up to 2.4 times slower there, though 4 threads changed their time by at most 10%. So they show what the default can cost on such a machine, not the cost of the threads alone.
We did not measure x86 (MKL, or OpenBLAS on x86) or a machine with only one kind of core, where the sizes at which threads start to pay may differ. There, compare the time of a solve on one and on a few threads.
Parallel projection of PSD blocks
A problem with several positive semidefinite (PSD) blocks spends much of its
time projecting them, and SCS can project several blocks at the same time on
different threads. It does so only in a build that asks for it, with the
build option USE_PARALLEL_PSD. Without the option the blocks are
projected one after another. That is the default, and it is how the Python
wheels and the Julia packages are built.
The option is off by default because it is faster only with a BLAS that is set up for it, and slower with one that is not. This section explains when it helps, how to turn it on, and how to set up the BLAS.
When it helps
It helps with several PSD blocks of comparable size, many small ones or a few large ones. On 4 threads, 4 to 16 blocks of size 256 to 1024 were projected about 3 times faster, and a thousand blocks of size 10 to 32 about 3.5 times faster.
It does not help with one block, or one block much larger than the rest: a parallel projection is no faster than its largest block. SCS recognizes such a problem and projects its blocks one after another, as it does without the option.
It speeds up the projection, not the rest of a solve. If most of the time goes into the linear system, the solve as a whole gains little.
How to turn it on
Build SCS with OpenMP and with the option:
make USE_OPENMP=1 USE_PARALLEL_PSD=1
or, with CMake,
cmake -DUSE_OPENMP=ON -DUSE_PARALLEL_PSD=ON ..
With CMake the option takes effect only in the libraries that CMake compiles
with OpenMP: scsdir, scsindir, scsdense,
scsaccel and scsgpuindir. CMake compiles the MKL Pardiso and
cuDSS libraries (scsmkl and scscudss) without OpenMP, so they
project the blocks one after another whatever the option is set to. The
Makefile compiles every library with OpenMP, these two included.
With -DUSE_PARALLEL_PSD=ON, if CMake does not find OpenMP the
configuration stops with an error, because no library would then have the
parallel projection. OpenMP that is installed where CMake does not look can be
pointed to with -DOpenMP_ROOT=<folder>: Homebrew’s libomp on
macOS needs this, e.g. -DOpenMP_ROOT=$(brew --prefix libomp). (With
-DUSE_OPENMP=ON alone CMake prints a warning instead and builds the
libraries without OpenMP.) The configure output reports what is built in the
lines OpenMP parallelization is ON and Parallel PSD projection is ON.
For the Python package the option is use_parallel_psd, in an install
from source: see the Python install page.
Then set the OpenMP thread count to the number of cores to use:
export OMP_NUM_THREADS=4
On a machine with fast and slow cores, count only the fast ones. Every thread gets an equal share of the blocks, so a thread on a slow core holds the others up.
Setting up the BLAS
Threads can work on the projection at two levels. SCS can project several blocks at once, and the BLAS can use several threads inside the eigendecomposition of a single block. Only one of the two should be active at a time. With the option on, every thread of SCS calls the BLAS, so the BLAS has to run on one thread there. If it does not, each thread of SCS starts the threads of the BLAS as well. There are then more threads than cores, and the projection is slower than it should be: in one measurement the process had 16 threads where 4 were asked for, and ran at half the speed.
Whether the BLAS stays on one thread depends on where it gets its threads from:
Your BLAS |
Inside the threads of SCS |
What to do |
|---|---|---|
Built with OpenMP, on the same OpenMP runtime as SCS: an OpenMP build of OpenBLAS or BLIS, NVPL, or MKL on the threading layer that matches the compiler of SCS |
Runs on one thread by itself, because OpenMP does not nest parallel regions by default |
Nothing. This is the setup to use |
MKL on Intel’s OpenMP runtime (its default), with SCS compiled by GCC |
Would start its own threads. On Linux, with MKL as a shared library, SCS holds it to one thread during the projection |
Nothing on Linux. Elsewhere set |
A pthreads build of OpenBLAS, which has a thread pool of its own. The
default |
Keeps its threads. On Linux SCS sees that and projects the blocks one after another instead |
Use an OpenMP build of OpenBLAS if you can. Otherwise set
|
Built with OpenMP, on a different OpenMP runtime from SCS (the BLAS on LLVM’s runtime and SCS compiled by GCC, say) |
Cannot see the threads of SCS and starts its own in each of them |
Build SCS and the BLAS with the same compiler family. No variable puts
only the BLAS on one thread: |
Accelerate (macOS) |
Keeps a pool of threads of its own, which stays almost idle |
Nothing. At its default settings the parallel projection was 2.3 to 3.3
times faster than the serial one on 4 threads (measured before SCS moved
to |
Putting a BLAS on one thread with an environment variable holds for the whole process: that BLAS then runs on one thread wherever else it is used, in SCS (the dense linear solver) and in your own code. A BLAS on the OpenMP runtime of SCS has no such cost. The OpenMP thread count is then one budget, which SCS uses during a parallel projection and the BLAS uses everywhere else.
Checking that it works
With
verboseset, the header of a solve says how many threads project the PSD blocks, for examplepsd cones projected in parallel by 4 threads. Without that line the blocks are projected one after another; the next part lists the reasons.Count the threads of the process during a solve (
top -H, orps -o nlwp= -p <pid>on Linux). There should be about as many as the OpenMP thread count. Several times more means that the BLAS is running its own threads inside those of SCS.Compare the time of a solve with that of a build without the option. If it is not faster, leave the option off.
How SCS uses the threads
The number of threads is fixed when the solver is set up. It is the OpenMP
thread count at that point (as set by OMP_NUM_THREADS or
omp_set_num_threads), at most the number of blocks larger than
\(1 \times 1\). It is also bounded by the amount of work, because each
thread takes a few microseconds to start. SCS counts 2 microseconds for each
thread, and 5 on macOS (PSD_PAR_THREAD_COST in src/cones.c).
The number of threads grows with about the square root of the time that SCS
estimates for the projection on one thread. With many blocks of similar size,
a projection of less than about 13 microseconds (32 on macOS) stays on one
thread, one of 50 microseconds gets about 6 threads (4 on macOS), and one of a
millisecond gets up to about 30 (20 on macOS). A solve uses fewer threads if
the OpenMP thread count has been lowered since the setup.
SCS estimates the time of each block from its size, with a formula
(psd_block_cost in src/cones.c) fitted to the time
syevd takes for a real block with NVPL on one core of an Arm
Cortex-X925. The estimate decides how the blocks are shared out and, with
the time per thread, how many threads are used. BLAS libraries differ most on
small blocks: Accelerate on an Apple M4 and OpenBLAS take a quarter to two
thirds of NVPL’s time for blocks of size 3 to 10, and MKL on x86-64 (AMD
Zen 3) 1.1 times. SCS uses one formula for all of them. Following NVPL, the
slowest of the first three, was the fastest of the formulas we compared over
those three libraries, but not with each of them. On the block structures
whose split changed, against the previous formula, the projection took:
with NVPL, 0.84 times the time at 2 to 4 threads and 0.89 at 10 threads;
with OpenBLAS, 0.94 and 1.20 times (see the OpenBLAS lock below);
with Accelerate, 1.06 and 1.12 times;
with MKL (static, on the GNU OpenMP runtime, as the scs-python option
mkl_static_threading=gnu_threadbuilds it), measured afterwards: 0.75, 0.79 and 0.73 times at 2, 3 and 4 threads (10 threads not measured). Part of that gain: in this build, blocks projected one after another each run on MKL’s own threads, which took longer than one thread at every block size measured (\(3 \times 3\) to \(128 \times 128\)).
Whole solves of the SDPs among those structures reached the same results in
0.98 times the time overall (0.86 with NVPL, 1.06 with OpenBLAS, 1.07 with
Accelerate), and 1.08 times at 10 threads alone. With MKL they reached the
same verified results in 0.81, 0.59 and 0.62 times the time at 2, 3 and 4
threads. The cost is on the libraries that are faster on small blocks: a
projection of 9 to 62 microseconds made of 5 to 64 blocks of size 3 to 10 can
get threads, or more of them, where fewer are faster (up to 2.3 times on the
M4). If that matters, compare the time of a solve with a lower
OMP_NUM_THREADS. OpenBLAS on x86-64 was not measured.
Complex blocks keep the estimate fitted to heevr, which is close to
heevd’s time with NVPL up to size 100 and up to 1.5 times too low for
larger blocks: the estimate fitted to heevd was slower in the same
measurements.
Even with the option, the blocks are projected one after another, and the BLAS is free to use its own threads (for blocks larger than \(384 \times 384\), see below), when
the library was compiled without OpenMP (
scsmklandscscudssbuilt with CMake),the threads would gain little: the blocks are too little work, or one block holds most of it (the parallel projection is no faster than its largest block),
a block larger than \(512 \times 512\) holds more than half of the work (the parallel projection would then gain less than a factor of two, and a multithreaded BLAS may do better on that block). Whether it does depends on the BLAS. MKL’s threads beat the parallel projection on such a block larger than 384 (AMD Zen 3, 3 and 4 threads), NVPL’s from about 1000 (DGX Spark), and Accelerate’s never (Apple M4). So where this rule projects such a block of size 640 to 2000 one after another, it took 1.03 to 1.85 times the time of the parallel projection on Accelerate, and 1.02 to 1.56 times with a BLAS on one thread (a pthreads OpenBLAS with
OPENBLAS_NUM_THREADS=1). 512 lies between the libraries: over all four we measured (with OpenBLAS’s OpenMP build) it took 1.6% more time than the best size, 768, with the smaller blocks held to one thread, and 2.4% more than the best, 1024 and 1500, with them left to the BLAS’s threads,the BLAS is a pthreads build of OpenBLAS set to more than one thread, where SCS can see that (see below), or
the solver is set up inside an active OpenMP parallel region, where the threads of the caller are the parallelism.
When a build with the option projects the blocks one after another, it sets
the OpenMP thread count to one for each block of size \(2 \times 2\) to
\(384 \times 384\), and back to what it was after them
(PSD_SERIAL_HOLD_N in src/cones.c). Larger blocks run with the
thread count as it was. This reaches a BLAS on the OpenMP runtime of SCS that
takes its number of threads from the OpenMP thread count, such as NVPL and an
OpenMP build of OpenBLAS. For MKL, whose own thread count takes precedence
over the OpenMP one, it also sets MKL’s thread-local count to one for the same
blocks, as the parallel projection does, and does so also when the OpenMP
thread count is one (OMP_NUM_THREADS=1 with MKL_NUM_THREADS
set). That goes through a weak reference to MKL’s symbol, which needs Linux
(ELF) and MKL’s symbols visible to SCS. Such a BLAS, and MKL, then run these
blocks on one thread, as inside a parallel projection, because on them their
threads cost more than they gain:
MKL 2026.1 (statically linked, GNU OpenMP layer, AMD Zen 3: the CPU build of the SCS benchmark, which sets
MKL_NUM_THREADS): blocks of size 128 or less took the time on one thread, where MKL’s 4 threads took 1.8 to 7 times as long for size 2 to 10. Whole solves of 148 pairs of problem and tolerance among the benchmark’s SDPs whose blocks are projected one after another (144 pairs, and 4 projected in parallel as controls, which the hold does not change), at 4 threads (measured with the MKL part alone; with the OpenMP part too the projections had the same bits): 127 pairs solved against 126, in 0.95 of the wall clock (shifted geometric mean, shift 10 s; 0.85 at 10 ms). MKL’s threaded eigensolver rounds differently from one thread, so the iterates change (in 126 of the 148 pairs), and the pairs that changed outcome went both ways (5 solved only with the hold, 4 only without it).NVPL (DGX Spark): real blocks of size 32 to 300 took 0.78 to 0.95 of the time at 2 and 4 threads, and real blocks of size 32 to 384 0.48 to 0.87 of it at 10 threads. Whole solves of the 70 shorter pairs of problem and tolerance among the benchmark’s SDPs whose blocks are projected one after another (66 pairs, and 4 projected in parallel, where nothing is held) reached the same results, with the same iterates, in 0.94 of the wall clock at 4 threads and 0.82 at 10 (shifted geometric mean, shift 10 s; 0.93 and 0.78 at 10 ms).
An OpenMP build of OpenBLAS: 0.59 to 0.98 of the time for blocks of size 32 to 384 at 4 threads on an Apple M4, and 0.15 to 0.82 for real blocks of size 3 to 512 at 4 threads on an AMD Zen 3.
Where the OpenMP thread count does not reach the BLAS, it changes nothing, neither the results nor the time:
a BLAS with threads of its own: a pthreads build of OpenBLAS (the default on Debian and Ubuntu, the SciPy and NumPy wheels, Julia) and Accelerate;
a BLAS on another OpenMP runtime than that of SCS;
an OpenMP build of OpenBLAS from version 0.3.34 on, once the program has called
openblas_set_num_threads: it then keeps that count (from its source; not measured);MKL where SCS cannot see it through the weak reference: on macOS and Windows, in an MKL loaded privately by another library (as Julia’s libblastrampoline does), and in a static MKL linked without the MKL Pardiso linear solver, which is what links in the function SCS calls, as for the guard of the parallel projection below (from how the linker treats a weak reference; not measured). There MKL’s own thread count takes precedence over the OpenMP one. MKL’s threads are slow on small blocks (see the MKL row of the table in Number of BLAS threads). If your problem’s blocks are small and projected one after another,
MKL_NUM_THREADS=1puts such an MKL on one thread, but for the whole process, MKL Pardiso included;a sequential BLAS, and builds of SCS without OpenMP (the Python wheels).
We did not measure MKL without MKL_NUM_THREADS, MKL on Intel’s OpenMP
runtime, BLIS, or Windows. The cost is on the larger blocks below the size:
there the threads of the BLAS can pay, and the block runs on one thread. A
block of size 512 took 1.10 to 1.20 times as long on one thread as on 4 (NVPL,
OpenBLAS on the M4), and blocks of size 200 to 384 1.02 to 1.12 times as long
as on 2 threads (OpenBLAS on the M4). Where the hold works, sizes 384 and 512
came out the same over all the block sizes and thread counts we measured, and
384 risks less. With LLVM’s OpenMP runtime (libomp, as clang links it),
setting the thread count to one also shrinks the team of the calling thread,
which the next parallel region grows again: about 1 microsecond per
projection at 4 threads on an Apple M4, in a microbenchmark. GNU’s runtime
does not show this.
The number of threads is chosen as if the threads were awake when a projection
starts. With the GNU OpenMP runtime on Linux they wait actively for a short
time after a parallel region (GOMP_SPINCOUNT) and then sleep, and
waking them can cost more than a small projection gains. On one machine, PSD
blocks that took less than a millisecond in all made an iteration up to 27%
slower when the rest of the iteration took a millisecond or more. If the PSD
blocks are a small part of a large problem, a build without
USE_PARALLEL_PSD suits it better. OMP_WAIT_POLICY=active keeps
the threads awake between projections, at the price of cores that are busy
while they wait.
What SCS checks, and where it cannot
SCS guards against two of the cases in the table, on some platforms only. That is the reason the option is left to whoever builds SCS and knows its BLAS.
MKL on another OpenMP runtime: SCS sets the thread-local thread count of MKL to one during the projection. This goes through a weak reference to
MKL_Set_Num_Threads_Local, which needs an ELF platform such as Linux and the MKL symbols visible to SCS. It does not work on Windows or macOS, with a static MKL linked without the MKL Pardiso linear solver (which references the function and so links it in), or with an MKL loaded privately by another library. A static MKL on its GNU OpenMP layer in a build withUSE_OPENMPand GCC (the scs-python optionmkl_static_threading=gnu_thread, see Multithreaded static MKL (x86-64 Linux)) does not depend on the guard: SCS and MKL share one runtime, which runs MKL on one thread inside SCS’s parallel region.A pthreads build of OpenBLAS with more than one thread: on ELF platforms SCS checks for it at setup and then projects the blocks one after another. With
OPENBLAS_NUM_THREADS=1the projection is parallel, but the BLAS calls of the threads still wait for one lock inside an OpenBLAS that was not built with OpenMP. SCS counts that when it chooses the number of threads: a few small blocks stay serial, many blocks of \(3 \times 3\) to \(10 \times 10\) get two to four threads, and blocks of \(16 \times 16\) to \(32 \times 32\) four to six. It does not count the cores the threads run on. On a DGX Spark (two clusters of Arm Cortex-X925 cores), a team of the same size took about 1.47 times as long with 10 OpenMP threads on the fast cores of both clusters as with 4 on one cluster (geometric mean of 55 ratios, one per block structure and team size, over 44 structures; 1.31 times over 11 ratios and 10 structures with NVPL, which has no lock). The two thread counts were timed in separate sessions, not side by side. With 10 threads the projection took 1.20 times the time of the previous formula on the block structures whose split changed, against 0.94 times at 2 to 4 threads. An OpenMP build of OpenBLAS does not have this limit. Both checks need the functionsopenblas_get_parallelandopenblas_get_num_threadsvisible to SCS: they are off for a staticlibopenblas.a(the weak references can stay unresolved), for an OpenBLAS with suffixed symbol names, and for one loaded privately by another library (libblastrampoline in Julia).In all other cases (other platforms, other libraries, another OpenMP runtime) SCS does nothing and assumes that the BLAS runs on one thread.
Thread safety, memory and reproducibility
Several threads call BLAS and LAPACK at once, so the library must be safe to
call that way. A single-threaded OpenBLAS (built with USE_THREAD=0) is
safe only if it was built with USE_LOCKING=1 (see OpenBLAS’s
Makefile.rule). SCS does not check this; OpenBLAS 0.3.28 and later list
USE_LOCKING in openblas_get_config(). OpenBLAS also has a table
of memory buffers of a size fixed when it is built (by NUM_THREADS, and
at least 50), and a thread holds one during a BLAS call: with more threads than
buffers, OpenBLAS 0.3.18 and later print a warning and allocate more, and
earlier versions fail. The OpenMP thread count bounds the number of threads.
A parallel projection takes more memory: each thread has its own eigendecomposition workspace, sized for the blocks that thread projects, and none is larger than the workspace of the serial projection. The extra memory is therefore at most the PSD workspace of the serial projection times the number of threads less one, and less when only a few threads get the largest blocks. That workspace is about \(3n^2\) floats for the largest real block of size \(n\) (see above, and Complex blocks for a complex block).
Each block goes through the same LAPACK calls, with the same work-array sizes, as in the serial projection, so with single-threaded BLAS the result is the same bit for bit, whatever the number of threads (unless the rounding of the BLAS depends on the memory alignment of its arguments, as it can with MKL).