Screaming Fast Galois Field Arithmetic Using Intel SIMD Extensions

Appeared in Proceedings of the 11th Conference on File and Storage Systems (FAST 2013).

Abstract

Galois Field arithmetic forms the basis of Reed-Solomon and other erasure coding techniques to protect storage systems from failures. Most implementations of Galois Field arithmetic rely on multiplication tables or discrete logarithms to perform this operation. However, the advent of 128-bit instructions, such as Intel’s Streaming SIMD Extensions, allows us to perform Galois Field arithmetic much faster. This short paper details how to leverage these instructions for various field sizes, and demonstrates the significant performance improvements on commodity microprocessors. The techniques that we describe are available as open source software.

Publication date:
February 2013

Authors:
James Plank
Kevin Greenan
Ethan L. Miller

Projects:
High-Performance Galois Field Arithmetic
Secure File and Storage Systems
Reliable Storage

Available media

Full paper text: PDF

Bibtex entry

@inproceedings{plank-fast13,
  author       = {James Plank and Kevin Greenan and Ethan L. Miller},
  title        = {Screaming Fast Galois Field Arithmetic Using Intel {SIMD} Extensions},
  booktitle    = {Proceedings of the 11th Conference on File and Storage Systems (FAST 2013)},
  month        = feb,
  year         = {2013},
}