EltwiseReduceMod fails on EltwiseReduceModAVX512 operation with a modulus that is between 51 and 52 bits.

[jcalafato1]

The library does not reduce properly for any modulus between 51 and 52 bits. See this test:

TEST(ReduceFailure, ReduceFailure) {
std::vector<uint64_t> tst = {
41834706795195925,
4670328046076965,
17760383643480343,
49435670237278413,
24379914680392825,
33362919182756282,
14501318335168678,
31183658415687847
};
auto mod = 4440955546175441;
auto chk = tst;
intel::hexl::EltwiseReduceMod(chk.data(), tst.data(), tst.size(),
mod,
mod, 1);
auto exp = tst;
for (auto & elem : exp) {
elem %= mod;
}
ASSERT_EQ(exp, chk);
}

This is just an example. I have tried several different moduli of the same bit width and several different inputs. The reduction function does not match the modulus operation.

[joserochh]

Hello @jcalafato1 I have reproduced this issue with a modulus size of 52 bits but not 51 bits. Do you have a 51 bits case that you can share? I think this is a limitation of the AVX512-IFMA (52 bits) algorithm on big inputs.

[jcalafato1]

Hey @joserochh thanks for getting back to me, is a fix available or is it just a limitation of the library? I have a workaround in my projects to prevent 52 bit moduli from being generated right now, but I'd rather not have the restriction.

I also misspoke, when i said between 51 and 52 bits i meant numbers between 2^51 and 2^52, which are 52 bit numbers.

[joserochh]

There will be a fix so you don't need to avoid 52 bit moduli. In the worst case, the library will have to use AVX512-DQ intrinsic functions instead of AVX512-IFMA for this scenario. When input values are not that big, say only up to 4 times modulus value (input_mod_factor = 4), then reduction works fine with 52 bit moduli on IFMA as the algorithm is way simpler.

[jcalafato1]

Sounds good, thanks! I'll watch for a new version.

[joserochh]

Fix is on dev branch.