I have two sparse general matrices stored in CSR format I need to multiply. Is there any chance to gain performance using AVX2? In general the matrices are big (hundreds of millions of non-zeros and sizes by about 3million x 3million). The number of non-zeros per matrix line should be sufficient but I am not sure if the irregular data access would make AVX2 code inefficient.
I know that there are libraries like Intel MKL and other who can already do matrix-matrix multiplication using AVX2. But I am looking for code I can look at and learn. Papers or github links would be also fine.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
You generally don't gain much for sparse matrix-matrix and sparse matrix-vector products using things such as SSE/AVX/... if the matrices are large. That's because these instructions offer the ability to do some floating point operations in parallel -- but for large sparse matrices, you are limited by the time it takes to get data from memory onto the processors, not by the time it takes to actually do the computations. As a consequence, the way you actually implement the multiplication doesn't matter very much unless your data structures as so small that they fit into the cache.
answered Mar 27, 2020 at 15:18
-
1$\begingroup$ Although I haven't implemented this specific kernel using AVX2, I think this answer is too pessimistic. In addition to performing flops in parallel, AVX2 intrinsics can also utilize multiple memory channels at once (ie access more system bandwidth than equivalent x87 code). My optimism stems from AVX2 implementations of stencil codes (FDTD), which are basically like a very specific sparse matvec (O(1) flops per read, memory bound). They can definitely be accelerated with AVX2, purely due to bandwidth enhancement effects, not flop-parallelism. $\endgroup$ Mar 27, 2020 at 15:30
-
$\begingroup$ @rchilton1980 -- I doubt that. Maybe you get more bandwidth from the local cache, but the performance of matvec or matmat products is determined almost exclusively by the RAM-to-cache bandwidth, and that is determined by the bus width, latency, and speed and independent of the instructions being executed. $\endgroup$ Mar 27, 2020 at 21:02
-
$\begingroup$ The performance of matvec and matmat product is really determined by RAM bandwidth. Nevertheless I have seen benchmarks from codes using Intel MKL matvec product where the performance improvements are at about 30% when using AVX2 code compared to scalar code. Thus I would expect also an improvement for matmat product. $\endgroup$ Mar 28, 2020 at 9:47
-
$\begingroup$ I am totally willing to believe this for dense operations where, with clever blocking, there is a substantial amount of data that can be reused -- you get it into the cache once, and then you can use vector instructions to quickly work on them. But for sparse matvecs and matmats, there is essentially no re-use of data and I would be quite surprised if there is much to gain. $\endgroup$ Mar 28, 2020 at 17:19
-
$\begingroup$ @WolfgangBangerth There are libraries that do interesting things to reduce the memory bandwidth, e.g. the SparseX library. I'd expect some improvement if you could use the BCSR matrix format, but I think that's probably a combination of the fact that it both slashes the size of the indexing structures and can use SIMD ops within the block. $\endgroup$ Mar 28, 2020 at 17:58