c.mulh instruction

[gsmecher]

A c.mulh instruction to mirror c.mul in zcb would allow the following to be expressed in purely compressed instructions:

• 32-bit DSP (dot product/convolution/correlation)
• wider multiplies (64 bits and upwards)

There is room in the instruction encodings directly below c.mul (see Table 16-6, RISC-V Unprivileged ISA) - there is a natural spot for c.mulh and it seems a shame not to take advantage of the symmetry here.

Related: #9. The MAC proposal was (reasonably) excluded as out-of-scope here. A c.mulh bookend to c.mul would partly address the same need but fits better within the mandate of this WG.

[gsmecher]

Here's a little additional colour: I develop the minimax RISC-V implementation (https://github.com/gsmecher/minimax), which directly executes only 16-bit instructions and emulates 32-bit instructions in microcode. Because of this architecture, there is an ~100x performance difference between compressed and uncompressed instructions. The ZC* extensions are critical because more code in the 16-bit space is a massive performance improvement for minimax.

More specifically: Minimax is currently useless for DSP because all multiplies must be emulated. A c.mul instruction brings high-performance 16-bit convolutions within reach. A c.mulh instruction would make performant 32-bit DSP possible in this core. This would open the core up to an entirely new type of application.

I understand that a ~100x performance differential in a weird implementation is a Me problem, not a You problem. I also understand it's late in the cycle for a new instruction. However: there is a perfect encoding candidate right below c.mul (see Table 16.6, RISC-V Unprivileged ISA). Since c.mul implies M, which mandates a 32x32 -> 64-bit multiplier anyways, the implementation cost is basically the multiplexer to select between low and high words of the 64-bit product. From this perspective: is the lack of c.mulh a deliberate decision, or just something nobody has requested yet?

Again, thanks for all your efforts - I am excited about this WG's work, with or without c.mulh.

[jnk0le]

The c.mulh would be usually paired with c.mul and in this case, there needs to be an explicit move due to destructive operand. Therefore c.mulh doesn't offer enough size reduction

[gsmecher]

@jnk0le - that is an excellent point. A synthetic c.mulh using Zcb instructions would be pretty short, and it looks like Zcb has all the right primitives already. Thank you - closing.

[gsmecher]

On reflection, @jnk0le, I closed this issue too soon. Your comment is predicated on paired c.mul/c.mulh, which is true for wider multiplies. It's not true for DSP algorithms (FFTs, FIRs, correlations, etc.). Because these are not general-purpose algorithms, they don't show up on general-purpose benchmarks.

I am, unfortunately, flatly wrong about the "obvious" encoding space for c.mulh. The slot below c.mulh in Table 16-6 is already consumed in Zc* and it does not look like there's an easy place to put c.mulh even if it were justified.

[tovine]

If you have any suggested benchmarks (preferably open source but IIRC ELF files is all you need) then I guess it should be possible/easy to add support for analyzing the impact of a c.mulh encoding to the hca script in this repository.

[gsmecher]

Thanks, @tovine: for DSP applications, ARM's CMSIS DSP library 0 seems like a good reference point. CMSIS is Apache licensed and should be directly portable to RISC-V (see e.g. 1).

The following is an example convolution kernel adapted from 2. The loop is unrolled by a factor of 4, but here's the compact version first:

#include <stdint.h>

typedef int32_t q31_t;
typedef int64_t q63_t;

int conv(int k, const q31_t * px, const q31_t * py) {
    q63_t sum;
    while(k > 0u) {
      sum = (q31_t) ((((q63_t) sum << 32) +
                      ((q63_t) * px++ * (*py--))) >> 32);

      k--;
    }
    return sum;
}

I get:

