EECS Publication
A Complete Treatment of Software Implementations of Finite Field Arithmetic for Erasure Coding Applications
James S. Plank and Kevin M. Greenan and Ethan L. Miller
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(2^w). There are many ways to implement finite field arithmetic in software, plus a few tricks to aid performance. This paper describes the various implementations and tricks, in tutorial-level detail, as they specifically apply to erasure coded storage systems. It also introduces an open-source Galois Field field arithmetic library that implements all of these techniques and tricks, and gives a rough performance evaluation.
Published 2013-10-14 04:00:00 as ut-cs-13-717 (ID:576)
ut-cs-13-717.pdf
http://web.eecs.utk.edu/~plank/plank/papers/UT-CS-13-717.html