Polynomial Code for ISA-L erasure code - optional faster encode - decode unchanged

[jeffareid]

The intended ISA-L use case is as an erasure only code. Polynomial code could do a somewhat faster single thread full encode using LFSR, but would require separate software for LFSR based encoding. Multi-threading would be a simpler way to increase throughput, I don't have any plans to create a repository for LFSR based encoding unless there is some interest in this.

For erasure codes like ISA-L, error checking | correction would be normally be handled externally, such as the ZFS file system. If error checking | correction was to be added to erasure code, a polynomial code based matrix can be used for encoding.

[jeffareid]

Update - the 24MB L3 cache is not common, but instead 3 MB per core. This is what caused the 512·1024 testing to hit the 51.2 GB/sec main memory bandwidth.

Using the self-reciprocal polynomials represented by the matrices generated by gf_gen_rcp_matrix() in ec_rcp.c, I did a proof of concept and got the following results for a LFSR based encode. There are no inversion issues with the polynomial based matrices.

I ran the code on a Dell 5560 laptop - Intel Core i7-11850H - AVX512+GFNI, which isn't consistent, so I used the numbers from best runs. I choose m=20 since that is what BackBlaze uses. I tested number of parities p from 1 to 6.

Initially I tested 512·1024 columns, which fits in the common 24 MB L3 cache, but was running into a 51.2 GB/sec main memory bandwidth issue. Turns out that L3 cache is not common, but instead 3 MB per core, which is why the 512·1024 byte testing was hampered by the 51.2 GB/sec main memory bandwidth. I switched to 48·1024 bytes per row, which fits in each core's 1.25 MB cache. ISA and LFSR both keep pointers to destination rows in registers. For source rows, ISA loads an 8 byte pointer to load 64 bytes at a time, while LFSR loads 128 bytes at a time using a pair of ZMM registers, For p=1, LFSR operates on 256 bytes at a time and just uses XOR. For p=2 to 6, only p/2 unique multipliers are needed, so they are only loaded one time into ZMM registers. p=6, 3 multipliers. p=5|4, 2 multipliers, p=3|2 1 multiplier, p=1 XOR. These are the results for single thread 48·1024 columns per row:

               lfsr          isa        increase
k=14 p=6 m=20   93.6 GB/sec   56.1 GB/sec  66.8% 
k=15 p=5 m=20  101.3 GB/sec   62.0 GB/sec  63.4%
k=16 p=4 m=20  109.4 GB/sec   68.0 GB/sec  60.9%
k=17 p=3 m=20  140.4 GB/sec   81.6 GB/sec  72.0%
k=18 p=2 m=20  163.7 GB/sec   82.7 GB/sec  97.9%
k=19 p=1 m=20  182.0 GB/sec  112.8 GB/sec  61.3%

[jeffareid]

Update - includes links to old and proof of concept code. The proof of concept LFSR code is based on 1987 code used for QIC tape drives. That LFSR code was updated to use PSHUFB in 2006, on an Intel Core 2 X6800, Windows XP X64, Visual Studio 2005, using 5 byte strings for PSHUFB, since VS2005 didn't have it yet. The 2006 test code was verified using a debugger to compare against the 1987 version (there is no output). Similar LFSR code was created by programmers at other tape companies. I bought a laptop with AVX512+GFNI Aug 2025 and ported the LFSR code to use vgf2p8affineqb and vpternlogq. I modded that LFSR code to make it callable from the ISA-L benchmark code (4 parameters instead of 6, m is hard coded to 20: {k,p} = {19,1} {18,2} {17,3} {16,4} {15,5} {14,6}).

[sam-lexx]

