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

Abstract

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. 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

Plain Text:

.techreport     pgm:13:cts
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

Bibtex:

@TECHREPORT{pgm:13:cts,
        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"
}

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).

Abstract

Citation Information

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