$ clang --target=riscv32 -march=rv32gc -Oz -c -o conv.o conv.c
$ riscv64-unknown-elf-objdump -d conv.o
00000000 <conv>:
   0:   c911                    beqz    a0,14 <conv+0x14>
   2:   4198                    lw      a4,0(a1)
   4:   421c                    lw      a5,0(a2)
   6:   0591                    addi    a1,a1,4
   8:   1671                    addi    a2,a2,-4
   a:   02e79733                mulh    a4,a5,a4
   e:   96ba                    add     a3,a3,a4
  10:   157d                    addi    a0,a0,-1
  12:   f965                    bnez    a0,2 <conv+0x2>
  14:   8536                    mv      a0,a3
  16:   8082                    ret

There are 8 instructions in the non-unrolled loop, of which mulh is the only uncompressed one. Pretty tough to make a case that c.mulh would improve code density here. I am not sure if there's a strong microarchitectural argument, and/or whether that's relevant to this WG anyway.

If I use the 4-way unrolled version of the kernel instead, I get something the following:

$ clang --target=riscv32 -march=rv32gc -Oz -c -o conv4.o conv4.c
$ riscv64-unknown-elf-objdump -d conv4.o
00000000 <conv>:
   0:   587d                    li      a6,-1
   2:   c529                    beqz    a0,4c <conv+0x4c>
   4:   419c                    lw      a5,0(a1)
   6:   4218                    lw      a4,0(a2)
   8:   02f71733                mulh    a4,a4,a5
   c:   0045a283                lw      t0,4(a1)
  10:   ffc62303                lw      t1,-4(a2)
  14:   98ba                    add     a7,a7,a4
  16:   0085a383                lw      t2,8(a1)
  1a:   ff862683                lw      a3,-8(a2)
  1e:   02531733                mulh    a4,t1,t0
  22:   0108f7b3                and     a5,a7,a6
  26:   973e                    add     a4,a4,a5
  28:   027698b3                mulh    a7,a3,t2
  2c:   45dc                    lw      a5,12(a1)
  2e:   ff462683                lw      a3,-12(a2)
  32:   01077733                and     a4,a4,a6
  36:   9746                    add     a4,a4,a7
  38:   01077733                and     a4,a4,a6
  3c:   02f696b3                mulh    a3,a3,a5
  40:   00d708b3                add     a7,a4,a3
  44:   157d                    addi    a0,a0,-1
  46:   05c1                    addi    a1,a1,16
  48:   1641                    addi    a2,a2,-16
  4a:   fd4d                    bnez    a0,4 <conv+0x4>
  4c:   8546                    mv      a0,a7
  4e:   8082                    ret

Here, there are 24 instructions in the loop (13 uncompressed, of which 4 are mulh.) There are RVC equivalents to everything except c.mulh - though it looks like it would take a different compiler or handwritten kernel to make a 16-bit c.mulh stand out.

An FFT implementation would be nearly as general-purpose as a convolution, but CMSIS doesn't have one. I'll poke around and see if I can put together something similar.

Ultimately, though, this is somewhat application-specific and I don't know if a benchmark belongs in your tree or not.

[gsmecher]

Here's an FFT, taken brutally and somewhat arbitrarily from cmsis-dsp.

#include <stdint.h>

typedef int32_t q31_t;
typedef int64_t q63_t;

#define multAcc_32x32_keep32_R(a, x, y) a = (q31_t) (((((q63_t) a) << 32) + ((q63_t) x * y) + 0x80000000LL ) >> 32)
#define multSub_32x32_keep32_R(a, x, y) a = (q31_t) (((((q63_t) a) << 32) - ((q63_t) x * y) + 0x80000000LL ) >> 32)
#define mult_32x32_keep32_R(a, x, y) a = (q31_t) (((q63_t) x * y + 0x80000000LL ) >> 32)
#define multAcc_32x32_keep32(a, x, y) a += (q31_t) (((q63_t) x * y) >> 32)
#define multSub_32x32_keep32(a, x, y) a -= (q31_t) (((q63_t) x * y) >> 32)
#define mult_32x32_keep32(a, x, y) a = (q31_t) (((q63_t) x * y ) >> 32)

