2 ms·

Yeah, C908 and X60 have a 256 cycle LMUL=8 vrgather for any SEW. I've written what I expect sane implementations to do here: https://gitlab.com/riseproject/ris

Yeah, C908 and X60 have a 256 cycle LMUL=8 vrgather for any SEW. I've written what I expect sane implementations to do here: https://gitlab.com/riseproject/riscv-optimization-guide/-/issues/1#note_1977583125 https://gitlab.com/riseproject/riscv-optimization-guide/-/is... This didn't take into account higher SEW, but I could imagine an implementation that as a LMUL2 native implementation for e32/e64. The number of connections for a specific SEW and VLEN should be (VLEN/SEW)(SEW/8), however the regularity and distance probably also impacts final implementation cost.

dzaima 2y ago
There is the better, but much more complex, option of a variable-latency vrgather, where, for each DLEN-sized output segment, it counts the number of distinct DLEN-sized chunks of the table the current indices require, and spends, say, ceil(that_count/2) uops (each uop being able to take two DLEN-sized table chunks, the indices, and outputting DLEN data; could also have only one DLEN-sized table chunk input at the obvious cost; also at some point there needs to be the necessary blending, idk where that fits in; probably could just be a temporary directly in the shuffle silicon). This would result in k*VL/DLEN uops for simple index patters such as zip/unzip/reverse/broadcast with k=1 or k=2, and worst-case (e.g. transpose) is as bad as your option 2 with N=1 or N=2, and requires just DLEN^2 connections in the main shuffle, as much of the heavy lifting is done by the already-necessary silicon for getting DLEN-sized chunks of operands (maybe there might be complications with having those not being requested sequentially though; I'm not a hardware person).
- camel-cdr 2y ago
  I'm also not a hardware person, but I think there is an easier/hackier variant of your approach, that should be relatively simple in an in-order design, but probably harder to do in an ooo design, because either need to variably add or remove uops based on the input. Maybe this is what you had in mind, but I must admit that I didn't fully understand how you described the implementation: For LMUL>1 vrgather: Create one uop for every LMUL=1 register: * Look at first index (n=idx[0]/(VLEN/SEW)), to select vector register to read from * do the LMUL=1 vrgather from that register, and check if all are in range * if they weren't, emit LMUL=1 vrgather uops corresponding to the other LMUL=1 register sources This would give you LMUL cycles for all permutations that read all values for a LMUL=1 register destination from a single LMUL=1 source register, or the proportional equivalent when DLEN<VLEN. So this would cover the LUT/zip/unzip/reverse/broadcast cases. As I mentioned I don't think this is a good fit for ooo designs, but in-order ones, with larger vector lengths could/should probably implement this.
  - dzaima 2y ago
    That is exactly my design (or, rather, a design I remember reading in the #riscv IRC room), taking the "could also have only one DLEN-sized table chunk input at the obvious cost" path; i.e. to extend your specification to my double-DLEN-chunk method, you'd have it find two different indices that each select a separate register, and blend those shuffled together all in one uop. https://github.com/llvm/llvm-project/issues/79196 https://github.com/llvm/llvm-project/issues/79196 also mentions this in "we want the elements to come from as few DLENs of the source vector as possible"; and down the comments there is me having had too much fun writing code to fill in "I don't care" index elements such that they don't add any more required chunks, in a completely-DLEN-agnostic way. I don't think this is necessarily that bad for ooo; it's really "just" variable latency, which would already exist to an extent on cores which dynamically scale based on VL (though, granted, not all would be such, and the exact latency would be found much later down the pipeline even then).
    - camel-cdr 2y ago
      Ah, great, I just wasn't sure what you meant with ceil(count/2). It's not worth implementing when VLEN>=DLEN, beacause then you can replace all of the uses were you'd always get an atvantage with unrolled LMUL=1 instructions. So I don't think it will be common in ooo designs, since they usually have smaller vectors.
      - dzaima 2y ago
        It's only not worth it if software indeed consistently does the LMUL=1 unrolling. Which I suppose most will, and vrgather with LMUL>1 will be roughly dead-on-arrival, but who knows.

dzaima 2y ago

There is the better, but much more complex, option of a variable-latency vrgather, where, for each DLEN-sized output segment, it counts the number of distinct DLEN-sized chunks of the table the current indices require, and spends, say, ceil(that_count/2) uops (each uop being able to take two DLEN-sized table chunks, the indices, and outputting DLEN data; could also have only one DLEN-sized table chunk input at the obvious cost; also at some point there needs to be the necessary blending, idk where that fits in; probably could just be a temporary directly in the shuffle silicon). This would result in k*VL/DLEN uops for simple index patters such as zip/unzip/reverse/broadcast with k=1 or k=2, and worst-case (e.g. transpose) is as bad as your option 2 with N=1 or N=2, and requires just DLEN^2 connections in the main shuffle, as much of the heavy lifting is done by the already-necessary silicon for getting DLEN-sized chunks of operands (maybe there might be complications with having those not being requested sequentially though; I'm not a hardware person).

camel-cdr 2y ago
I'm also not a hardware person, but I think there is an easier/hackier variant of your approach, that should be relatively simple in an in-order design, but probably harder to do in an ooo design, because either need to variably add or remove uops based on the input. Maybe this is what you had in mind, but I must admit that I didn't fully understand how you described the implementation: For LMUL>1 vrgather: Create one uop for every LMUL=1 register: * Look at first index (n=idx[0]/(VLEN/SEW)), to select vector register to read from * do the LMUL=1 vrgather from that register, and check if all are in range * if they weren't, emit LMUL=1 vrgather uops corresponding to the other LMUL=1 register sources This would give you LMUL cycles for all permutations that read all values for a LMUL=1 register destination from a single LMUL=1 source register, or the proportional equivalent when DLEN<VLEN. So this would cover the LUT/zip/unzip/reverse/broadcast cases. As I mentioned I don't think this is a good fit for ooo designs, but in-order ones, with larger vector lengths could/should probably implement this.
- dzaima 2y ago
  That is exactly my design (or, rather, a design I remember reading in the #riscv IRC room), taking the "could also have only one DLEN-sized table chunk input at the obvious cost" path; i.e. to extend your specification to my double-DLEN-chunk method, you'd have it find two different indices that each select a separate register, and blend those shuffled together all in one uop. https://github.com/llvm/llvm-project/issues/79196 https://github.com/llvm/llvm-project/issues/79196 also mentions this in "we want the elements to come from as few DLENs of the source vector as possible"; and down the comments there is me having had too much fun writing code to fill in "I don't care" index elements such that they don't add any more required chunks, in a completely-DLEN-agnostic way. I don't think this is necessarily that bad for ooo; it's really "just" variable latency, which would already exist to an extent on cores which dynamically scale based on VL (though, granted, not all would be such, and the exact latency would be found much later down the pipeline even then).
  - camel-cdr 2y ago
    Ah, great, I just wasn't sure what you meant with ceil(count/2). It's not worth implementing when VLEN>=DLEN, beacause then you can replace all of the uses were you'd always get an atvantage with unrolled LMUL=1 instructions. So I don't think it will be common in ooo designs, since they usually have smaller vectors.
    - dzaima 2y ago
      It's only not worth it if software indeed consistently does the LMUL=1 unrolling. Which I suppose most will, and vrgather with LMUL>1 will be roughly dead-on-arrival, but who knows.