8 ms·

Optimize sgemm on RISC-V platform

79 points by camel-cdr 3y ago

CaliforniaKarl 3y ago
I enjoyed reading this! Take a problem, in a controlled environment, start with the simple implementation, iterate, and compare results.
kragen 3y ago
this is a great tutorial on optimizing linear algebra algorithms; the animations really help a lot and are really well done this sgemm progress is pretty impressive. i assume 'version 0' is one of the lower lines on the first graph? he has a graph lower down that shows it getting under 300 megaflops, closer to 50 megaflops for most problem sizes. getting up to 2.2 gigaflops is seriously impressive; that's 55% of the maximum theoretical possible throughput, which is really challenging on things that aren't vector supercomputers (which don't have caches!) with respect to the rvv assembly, it's worth noting that the allwinner d1 being optimized for here has the pre-ratification version 0.7.1 of the risc-v v extension (rvv) which has some incompatibilities with the ratified 1.0.0. i don't know the instruction set well enough to know if those incompatibilities affect this code probably worth archiving this link: https://github.com/Zhao-Dongyu/sgemm_riscv https://github.com/Zhao-Dongyu/sgemm_riscv — ⁂ — vaguely relatedly, i was astounded yesterday to find that gcc 12.2.0 fails at some basic optimizations on risc-v. (all of the following is with -Os) this trivial subroutine int sumarray(int *a, int n) { int total = 0; for (int i = 0; i != n; i++) total += a[i]; return total; } compiles (with -Os) to a loop containing separate left shift, address-addition, counter-incrementation, and integer addition instructions, 8 instructions in all, plus a ret. omitting initialization: 1: sext.w a3,a5 ; it's my fault i declared i as int instead of size_t so really 7 bne a1,a3,2f ; return if i == n ret 2: slli a3,a5,2 ; convert i to byte offset add a3,a3,a4 ; compute &a[i] lw a3,0(a3) ; load a[i] addi a5,a5,1 ; increment i addw a0,a0,a3 ; update total j 1b ; lather, rinse, repeat (same in 13.2.0: https://godbolt.org/z/cd1qa6Yzn https://godbolt.org/z/cd1qa6Yzn) i can get it to compile to reasonable code (5 instructions in the loop plus a ret) by writing int sumarray_opt(int *a, int n) { int total = 0; for (int *end = a + n; a != end; a++) total += *a; return total; } like the desperate, cornered animal i am 1: bne a5,a1,2f ret 2: lw a4,0(a5) addi a5,a5,4 ; how motherfucking annoying is it that objdump calls this an add addw a0,a0,a4 j 1b isn't strength-reduction something compilers know how to do already? are modern cpus so goddamned superscalar that the difference doesn't matter? (i'm pretty sure less than 0.1% of the billion-plus shipped hardware risc-v cpus out in the field are superscalar.) needing three separate instructions in the first version for converting to a byte offset, adding the byte index to the array base register, and loading from the address is something that could be ameliorated by hardware, but would involve some tradeoffs; the zba bit-manipulation extension to the risc-v isa contains 8 instructions for that sort of thing, including a sh2add that would reduce it to 2. but reducing it to 0 inside the loop with strength reduction is better. risc-v has a lot of talk about the great importance of macro-op fusion, but that won't help here; it could fuse the shift and add maybe but the add isn't going to go away until somebody applies some loop induction like, optimizing code for an instruction set with literally thousands of different implementations with different performance characteristics is sort of impossible, but i dare you to find me a risc-v where the first loop runs faster than the second one. or even the same speed on arm(32) gcc compiles both subroutines to the same code, as any reasonable human being would expect, with the loop being something equivalent to: 1: cmp r3, r1 bxeq lr ldr r2, [r3], #4 add r0, r0, r2 b 1b (same in 13.2.0: https://godbolt.org/z/qTs5vMEjs https://godbolt.org/z/qTs5vMEjs) that is, the same version of gcc does do the strength-reduction optimization for arm(32) (but not aarch64, but maybe that's defensible since aarch64 is usually superscalar: https://godbolt.org/z/1dbYhEavM https://godbolt.org/z/1dbYhEavM). this is still 5 instructions because it can combine the load and increment into a single postincrement load, but the return-if-not-equal costs us two instructions instead of one. and the actual speed of that will depend a lot more on things like macro-op fusion and branch prediction. like, it would be easy for the bne to take a lot more than two cycles. for cortex-m4 gcc also generates the same code for both versions, but of course there's no bxeq on cortex-m4: 1: cmp r3, r1 bne.n 2f bx lr 2: ldr.w r2, [r3], #4 add r0, r2 b.n 1b (same in 13.2.0: https://godbolt.org/z/Wc3bv6sWa https://godbolt.org/z/Wc3bv6sWa) so in conclusion risc-v gcc still needs a lot of work to catch up with arm gcc, even to successfully apply broadly-applicable cross-platform optimizations that it successfully applies on arm, which surprised me a lot postscript: apparently with -O3 instead of -Os gcc does a lot better on risc-v
- dzaima 3y ago
  gcc does give the 4-instr loop on all of -O1, -O2, and -O3 for the basic loop. And, to its credit, the worse loop on -Os does result in the function being 2 bytes smaller (if I'm reading it right), which is what you ask for with -Os. And on -march=rv64gc_zba, the -Os version is 4 bytes smaller than the -O3 one.
  - kragen 3y ago
    iiinteresting! i can't see how to get machine code listings on godbolt, but on my own machine (with 12.2.0) the -Os sumarray is 30 bytes, sumarray_opt is 22. with -O3 sumarray shrinks to 28 bytes but its loop is indeed only 4 instructions long, and sumarray_opt is 26 bytes (with the same inner loop with slightly different register assignments). so at least that one is smaller. and it's probably true that the 22-byte sumarray_opt with its 5-instruction loop is slower on most machines than the 26-byte version—but the 26-byte version would have been both smaller and faster than what -Os emitted for sumarray originally with -Os (please forgive objdump's unreadable disassembly and incorrect mnemonics): 00000000000007e8 <sumarray>: 7e8: 872a mv a4,a0 7ea: 4781 li a5,0 7ec: 4501 li a0,0 7ee: 0007869b sext.w a3,a5 7f2: 00d59363 bne a1,a3,7f8 <sumarray+0x10> 7f6: 8082 ret 7f8: 00279693 sll a3,a5,0x2 7fc: 96ba add a3,a3,a4 7fe: 4294 lw a3,0(a3) 800: 0785 add a5,a5,1 802: 9d35 addw a0,a0,a3 804: b7ed j 7ee <sumarray+0x6> 0000000000000806 <sumarray_opt>: 806: 058a sll a1,a1,0x2 808: 87aa mv a5,a0 80a: 95aa add a1,a1,a0 80c: 4501 li a0,0 80e: 00b79363 bne a5,a1,814 <sumarray_opt+0xe> 812: 8082 ret 814: 4398 lw a4,0(a5) 816: 0791 add a5,a5,4 818: 9d39 addw a0,a0,a4 81a: bfd5 j 80e <sumarray_opt+0x8> with -O3: 00000000000007f0 <sumarray>: 7f0: cd81 beqz a1,808 <sumarray+0x18> 7f2: 058a sll a1,a1,0x2 7f4: 87aa mv a5,a0 7f6: 00b506b3 add a3,a0,a1 7fa: 4501 li a0,0 7fc: 4398 lw a4,0(a5) 7fe: 0791 add a5,a5,4 800: 9d39 addw a0,a0,a4 802: fef69de3 bne a3,a5,7fc <sumarray+0xc> 806: 8082 ret 808: 4501 li a0,0 80a: 8082 ret 000000000000080c <sumarray_opt>: 80c: 058a sll a1,a1,0x2 80e: 87aa mv a5,a0 810: 95aa add a1,a1,a0 812: 4501 li a0,0 814: 00b78863 beq a5,a1,824 <sumarray_opt+0x18> 818: 4398 lw a4,0(a5) 81a: 0791 add a5,a5,4 81c: 9d39 addw a0,a0,a4 81e: fef59de3 bne a1,a5,818 <sumarray_opt+0xc> 822: 8082 ret 824: 8082 ret still, aside from risc-v's unnecessarily pedagogical syntax, what's wrong with this? .globl sumarray sumarray: mv a2, a0 # compensate for abi design blunder: first argument (array base address) in return value register slli a1, a1, 2 # convert array size to byte count li a0, 0 # initialize return value to 0 add a1, a1, a2 # compute array end beq a1, a2, 1f # skip loop if empty 2: lw a3, (a2) # load array item from memory add a0, a0, a3 # add to total addi a2, a2, 4 # increment array pointer bne a1, a2, 2b # continue loop unless done 1: ret except for the snarky comments, isn't this the code you'd expect from the compiler (without zba)? i wouldn't describe it as thoroughly tested, but it does seem to work. as i count it, it's 24 bytes and so smaller than anything except the original sumarray_opt, and it contains the same 4-instruction loop as the -O3 versions. i guess it's the -O3 sumarray_opt without the useless extra ret instruction, which is presumably some kind of minor bug
taminka 3y ago
interesting write-up even outside of the risc-v context, bc most of the optimisations are the same for different platforms one interesting difference is that memory prefetching/preloading has such a huge difference, whereas on arm/x86 it barely makes any difference (in my experience) that it's not even worth doing also, doesn't allwinner d1-h have simd registers?
- adgjlsfhk1 3y ago
  The chips you're used to have had decades of optimization to their automatic memory prefetching. Apples M1 etc do even better (they can speculate prefetch through a pointer which can make lots of data-structures a ton faster. Also for really high performance on x86, prefetching can often be a ~30% boost.
  - taminka 3y ago
    yeah, that's probably it i'm using an m1 laptop, so my sgemm implementation relies on arm neon vector extension, and i saw literally no performance improvements when i added prefetching, which could either be a result of their speculative optimisations or an issue in my own implementation but i have noticed some ppl saying that adding prefetching on x86 has little performance improvement for sgemm, bc it's a scenario in which it's easier to predict the next memory address that's gonna be used
    - ribit 3y ago
      Probably preaching to the choir here, but if you want high-performance sgemm on M-series, you should consider using the system-provided BLAS. It will invoke the dedicated matmul hardware on Apple CPUs, which has access to significantly higher memory and compute bandwidth than Neon. SIMD-based matmul on M1 only makes sense if your matrices are small and you need the result immediately (e.g. geometric transformations). I hope that Apple will implement SVE/SME one day which will allow us to leverage this hardware directly...
      - taminka 3y ago
ThouYS 3y ago
cool stuff!
camel-cdr 3y ago
Btw, here are measurements from a C920: https://github.com/Zhao-Dongyu/sgemm_riscv/issues/1 https://github.com/Zhao-Dongyu/sgemm_riscv/issues/1
j_not_j 3y ago
There is a recent update to the blis alternative to BLAS that includes a number of RISC-V performance optimizations. https://github.com/flame/blis/pull/737 https://github.com/flame/blis/pull/737

79 points by camel-cdr 3y ago

I enjoyed reading this! Take a problem, in a controlled environment, start with the simple implementation, iterate, and compare results.

kragen 3y ago

this is a great tutorial on optimizing linear algebra algorithms; the animations really help a lot and are really well done this sgemm progress is pretty impressive. i assume 'version 0' is one of the lower lines on the first graph? he has a graph lower down that shows it getting under 300 megaflops, closer to 50 megaflops for most problem sizes. getting up to 2.2 gigaflops is seriously impressive; that's 55% of the maximum theoretical possible throughput, which is really challenging on things that aren't vector supercomputers (which don't have caches!) with respect to the rvv assembly, it's worth noting that the allwinner d1 being optimized for here has the pre-ratification version 0.7.1 of the risc-v v extension (rvv) which has some incompatibilities with the ratified 1.0.0. i don't know the instruction set well enough to know if those incompatibilities affect this code probably worth archiving this link: https://github.com/Zhao-Dongyu/sgemm_riscv https://github.com/Zhao-Dongyu/sgemm_riscv — ⁂ — vaguely relatedly, i was astounded yesterday to find that gcc 12.2.0 fails at some basic optimizations on risc-v. (all of the following is with -Os) this trivial subroutine int sumarray(int *a, int n) { int total = 0; for (int i = 0; i != n; i++) total += a[i]; return total; } compiles (with -Os) to a loop containing separate left shift, address-addition, counter-incrementation, and integer addition instructions, 8 instructions in all, plus a ret. omitting initialization: 1: sext.w a3,a5 ; it's my fault i declared i as int instead of size_t so really 7 bne a1,a3,2f ; return if i == n ret 2: slli a3,a5,2 ; convert i to byte offset add a3,a3,a4 ; compute &a[i] lw a3,0(a3) ; load a[i] addi a5,a5,1 ; increment i addw a0,a0,a3 ; update total j 1b ; lather, rinse, repeat (same in 13.2.0: https://godbolt.org/z/cd1qa6Yzn https://godbolt.org/z/cd1qa6Yzn) i can get it to compile to reasonable code (5 instructions in the loop plus a ret) by writing int sumarray_opt(int *a, int n) { int total = 0; for (int *end = a + n; a != end; a++) total += *a; return total; } like the desperate, cornered animal i am 1: bne a5,a1,2f ret 2: lw a4,0(a5) addi a5,a5,4 ; how motherfucking annoying is it that objdump calls this an add addw a0,a0,a4 j 1b isn't strength-reduction something compilers know how to do already? are modern cpus so goddamned superscalar that the difference doesn't matter? (i'm pretty sure less than 0.1% of the billion-plus shipped hardware risc-v cpus out in the field are superscalar.) needing three separate instructions in the first version for converting to a byte offset, adding the byte index to the array base register, and loading from the address is something that could be ameliorated by hardware, but would involve some tradeoffs; the zba bit-manipulation extension to the risc-v isa contains 8 instructions for that sort of thing, including a sh2add that would reduce it to 2. but reducing it to 0 inside the loop with strength reduction is better. risc-v has a lot of talk about the great importance of macro-op fusion, but that won't help here; it could fuse the shift and add maybe but the add isn't going to go away until somebody applies some loop induction like, optimizing code for an instruction set with literally thousands of different implementations with different performance characteristics is sort of impossible, but i dare you to find me a risc-v where the first loop runs faster than the second one. or even the same speed on arm(32) gcc compiles both subroutines to the same code, as any reasonable human being would expect, with the loop being something equivalent to: 1: cmp r3, r1 bxeq lr ldr r2, [r3], #4 add r0, r0, r2 b 1b (same in 13.2.0: https://godbolt.org/z/qTs5vMEjs https://godbolt.org/z/qTs5vMEjs) that is, the same version of gcc does do the strength-reduction optimization for arm(32) (but not aarch64, but maybe that's defensible since aarch64 is usually superscalar: https://godbolt.org/z/1dbYhEavM https://godbolt.org/z/1dbYhEavM). this is still 5 instructions because it can combine the load and increment into a single postincrement load, but the return-if-not-equal costs us two instructions instead of one. and the actual speed of that will depend a lot more on things like macro-op fusion and branch prediction. like, it would be easy for the bne to take a lot more than two cycles. for cortex-m4 gcc also generates the same code for both versions, but of course there's no bxeq on cortex-m4: 1: cmp r3, r1 bne.n 2f bx lr 2: ldr.w r2, [r3], #4 add r0, r2 b.n 1b (same in 13.2.0: https://godbolt.org/z/Wc3bv6sWa https://godbolt.org/z/Wc3bv6sWa) so in conclusion risc-v gcc still needs a lot of work to catch up with arm gcc, even to successfully apply broadly-applicable cross-platform optimizations that it successfully applies on arm, which surprised me a lot postscript: apparently with -O3 instead of -Os gcc does a lot better on risc-v

dzaima 3y ago
gcc does give the 4-instr loop on all of -O1, -O2, and -O3 for the basic loop. And, to its credit, the worse loop on -Os does result in the function being 2 bytes smaller (if I'm reading it right), which is what you ask for with -Os. And on -march=rv64gc_zba, the -Os version is 4 bytes smaller than the -O3 one.
- kragen 3y ago
  iiinteresting! i can't see how to get machine code listings on godbolt, but on my own machine (with 12.2.0) the -Os sumarray is 30 bytes, sumarray_opt is 22. with -O3 sumarray shrinks to 28 bytes but its loop is indeed only 4 instructions long, and sumarray_opt is 26 bytes (with the same inner loop with slightly different register assignments). so at least that one is smaller. and it's probably true that the 22-byte sumarray_opt with its 5-instruction loop is slower on most machines than the 26-byte version—but the 26-byte version would have been both smaller and faster than what -Os emitted for sumarray originally with -Os (please forgive objdump's unreadable disassembly and incorrect mnemonics): 00000000000007e8 <sumarray>: 7e8: 872a mv a4,a0 7ea: 4781 li a5,0 7ec: 4501 li a0,0 7ee: 0007869b sext.w a3,a5 7f2: 00d59363 bne a1,a3,7f8 <sumarray+0x10> 7f6: 8082 ret 7f8: 00279693 sll a3,a5,0x2 7fc: 96ba add a3,a3,a4 7fe: 4294 lw a3,0(a3) 800: 0785 add a5,a5,1 802: 9d35 addw a0,a0,a3 804: b7ed j 7ee <sumarray+0x6> 0000000000000806 <sumarray_opt>: 806: 058a sll a1,a1,0x2 808: 87aa mv a5,a0 80a: 95aa add a1,a1,a0 80c: 4501 li a0,0 80e: 00b79363 bne a5,a1,814 <sumarray_opt+0xe> 812: 8082 ret 814: 4398 lw a4,0(a5) 816: 0791 add a5,a5,4 818: 9d39 addw a0,a0,a4 81a: bfd5 j 80e <sumarray_opt+0x8> with -O3: 00000000000007f0 <sumarray>: 7f0: cd81 beqz a1,808 <sumarray+0x18> 7f2: 058a sll a1,a1,0x2 7f4: 87aa mv a5,a0 7f6: 00b506b3 add a3,a0,a1 7fa: 4501 li a0,0 7fc: 4398 lw a4,0(a5) 7fe: 0791 add a5,a5,4 800: 9d39 addw a0,a0,a4 802: fef69de3 bne a3,a5,7fc <sumarray+0xc> 806: 8082 ret 808: 4501 li a0,0 80a: 8082 ret 000000000000080c <sumarray_opt>: 80c: 058a sll a1,a1,0x2 80e: 87aa mv a5,a0 810: 95aa add a1,a1,a0 812: 4501 li a0,0 814: 00b78863 beq a5,a1,824 <sumarray_opt+0x18> 818: 4398 lw a4,0(a5) 81a: 0791 add a5,a5,4 81c: 9d39 addw a0,a0,a4 81e: fef59de3 bne a1,a5,818 <sumarray_opt+0xc> 822: 8082 ret 824: 8082 ret still, aside from risc-v's unnecessarily pedagogical syntax, what's wrong with this? .globl sumarray sumarray: mv a2, a0 # compensate for abi design blunder: first argument (array base address) in return value register slli a1, a1, 2 # convert array size to byte count li a0, 0 # initialize return value to 0 add a1, a1, a2 # compute array end beq a1, a2, 1f # skip loop if empty 2: lw a3, (a2) # load array item from memory add a0, a0, a3 # add to total addi a2, a2, 4 # increment array pointer bne a1, a2, 2b # continue loop unless done 1: ret except for the snarky comments, isn't this the code you'd expect from the compiler (without zba)? i wouldn't describe it as thoroughly tested, but it does seem to work. as i count it, it's 24 bytes and so smaller than anything except the original sumarray_opt, and it contains the same 4-instruction loop as the -O3 versions. i guess it's the -O3 sumarray_opt without the useless extra ret instruction, which is presumably some kind of minor bug

taminka 3y ago

interesting write-up even outside of the risc-v context, bc most of the optimisations are the same for different platforms one interesting difference is that memory prefetching/preloading has such a huge difference, whereas on arm/x86 it barely makes any difference (in my experience) that it's not even worth doing also, doesn't allwinner d1-h have simd registers?

adgjlsfhk1 3y ago
The chips you're used to have had decades of optimization to their automatic memory prefetching. Apples M1 etc do even better (they can speculate prefetch through a pointer which can make lots of data-structures a ton faster. Also for really high performance on x86, prefetching can often be a ~30% boost.
- taminka 3y ago
  yeah, that's probably it i'm using an m1 laptop, so my sgemm implementation relies on arm neon vector extension, and i saw literally no performance improvements when i added prefetching, which could either be a result of their speculative optimisations or an issue in my own implementation but i have noticed some ppl saying that adding prefetching on x86 has little performance improvement for sgemm, bc it's a scenario in which it's easier to predict the next memory address that's gonna be used
  - ribit 3y ago
    Probably preaching to the choir here, but if you want high-performance sgemm on M-series, you should consider using the system-provided BLAS. It will invoke the dedicated matmul hardware on Apple CPUs, which has access to significantly higher memory and compute bandwidth than Neon. SIMD-based matmul on M1 only makes sense if your matrices are small and you need the result immediately (e.g. geometric transformations). I hope that Apple will implement SVE/SME one day which will allow us to leverage this hardware directly...
    - taminka 3y ago

ThouYS 3y ago

cool stuff!

camel-cdr 3y ago

Btw, here are measurements from a C920: https://github.com/Zhao-Dongyu/sgemm_riscv/issues/1 https://github.com/Zhao-Dongyu/sgemm_riscv/issues/1

j_not_j 3y ago

There is a recent update to the blis alternative to BLAS that includes a number of RISC-V performance optimizations. https://github.com/flame/blis/pull/737 https://github.com/flame/blis/pull/737