AVX512 - Add two 512-bit integers using _addcarryx_u64 function

Question

My purpose is to add two __m512i variables (c = a + b) as efficiently as possible. To do so, I'd like to use the _addcarryx_u64 function which takes uint64_t as inputs.

unsigned char _addcarryx_u64 (unsigned char c_in, 
                              unsigned __int64 a, 
                              unsigned __int64 b, 
                              unsigned __int64 * out)

I manage to obtain a working function based on buffers:

__m512i _m512_add(const __m512i a, const __m512i b)
{
    const size_t n = sizeof(__m512i) / sizeof(uint64_t);
    uint64_t buf_a[n], buf_b[n], buf_c[n];

    _mm512_storeu_si512((__m512i *)buf_a, a);
    _mm512_storeu_si512((__m512i *)buf_b, b);

    unsigned char c_in = 0;

    for (unsigned i = n-1; i < n; --i)
        c_in = _addcarryx_u64(c_in, buf_a[i], buf_b[i], &(buf_c[i]));

    return _mm512_setr_epi64(buf_c[0], buf_c[1], buf_c[2], buf_c[3],
                             buf_c[4], buf_c[5], buf_c[6], buf_c[7]);
}

But it is not as efficient as I expected. Note that I compare timing and result with the GMP library and another function (based on intrinsics functions but not _addcarryx_u64) that I previously wrote.

My question is the following, is there a more efficient way to access the different uint64_t than using some buffers? I was thinking like a table (a[i]) or using extraction functions but didn't find anything satisfying my needs / didn't manage to do it.

Answer 1

Probably not what you're expecting, but it's possible to do a 512-bit add directly with AVX512 registers. The _addcarryx_u64() intrinsic is not necessary nor do you need to break up the register into scalars.

Taken from my blog: http://www.numberworld.org/y-cruncher/internals/addition.html#ks_add

The following is a little-endian 512-bit full-adder:

__m512i add512(uint32_t& carry, __m512i A, __m512i B){

    const __m512i MAX_WORD = _mm512_set1_epi64(0xffffffffffffffff);

    __m512i s = _mm512_add_epi64(A, B);
    __mmask16 c = _mm512_cmplt_epu64_mask(s, A);
    __mmask16 m = _mm512_cmpeq_epi64_mask(s, MAX_WORD);

    {

        uint32_t c0 = _mm512_mask2int(c);
        uint32_t m0 = _mm512_mask2int(m);
        carry += m0;
        carry = (carry + c0*2); //  lea
        m0 ^= carry;
        carry >>= 8;
        m = _mm512_int2mask(m0);

    }

    return _mm512_mask_sub_epi64(s, m, s, MAX_WORD);
}

The carry parameter indicates the carry-in. It will be replaced with the carry-out. It must be either 0 or 1.

---

To clarify, this is little-endian across all 512 bits. So carry propagation goes from lowest address to highest address. I'm not sure if this is what you really wanted since your example seems to do it in big-endian with 64-bit granularity.

If you really do want this in big-endian, you will need to shuffle all the inputs and outputs since there's no way to efficiently reverse the direction of the carry-propagation.

---

Background:

This is something I attacked back in January of 2017 while I was experimenting with parallel adder algorithms. And somewhat by chance I managed to derive the general approach to the above method.

I've since been told that this sequence was already known internally to Intel, but they never published it. And it seems quite likely that the kadd mask instructions were specifically designed for parallel-prefix algorithms like the adder given here.