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:

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.

2 thoughts on “Galois Fields @ USENIX FAST 2013

  1. Bulat Ziganshin (@justbulat)

    1. link to “Impact of Intel’s New Instruction Sets on Software Implementation of GF(2)[x] Multiplication” is broken (start it with http://)
    2. “Impact of Intel’s New Instruction Sets on Software Implementation of GF(2)[x] Multiplication” and gf2x are absolutely meaningless for error correction since they discuss multiplication in too large Galois fields
    3. FECpp and first paper isn’t as interesting as Plank paper since FECpp supports only 8-bit galois fields. Plank already placed his low-level library (i.e. GF arithmetics) on github and promised to bring high-level one (i.e. ECC encoding/decoding) in August

    1. moinakg Post author

      Thanks. I fixed the link. Now that the GF-Complete library is available the other ones are less useful at this point.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s