@jeffareid - Since you mentioned Windows, I assume you are using Visual Studio 2022 or 2026. Can you make a zip of what is needed to build your affine LFSR code? I also did a PSHUFB version back in 2006, but with standard polynomial, not reciprocal polynomial. I tested ISA-L and @GrokDarkMatter LFSR code with the same parameters as you, m=20. Grok's code is C intrinsics, so it's slower than ISA-L, at least for m <= 20. Do you also have code for standard polynomial instead reciprocal polynomial, which will be slower, but I'd like to see how it compares to ISA-L. Single erasure correction can be done using XOR with reciprocal polynomial if p is odd, but a normal polynomial with one root = 1 is needed if p is even.

[jeffareid]

@sam-lexx

Links to the zip files:

https://rcgldr.net/erszip/ersxenc6.zip

Create a directory c:\ersxenc6 and unzip ersxenc6.zip into it.

https://rcgldr.net/erszip/nasm.zip

Create a directory c:\nasm and unzip nasm.zip into it.

I'm using Visual Studio 2022. The code only supports AVX512+GFNI. The solution | project name is ersxenc6. ersr6a.asm uses self-reciprocal polynomials, while ersp6a.asm uses standard polynomials and is slower than ersr6a.asm, but faster than ISA-L. The project uses the file ersx6a.asm, copy ersr6a.asm or ersp6a.asm to ersx6a.asm to do the build. There are defines at the start of erasure_code_perf.c that I added that need to be edited depending on which encoding and how many parities to test. Define RCP to 1 for ersr6a.asm or define BCH to 1 for ersp6a.asm. ersx6a.asm is assembled using masm, while all of the gf_?vect...asm files are assembled using nasm. The total number of rows is defined by M and needs to be 20. The number of parities is defined by P and can be 1 to 6. Note that P=1 is just XOR.

I also tested Grok's code and it is slower than ISA-L since it uses C intrinsics as you noted. I looked at his repository and there have been no updates since 3 months ago, so I assume he lost interest.

No one else here at Intel has shown interest in any alternate encoding scheme, since it would not be compatible with the existing erasure code implementations (BackBlaze, Ceph, ZFS, ...). This was mostly an academic exercise for me, a derivative of my 1987 code which I updated to use PSHUFB in 2006, and recently updated again to use vgf2p8affineqb. The 1987 code was used for software based erasure | error correction on QIC-02 and QIC-40|80|... type tape drives. On later drives, erasure | error correction code was hardware based, with some software involved. After that, software based erasure + error correction code was only done for hardware development | verification. Intel announced PSHUFB in a 2004 publishing of their patent filed for in 2003. The first chips to include PSHUFB were released in June 2006, and my company bought systems that supported PSHUFB to use with LFSR based erasure + error correction software testing soon after. I bought a system that supported PSHUFB in Oct 2006 so I could enhance the LFSR stuff at home. I bought a laptop mid 2025 so I could test AVX512+GFNI based LFSR code at home. Throughout all of this, the code has been based on the 1987 code, using the same unfolded loop using macros logic as seen if you look at the old code from the links in my prior post.

[jeffareid]

