Analysis and Construction of Galois Fields for Efficient Storage Reliability

Published as Storage Systems Research Center Technical Report UCSC-SSRC-07-09. Revised version published in MASCOTS 2008..

Abstract

Software-based Galois field implementations are used in the reliability and security components of many storage systems. Unfortunately, multiplication and division operations over Galois fields are expensive, compared to the addition. To accelerate multiplication and division, most software Galois field implementations use pre-computed look-up tables, accepting the memory overhead associated with optimizing these operations. However, the amount of available memory constrains the size of a Galois field and leads to inconsistent performance across architectures. This is especially problematic in environments with limited memory, such as sensor networks.

In this paper, we first analyze existing table-based implementation and optimization techniques for GF(2^l) multiplication and division. Next, we propose the use of techniques that perform multiplication and division in an extension of GF(2^l), where the actual multiplications and divisions are performed in a smaller field and combined. This approach allows different applications to share Galois field multiplication tables, regardless of the field size, while drastically lowering memory consumption. We evaluated multiple such approaches in terms of basic operation performance and memory consumption. We then evaluated different approaches for their suitability in common Galois field applications. Our experiments showed that the relative performance of each approach varies with processor architecture, and that CPU, memory limitations and field size must be considered when selecting an appropriate Galois field implementation. In particular, the use of extension fields is often faster and less memory-intensive than comparable approaches using standard algorithms for GF(2^l).

Publication date:
August 2007

Authors:
Kevin Greenan
Ethan L. Miller
Thomas Schwarz

Projects:
Archival Storage
Secure File and Storage Systems
Reliable Storage

Available media

Full paper text: PDF

Bibtex entry

@techreport{greenan-ssrctr07,
  author       = {Kevin Greenan and Ethan L. Miller and Thomas Schwarz},
  title        = {Analysis and Construction of Galois Fields for Efficient Storage Reliability},
  institution  = {University of California, Santa Cruz},
  number       = {UCSC-SSRC-07-09},
  month        = aug,
  year         = {2007},
}