如何利用Intel ADX指令实现256位无符号整数的加乘运算加速？

一、ADX指令核心优势 #

ADX扩展引入ADCX和ADOX两条关键指令，它们能独立跟踪两个进位链，解决传统ADC指令因单一进位依赖导致的串行瓶颈，特别适合多字长整数的并行加法/乘法分解运算。

二、256位无符号整数加法实现 #

256位整数可拆分为4个64位无符号字（uint64_t），利用ADX的双进位链特性，将高半部分和低半部分的加法并行执行：

代码示例（GCC内嵌汇编） #

#include <stdint.h>

void adx_add_256(uint64_t *dst, const uint64_t *src1, const uint64_t *src2) {
    uint64_t c0, c1;
    // 低128位加法，用ADCX跟踪进位c0
    __asm__ __volatile__ (
        "adcq %[s2_0], %[s1_0]\n\t"
        "adcxl %[s2_1], %[s1_1]\n\t"
        "movq %%rax, %[c0]\n\t"
        : [s1_0] "+r" (src1[0]), [s1_1] "+r" (src1[1]), [c0] "=r" (c0)
        : [s2_0] "r" (src2[0]), [s2_1] "r" (src2[1])
        : "rax", "cc"
    );
    // 高128位加法，用ADOX跟踪进位c1，不干扰低半部分进位
    __asm__ __volatile__ (
        "adoxq %[s2_2], %[s1_2]\n\t"
        "adoxl %[s2_3], %[s1_3]\n\t"
        "movq %%rax, %[c1]\n\t"
        : [s1_2] "+r" (src1[2]), [s1_3] "+r" (src1[3]), [c1] "=r" (c1)
        : [s2_2] "r" (src2[2]), [s2_3] "r" (src2[3])
        : "rax", "cc"
    );
    // 合并最终溢出进位（按需处理）
    uint64_t final_carry = c0 | c1;
    // 写入结果
    dst[0] = src1[0];
    dst[1] = src1[1];
    dst[2] = src1[2];
    dst[3] = src1[3];
}

关键说明 #

• ADCX：仅更新CF（进位标志），不影响OF（溢出标志），用于一条独立进位链
• ADOX：仅更新OF，不影响CF，用于另一条独立进位链
• 拆分256位为两组128位并行加法，避免传统ADC的串行进位传播延迟

三、256位无符号整数乘法实现 #

256位乘法本质是4个64位字的交叉乘法，ADX可加速部分积的累加过程：

核心思路 #

1. 将256位整数A（a3,a2,a1,a0）和B（b3,b2,b1,b0）拆分为64位字
2. 计算所有16组64位×64位的部分积（每组结果为128位）
3. 利用ADX的双进位链并行累加部分积，减少进位传播的串行等待

代码示例（简化版） #

#include <stdint.h>

void adx_mul_256(uint64_t *dst, const uint64_t *src1, const uint64_t *src2) {
    uint64_t temp[8] = {0}; // 存储512位乘积结果
    uint64_t c0, c1;

    // 计算a0*b0，直接写入temp低两位
    __asm__ __volatile__ (
        "mulq %[b0]\n\t"
        "movq %%rax, %[t0]\n\t"
        "movq %%rdx, %[t1]\n\t"
        : [t0] "=m" (temp[0]), [t1] "=m" (temp[1])
        : [a0] "a" (src1[0]), [b0] "r" (src2[0])
        : "rdx"
    );

    // 累加a0*b1 + a1*b0，用ADX双进位链并行处理低/高部分
    __asm__ __volatile__ (
        "mulq %[b1]\n\t"
        "adcxl %%rax, %[t1]\n\t"
        "adoxl %%rdx, %[t2]\n\t"
        "movq %[a1], %%rax\n\t"
        "mulq %[b0]\n\t"
        "adcxl %%rax, %[t1]\n\t"
        "adoxl %%rdx, %[t2]\n\t"
        "movq %%rax, %[c0]\n\t"
        "movq %%rdx, %[c1]\n\t"
        : [t1] "+m" (temp[1]), [t2] "+m" (temp[2]), [c0] "=r" (c0), [c1] "=r" (c1)
        : [a0] "a" (src1[0]), [b1] "r" (src2[1]), [a1] "r" (src1[1]), [b0] "r" (src2[0])
        : "rdx", "cc"
    );

    // 剩余部分积累加逻辑类似，重复利用ADCX/ADOX并行处理进位链
    // ...（省略完整累加代码）

    // 写入低256位结果到dst
    for (int i = 0; i < 4; i++) {
        dst[i] = temp[i];
    }
}

关键说明 #

• 乘法的部分积累加是性能瓶颈，ADX允许同时处理两条进位链，将串行累加操作并行化
• 配合MUL指令生成128位部分积，用ADCX累加低64位进位，ADOX累加高64位进位，避免单一进位链的延迟

四、编译器内置函数替代方案 #

若不想编写内嵌汇编，GCC和Clang提供ADX相关内置函数：

• __builtin_adcx_u64：执行64位加法，更新CF进位
• __builtin_adox_u64：执行64位加法，更新OF进位
• __builtin_addcx_u32/__builtin_addox_u32：32位版本

示例片段：

uint64_t carry_cf = 0;
dst[0] = src1[0] + src2[0];
carry_cf = __builtin_adcx_u64(src1[1], src2[1], carry_cf);

uint64_t carry_of = 0;
dst[2] = __builtin_adox_u64(src1[2], src2[2], carry_of);
dst[3] = __builtin_adox_u64(src1[3], src2[3], carry_of);

五、性能优化注意事项 #

• 确保目标CPU支持ADX（Intel Haswell及以后，AMD Zen及以后），可通过cpuid指令检测
• 数据对齐到64位边界，减少内存访问延迟
• 循环展开多字长运算，避免分支预测开销
• 配合BMI2等其他x86扩展，进一步优化乘法部分积计算

内容的提问来源于stack exchange，提问作者phqb