@sam-lexx - link to RS(64,54) m=64, k= 54, p = 10, c = 480 (# of columns) pshufb assembly code from 2006. This matches the prior C2 RS(64,54), 480 columns for LTO3 | LTO4 mentioned in the LTO5 patent that details C2 RS(96,84) for LTO5. The code uses a loop where values are shifted as opposed to registers logically shifted, which is slower than an unfolded loop but was good enough for testing at the time. The code generates parities (encode), then generates syndromes (decode) and checks the syndromes for all zero. It returns an error code in rax: 0 = passed, 1 = failed.

erssym.asm

Batch file to run encsyn and echo if the code passed or failed based on the returned error code.

encsyn.bat

For p=6, AVX512+GFNI, self-reciprocal polynomial, unfolded code that cycles registers is about 20% faster than a loop that cycles values through registers on my system. I only did this as a proof of concept with m fixed at 20. For a variable m, the unfolded loop includes the maximum value of m instances of the unfolded loop. The equivalent of a switch | case to branch into the unfolded code is implemented using registers to hold the addresses to jump to. The code is similar to a 1987 encode function I worked on. No one in the ISA-L group seems interested in this so I didn't bother making the code generic.

[jeffareid]

@sam-lexx - I tested the Visual Studio zip file with both VS2022 and VS2026, it builds fine with either

You mentioned using pshufb back in 2006 issue #355. In 2004, Intel announced they were working on EMT64, their version of AMD64 64 bit mode (later called Intel 64), as well as xmm registers, pshub, ..., , In July 2006, Intel released their first X86-X64 (64 bit) desktop and laptop processors - Core 2, which also included the xmm | pshufb stuff, so it became popular quickly for parallel table lookup, as described in their 2003 patent. My company bought a few desktops with the Core 2 X6800 in August 2006, and I ended up buying one in October 2006 so I could work on this stuff from home. Links for some history on this:

https://patents.google.com/patent/US20040054879A1/en

https://patents.google.com/patent/US7761694

https://en.wikipedia.org/wiki/Conroe_(microprocessor)

https://en.wikipedia.org/wiki/Intel_Core_2

2008 - Advanced bit manipulation instructions - Princeton University

https://www.proquest.com/openview/0ad3a2474b0691b65b35582fbdb3cf40/1?pq-origsite=gscholar&cbl=18750

2008 - Wojciech Mulai - PSHUFB used for optimized pop count

https://www.chessprogramming.org/Wojciech_Mu%C5%82a

2009 - Ampire lab - used for encryption and decryption. Includes references to
Reed Solomon, as there is a Reed Solmoon based encryption method.

http://www.hyperelliptic.org/SPEED/record09.pdf

---

Although no one in the ISA-L group seems interested, in my spare time, I've been slowly updating my AVX512+GFNI encoder so it can handle a variable number of rows instead of just 20. When I get it done, I'll post a link. Although it's working with ISA-L, the use case is different, since ISA-L is focused on improving existing erasure codes as opposed to alternate codes, which would include BackBlaze, Ceph, and ZFS, although ZFS is a lot more than just an erasure code.

[sam-lexx]

@jeffareid

I think a fairly large group was aware of Intel's 2006 release of 64 bit mode and the xmm stuff like pshufb. My comment in #355 about parallel multiplier was based on the fact that hardware has been using parallel multipliers since the 1980's and those involved were waiting for something similar in CPUs. It was a long wait from Intel's 2004 announcement before the first actual processors to implement something that could do the equivalent by doing existing software table lookup based multiplies in parallel using pshufb in 2006, later 4 pclmulqdq in parallel with AVX512, then 8 by 8 parallel carryless multiply with vgf2p8affineqb for 64 parallel multiplies.

When you get variable number of rows version working, I'll try it out, but as you commented, I don't think anyone else at ISA-L is interested.

[jeffareid]

@sam-lexx - I already had a variable number of rows done, but limited to a max of 32 rows. This could easily be increased, but I don't see the point, so I'll just leave it as is for now. To do a build with the prior zip for VS2022 | VS2026, just copy ersrna.asm to ersx6a.asm , edit erasure_code_perf.c to set total number of rows M and number of parity rows P, and number of columns per row NCOL . NCOL needs to a multiple of 128 for P = 2 to 6, and multiple of 256 for P = 1. I don't plan on updating this either, since it's just a proof of concept, enough to compare LFSR self-reciprocal polynomial encoding versus matrix encoding. Decoding for a single erasure can be done with XOR if P is an odd number. For even numbers, a regular polynomial is needed, but due to lack of interest, I"m not going to spend more time on this.

ersna.asm

The code uses tables of pointers to code, one points to code to load a register, the other a pointer to jump into the unfolded loop. There is a one time load of pointers into rsi and rdi. A jmp rsi is done to load a register, and that code does a jmp rdi to jump into the unfolded inner loop. There was little to no impact on performance with the two jumps done once per outer loop into the unfolded inner loop. Again, this follows the strategy of the 1986-1987 code.