void arm_split_rifft_q31(
        q31_t * pSrc,
        uint32_t fftLen,
  const q31_t * pATable,
  const q31_t * pBTable,
        q31_t * pDst,
        uint32_t modifier) {       
        q31_t outR, outI;
  const q31_t *pCoefA, *pCoefB;
        q31_t CoefA1, CoefA2, CoefB1;
        q31_t *pIn1 = &pSrc[0], *pIn2 = &pSrc[2 * fftLen + 1];

  pCoefA = &pATable[0];
  pCoefB = &pBTable[0];

  while (fftLen > 0U) {
     CoefA1 = *pCoefA++;
     CoefA2 = *pCoefA;

     mult_32x32_keep32_R (outR, *pIn1, CoefA1);
     mult_32x32_keep32_R (outI, *pIn1++, -CoefA2);
     multAcc_32x32_keep32_R (outR, *pIn1, CoefA2);
     multAcc_32x32_keep32_R (outI, *pIn1++, CoefA1);
     multAcc_32x32_keep32_R (outR, *pIn2, CoefA2);
     CoefB1 = *pCoefB;

     multSub_32x32_keep32_R (outI, *pIn2--, CoefB1);
     multAcc_32x32_keep32_R (outR, *pIn2, CoefB1);
     multAcc_32x32_keep32_R (outI, *pIn2--, CoefA2);

     *pDst++ = outR;
     *pDst++ = outI;

     pCoefB = pCoefB + (modifier * 2);
     pCoefA = pCoefA + (modifier * 2 - 1);

     fftLen--;
  }
}

I get the following:

