Accelerating Galois Field Arithmetic for Reed-Solomon Erasure Codes in Storage Applications

Galois fields (also called finite fields) play an essential role in the areas of cryptography and coding theory. They are the foundation of various error- and erasure-correcting codes and therefore central to the design of reliable storage systems. The efficiency and performance of these systems depend considerably on the implementation of Galois field arithmetic, in particular on the implementation of the multiplication. In current software implementations multiplication is typically performed by using pre-calculated lookup tables for the logarithm and its inverse or even for the full multiplication result. However, today the memory subsystem has become one of the main bottlenecks in commodity systems and relying on large in-memory data structures accessed from inner loop code can severely impact the overall performance and deteriorate scalability. In this paper, we study the execution of Galois field multiplication on modern processor architectures without using lookup tables. Instead we propose to trade computation for memory references and, therefore, to perform full polynomial multiplication with modular reduction using the generator polynomial of the Galois field. We present a SIMDized (vectorized) implementation of the polynomial multiplication algorithm in GF(2^16) and show the performance on commodity processors and on GPGPU accelerators.