给出低位字产品,计算两个单词的双字产品(签名)

Question

在Hacker的喜悦中,有一种算法来计算两个(带符号)单词的双字产品.

该函数muldws1使用四次乘法和五次加法来计算两个单词的双字.

在该代码的末尾有一行注释掉

/* w[1] = u*v;                  // Alternative. */

该替代方案使用五次乘法和四次加法,即它为乘法交换加法.

但我认为这种替代方法可以改进.我还没有说过硬件.让我们假设一个假设的CPU,它可以计算两个字但不是高位字的乘积的低位字(例如,对于32位字32x32到低32).在这种情况下,在我看来,这个算法可以改进.这是我假设32位字的想法(相同的概念适用于64位字).

void muldws1_improved(int w[], int32_t x, int32_t y) {
    uint16_t xl = x; int16_t xh = x >> 16;
    uint16_t yl = y; int16_t yh = y >> 16;

    uint32 lo = x*y;
    int32_t t = xl*yh + xh*yl;

    uint16_t tl = t; int16_t th = t >>16;
    uint16_t loh = lo >> 16;

    int32_t cy = loh<tl; //carry
    int32_t hi = xh*yh + th + cy;
    w[0] = hi; w[1] = lo;
}

这使用了四次乘法,三次加法和一次比较.这是我所希望的一个小改进.

这可以改善吗？有没有更好的方法来确定进位标志？我应该指出我也假设硬件没有进位标志(例如没有ADDC指令)但可以比较字(例如word1<word).

编辑:正如Sander De Dycker指出我的功能未通过单元测试.这是一个通过单元测试的版本,但效率较低.我认为它可以改进.

void muldws1_improved_v2(int w[], int32_t x, int32_t y) {
    uint16_t xl = x; int16_t xh = x >> 16;
    uint16_t yl = y; int16_t yh = y >> 16;

    uint32_t lo = x*y;
    int32_t  t2 = xl*yh;
    int32_t  t3 = xh*yl;
    int32_t  t4 = xh*yh;

    uint16_t t2l = t2; int16_t t2h = t2 >>16;
    uint16_t t3l = t3; int16_t t3h = t3 >>16;
    uint16_t loh = lo >> 16;

    uint16_t t = t2l + t3l;
    int32_t carry = (t<t2l) + (loh<t);
    int32_t hi = t4 + t2h + t3h + carry;
    w[0] = hi; w[1] = lo;
}

这使用了四次乘法,五次加法和两次比较,这比原始函数更糟糕.

Answer 1

我的问题中我的功能有两个问题muldws1_improved。其中之一是当我这样做时它错过了进位xl*yh + xh*yl。这就是单元测试失败的原因。但另一个问题是，有签名*未签名的产品需要比 C 代码中更多的机器逻辑。（请参阅下面我的编辑）。 我找到了一个更好的解决方案，即首先优化无符号乘积函数muldwu1，然后执行

muldwu1(w,x,y);
w[0] -= ((x<0) ? y : 0)  + ((y<0) ? x : 0);

纠正标志。

这是我尝试改进muldwu1使用较低的单词lo = x*y（是的，这个函数通过了 Hacker's pleasure 的单元测试）。

void muldwu1_improved(uint32_t w[], uint32_t x, uint32_t y) {
    uint16_t xl = x; uint16_t xh = x >> 16;
    uint16_t yl = y; uint16_t yh = y >> 16;

    uint32_t lo   = x*y;    //32x32 to 32
    uint32_t t1   = xl*yh;  //16x16 to 32
    uint32_t t2   = xh*yl;  //16x16 to 32
    uint32_t t3   = xh*yh;  //16x16 to 32

    uint32_t t    = t1 + t2;
    uint32_t tl   = 0xFFFF & t;
    uint32_t th   = t >> 16;
    uint32_t loh  = lo >> 16;

    uint32_t cy   = ((t<t1) << 16) + (loh<tl); //carry
             w[1] = lo;
             w[0] = t3 + th + cy;
}

这比 Hacker's pleasure 的原始函数少了一个添加，但它必须进行两次比较

 1 mul32x32 to 32
 3 mul16x16 to 32
 4 add32
 5 shift logical (or shuffles)
 1 and
 2 compare32
***********
16 operations

编辑：

我对 Hacker's Delight（第二版）中有关 mulhs 和 mulhu 算法的声明感到困扰。

该算法需要 16 个有符号或无符号版本的基本 RISC 指令，其中 4 个是乘法指令。

我仅用 16 条 SSE 指令实现了未签名算法，但我的签名版本需要更多指令。我明白了原因，现在我可以回答我自己的问题了。

我未能找到比《Hacker's Delight》更好的版本的原因是，他们假设的 RISC 处理器有一条指令，可以计算两个字乘积的低位字。换句话说，他们的算法已经针对这种情况进行了优化，因此不太可能有比他们已有的版本更好的版本。

他们列出替代方案的原因是因为他们假设乘法（和除法）可能比其他指令更昂贵，因此他们将替代方案留作优化的案例。

因此 C 代码不会隐藏重要的机器逻辑。它假设机器可以执行字*字到低位字的操作。

为什么这很重要？在他们的算法中，他们首先做

u0 = u >> 16;

然后

t = u0*v1 + k;

如果u = 0x80000000u0 = 0xffff8000. 但是，如果您的 CPU 只能采用半字乘积来获得全字，则上半字u0将被忽略，并且您会得到错误的带符号结果。

在这种情况下，您应该计算无符号的高位字，然后hi -= ((x<0) ? y : 0) + ((y<0) ? x : 0);按照我已经说过的那样正确使用。

我对此感兴趣的原因是，Intel 的 SIMD 指令（SSE2 到 AVX2）没有执行 64x64 到 64 的指令，它们只有 32x32 到 64。这就是为什么我的签名版本需要更多指令。

但AVX512有64x64到64的指令。因此，对于 AVX512，签名版本应采用与未签名版本相同数量的指令。但是，由于 64x64 到 64 指令可能比 32x32 到 64 指令慢得多，因此无论如何执行无符号版本然后进行更正可能更有意义。