$ clang --target=riscv32 -march=rv32gc -Oz -c -o cmsis_fft.o cmsis_fft.c
$ riscv64-unknown-elf-objdump -d cmsis_fft.o
00000000 <arm_split_rifft_q31>:
   0:   1141                    addi    sp,sp,-16
   2:   c622                    sw  s0,12(sp)
   4:   c426                    sw  s1,8(sp)
   6:   c24a                    sw  s2,4(sp)
   8:   c04e                    sw  s3,0(sp)
   a:   4801                    li  a6,0
   c:   58fd                    li  a7,-1
   e:   800002b7            lui t0,0x80000
  12:   00359313            slli    t1,a1,0x3
  16:   932a                    add t1,t1,a0
  18:   0311                    addi    t1,t1,4
  1a:   00379393            slli    t2,a5,0x3
  1e:   c9e5                    beqz    a1,10e <arm_split_rifft_q31+0x10e>
  20:   01060eb3            add t4,a2,a6
  24:   000eae03            lw  t3,0(t4)
  28:   411c                    lw  a5,0(a0)
  2a:   01068f33            add t5,a3,a6
  2e:   004eae83            lw  t4,4(t4)
  32:   03c79fb3            mulh    t6,a5,t3
  36:   03c78433            mul s0,a5,t3
  3a:   005404b3            add s1,s0,t0
  3e:   0084b433            sltu    s0,s1,s0
  42:   9fa2                    add t6,t6,s0
  44:   41d00433            neg s0,t4
  48:   02879933            mulh    s2,a5,s0
  4c:   028787b3            mul a5,a5,s0
  50:   00578433            add s0,a5,t0
  54:   4144                    lw  s1,4(a0)
  56:   00f437b3            sltu    a5,s0,a5
  5a:   993e                    add s2,s2,a5
  5c:   011fffb3            and t6,t6,a7
  60:   03d499b3            mulh    s3,s1,t4
  64:   03d48433            mul s0,s1,t4
  68:   005407b3            add a5,s0,t0
  6c:   0087b7b3            sltu    a5,a5,s0
  70:   97ce                    add a5,a5,s3
  72:   9fbe                    add t6,t6,a5
  74:   01197933            and s2,s2,a7
  78:   03c497b3            mulh    a5,s1,t3
  7c:   03c484b3            mul s1,s1,t3
  80:   00548433            add s0,s1,t0
  84:   009434b3            sltu    s1,s0,s1
  88:   00032403            lw  s0,0(t1)
  8c:   97a6                    add a5,a5,s1
  8e:   01278e33            add t3,a5,s2
  92:   011fffb3            and t6,t6,a7
  96:   03d41933            mulh    s2,s0,t4
  9a:   03d404b3            mul s1,s0,t4
  9e:   005487b3            add a5,s1,t0
  a2:   0097b7b3            sltu    a5,a5,s1
  a6:   000f2483            lw  s1,0(t5)
  aa:   97ca                    add a5,a5,s2
  ac:   01f78f33            add t5,a5,t6
  b0:   011e7e33            and t3,t3,a7
  b4:   02849fb3            mulh    t6,s1,s0
  b8:   02848433            mul s0,s1,s0
  bc:   0082b433            sltu    s0,t0,s0
  c0:   ffc32783            lw  a5,-4(t1)
  c4:   947e                    add s0,s0,t6
  c6:   408e0e33            sub t3,t3,s0
  ca:   011f7f33            and t5,t5,a7
  ce:   02979fb3            mulh    t6,a5,s1
  d2:   029784b3            mul s1,a5,s1
  d6:   00548433            add s0,s1,t0
  da:   00943433            sltu    s0,s0,s1
  de:   008f84b3            add s1,t6,s0
  e2:   9f26                    add t5,t5,s1
  e4:   011e7e33            and t3,t3,a7
  e8:   03d794b3            mulh    s1,a5,t4
  ec:   03d787b3            mul a5,a5,t4
  f0:   00578433            add s0,a5,t0
  f4:   00f437b3            sltu    a5,s0,a5
  f8:   97a6                    add a5,a5,s1
  fa:   97f2                    add a5,a5,t3
  fc:   01e72023            sw  t5,0(a4)
 100:   c35c                    sw  a5,4(a4)
 102:   15fd                    addi    a1,a1,-1
 104:   981e                    add a6,a6,t2
 106:   0521                    addi    a0,a0,8
 108:   1361                    addi    t1,t1,-8
 10a:   0721                    addi    a4,a4,8
 10c:   f991                    bnez    a1,20 <arm_split_rifft_q31+0x20>
 10e:   4432                    lw  s0,12(sp)
 110:   44a2                    lw  s1,8(sp)
 112:   4912                    lw  s2,4(sp)
 114:   4982                    lw  s3,0(sp)
 116:   0141                    addi    sp,sp,16
 118:   8082                    ret

This implementation looks like a dead end for c.mulh: most of the loop consists of 32-bit instructions (mul/mulh pairs not least among them, per @jnk0le's point above).

[gsmecher]

Just to be 100% clear: I think this idea is DOA for non-technical reasons (schedule, scope) and technical reasons outside the scope of all my analysis above (lack of available encoding space for c.mulh). It is probably not worth discussing the motivational benchmarks alone if it's moot.

[abukharmeh]

In the initial analysis phase, we generated frequency count of all instructions used in all benchmarks we have used, and before trying to fit to any compressed encoding, the saving from c.mulh were way too low to consider. Like you said this would be more applicable in DSP type application , but would need to prove some how that the code size saving per encoding bit spent is worth while, and I think that would be fairly hard.

Zc* extension is frozen at its current state, so its very unlikely that any new instructions would be added. But if you would like to make a better case for such instruction, I would encourage you to find opensource benchmarks that you think would benefit from it, and PR their compilation instructions for RISC-V and link to their source here thus we can evaluate using them when we work on the next iteration of the extension !

[gsmecher]

Thanks - this context is helpful, and I understand and agree with what you say. I will keep my eyes open for a justifiable benchmark that supports c.mulh.