A Complete Treatment of Software Implementations of Finite Field Arithmetic for Erasure Coding Applications
Technical Report UT-CS-13-717
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.
- Plain Text:
author J. S. Plank and K. M. Greenan and E. L. Miller
title A Complete Treatment of Software Implementations of Finite Field Arithmetic
for Erasure Coding Applications
institution University of Tennessee
author = "J. S. Plank and K. M. Greenan and E. L. Miller",
title = "A Complete Treatment of Software Implementations of Finite Field Arithmetic
for Erasure Coding Applications",
institution = "University of Tennessee",
month = "October",
year = "2013",
number = "UT-CS-13-717",
where = "http://web.eecs.utk.edu/~jplank/plank/papers/UT-CS-13-717.html"