A Complete Treatment of Software Implementations of Finite Field Arithmetic for Erasure Coding Applications

James S. Plank (University of Tennessee),
Kevin M. Greenan (Box),
Ethan L. Miller (UC Santa Cruz).

October, 2013

Technical Report UT-CS-13-717
EECS Department
University of Tennessee
Knoxville, TN 37996

PDF of the paper.


Finite field arithmetic lies at the heart of erasure codes that protect storage systems from failures. This arithmetic defines addition and multiplication over a closed set of numbers such that every number has a unique multiplicative inverse. For storage systems, the size of these sets is typically a power of two, and the finite fields most often employed are Galois Fields, denoted GF(2w). There are many ways to implement finite field arithmetic in software, plus a few tricks to aid performance. In this paper, we describe the various implementations and tricks, in tutorial- level detail, as they specifically apply to erasure coded storage systems. We also introduce an open-source Galois Field field arithmetic library called "GF-Complete" that implements all of these techniques and tricks, and give a rough performance evaluation.

Citation Information