Default matrix memory alignment mismatches the L1 cacheline size of most (all?) x64 CPU

[kkm000]

kaldi/src/matrix/kaldi-matrix.cc

Lines 55 to 56 in 813b731

	if ((p_work = static_cast<Real*>(
	KALDI_MEMALIGN(16, sizeof(Real)*l_work, &temp))) == NULL) {

The L1 cacheline size on all Xeons and AMD EPYCs I checked is 64. The actual alignment is invariably 16 and is sprinkled all over the code. This causes a performance hit. For the L1 constructive interference, the alignment should be 64 on x64 hardware.

Proposal:

• The C++17 "the toolchain knows it better" approach being out of reach, add a preprocessor variable KALDI_CONSTRUCTIVE_MEMALIGN, to signify the constructive cacheline alignment, and default it to 64 if not defined otherwise with the -D compiler switch during compilation.
• Replace compiler macros KALDI_MEMALIGN and KALDI_MEMALIGN_FREE with functions templated on the type being allocated, allowing the above code be rewritten calloc-style (number of elements) without explicit arithmetics and casting. This will make it easier to add an overload that would take an alternative value for the alignment, should such a need arise. This will also ease a later transition to C++17 std::aligned_alloc and/or the aligned signature of operator new (signatures: throwing (4) and non-throwing (8)). Example:

if ((p_work = KaldiAlignedAlloc<Real>(l_work)) == nullptr)
 . . .
KaldiAlignedFree(p_work);

---

On Linux, CPU cache descriptors are exposed through the sys filesystem. In particular,

$ cat /sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size
64

index0 = the cache closest to the CPU = L1.

[danpovey]

Cool!
If you have a little time for Kaldi stuff could you please check over PRs and check that we aren't forgetting anything?

[kkm000]

@danpovey, I was extremely busy for a couple weeks, but looks like I'm getting a breather. I'll do that on the weekend.

[kkm000]

@danpovey, I'm working on this but there is more to it than lies on the surface. For one, it's important to propagate the compiler hints that the memory is indeed aligned in some cases.

Do you perchance remember why do we have 3 different types for matrix indices?

kaldi/src/matrix/matrix-common.h

Lines 98 to 105 in 785ecf7

	typedef int32 MatrixIndexT;
	typedef int32 SignedMatrixIndexT;
	typedef uint32 UnsignedMatrixIndexT;
	// If you want to use size_t for the index type, do as follows instead:
	//typedef size_t MatrixIndexT;
	//typedef ssize_t SignedMatrixIndexT;
	//typedef size_t UnsignedMatrixIndexT;

[danpovey]

Those typedefs were intended to help future compatibility, in case we at some point decided to change the matrix index type (int32) to a different size type or possibly an unsigned type. But they are inconsistently used so best not to rely too much on them.

[nshmyrev]

Speaking of matrices in cache, this library uses "panel layout" of matrices for very fast sgemm:

https://github.com/giaf/blasfeo

it is 3 times faster than openblas on arm and 1.5 times faster than mkl for matrices of our size. Its not very straightforwar to repack matrices in kaldi though but it would be nice to integrate it one day.

[kkm000]

@danpovey, so maybe get rid of them? While I'm mangling the matrix library. Leave one signed MatrixIndexT?

@nshmyrev, thanks, interesting, I'll certainly have a look. I could not find the AVX512 kernels (here: https://github.com/giaf/blasfeo/tree/master/kernel), and if it does not use it, then what is the 1.5 speedup measured against?

On the same note, have you had a look at oneMKL? It's now 2 libraries in one, the "classic" MKL and the second one, with a C++ interface, which JITs optimal code for the CPU and the problem. If you have, what do you think?

[danpovey]

removing.them is.ok for me

…

On Sunday, January 10, 2021, kkm000 ***@***.***> wrote: @danpovey <https://github.com/danpovey>, so maybe get rid of them? While I'm mangling the matrix library. Leave one signed MatrixIndexT? @nshmyrev <https://github.com/nshmyrev>, thanks, interesting, I'll certainly have a look. I could not find the AVX512 kernels (here: https://github.com/giaf/blasfeo/tree/master/kernel), and if it does not use it, then what is the 1.5 speedup measured against? On the same note, have you had a look at oneMKL? It's now 2 libraries in one, the "classic" MKL and the second one, with a C++ interface, which JITs optimal code for the CPU and the problem. If you have, what do you think? — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#4404 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAZFLO6J226UIGMQ6VFZKO3SZDVCTANCNFSM4VMJT47Q> .

[kkm000]

I'm putting this on a backburner for a while. The things are a little more complex than just changing the macros. The problem is with subvectors/submatrices. If we tell the compiler the memory is aligned, it better be, or we'll get the UB. This means the stride of SubMatrix should be handled with not simply row tail slack, as in the Matrix, but also use pre-padding and offset (i.e., the row doesn't always begin at the start of a stride, when starting column is not an alignment multiple). The same is true for SubVector: their data_ should be aligned if we hint the compiler that it is, so there needs to be an offset from data_ to the 0th element of the SubVector.

Fortunately, cudaMalloc aligns at 256 byte boundary, which exceeds any CPU alignment requirements, so memcopy between CPU and GPU won't be a problem.

My hands are itchy to rework the whole kaboodle, perhaps using the F-bound polymorphism technique where sensible to minimize virtual calls, but that's a big project. It's not as readable, but the matrix lib needs all efficiency it can achieve, so I'm not against losing a bit of readability; I'll comment it well, as I usually do.

And the CuMatrix can be a simple typedef for Matrix when compiling w/o CUDA; ditto Cu{Vector,Sub*}.

@danpovey, @jtrmal, do you perchance remember why the CUDA allocator is implemented the way it is? It essentially grabs a huge chunk of device memory and implements its own heap management algorithm within it. Given that CUDA had likely much advanced since this was first implemented, is it still necessary? Will simple cudaMalloc do? Is it worth testing?

[danpovey]

Mm. Some toolkits store the original data_ pointer and an offset into it. In fact, in k2 we do that, with an extra layer of indirection on the 'data' pointer so we can do things like resizing and lazy allocaation.

But modifying the whole Kaldi library for that at this point would be, IMO, not worth the effort and may cause other problems; I think it would make more sense to get involved with k2 if you want to do interesting hardware stuff. I know I haven't fully explained to you why we can do cool stuff with it that we couldn't otherwise do, but trust me, it's coming fairly soon (month or two).

We use our own allocator because CUDA's one is extremely slow, especially when multiple devices are attached to the same machine as it syncs all of them I think, for unified memory reasons. Other toolkits do this as well, like PyTorch; all serious CUDA code uses a caching allocator I think.

Are you sure the compiler's hints about boundaries would get properly passed through the BLAS interface? I wouldn't think so as they tend to be "C" interfaces. I'd think just allocating on the correct boundary would give most of the benefit.

[kkm000]

When can we sync on K2 face-to-face? Please set the time when you are ready and available.

Are you sure the compiler's hints about boundaries would get properly passed through the BLAS interface? I wouldn't think so as they tend to be "C" interfaces. I'd think just allocating on the correct boundary would give most of the benefit.

They would, but it's up to the BLAS library to use them. If the library makes no assumption about the alignment, it's always fine, whether the memory is aligned or not. The trouble starts when we have unaligned memory but tell the compiler it is, and it uses the hint. Not all algorithms translate to BLAS calls 1:1; there are loops, and this is where alignment becomes important.

I once implemented matrix multiplication (about 1000×1000 floats, give or take) as simple two loops, and got the same perf as MKL after following hints from the icc static analyser (aligned some memory and rearranged loop order), ca. 2014 I think, on a Haswell i7 desktop CPU (which actually has a weird half-AVX2 unit, and fakes it by doing 2 FMA sequentially; the first full-width AVX2 unit was only added in Haswell Xeon E7-v3, next year, IIRC).

[kkm000]

We use our own allocator because CUDA's one is extremely slow, especially when multiple devices are attached to the same machine as it syncs all of them I think, for unified memory reasons. Other toolkits do this as well, like PyTorch; all serious CUDA code uses a caching allocator I think.

Wondering why CUDA still does not include one then. Not impossible, of course, I've seen worse, but just... weirdly illogical for such a mature toolchain. Especially with Intel's stepping on their toes with DPC++ via SYCL backend (they primarily target their own GPUs, of course, but CUDA is supported--SYCL is not an Intel product, and NVIDIA is a member of the consortium). I'll check what's new in 11.2 when I have time.