Tag Archives: SIMD

Galois Fields @ USENIX FAST 2013

USENIX sponsors an annual storage related conference called File and Storage Technologies or FAST for short. It has been happening for more than a decade and this year’s FAST seminar has lined up an impressive list of sessions. Of all those, there is one session that caught my attention: https://www.usenix.org/conference/fast13/screaming-fast-galois-field-arithmetic-using-sse2-extensions

Galois Field or Finite Field is a construct out of Abstract Algebra which raises it’s spooky head whenever Cryptography, Error Correcting Codes, Rabin Deduplication, number theory and related stuff are concerned.  It is interesting to see EMC having done work on speeding up GF computations on modern x86 CPUs using the SSE SIMD instruction set. However it does not appear to be an entirely new work. There has already been work done on this aspect. For example look at the following links:

Optimizing Forward ECC Codes using SIMD instructions

Impact of Intel’s New Instruction Sets on Software Implementation of GF(2)[x] Multiplication

gf2x – A library for multiplying polynomials over the binary field

EMC is obviously interested in speeding up Data Deduplication in it’s Data Domain products. So we should see subsequent releases of Data Domain coming with this optimization. It will be interesting to see what other work the EMC paper cites when it is eventually made public.

Of the above three links the first one is of most interest to me. I am looking to implement error correcting codes in Pcompress and that article’s author provides a nice SIMD-optimized ECC library called FECpp.