Gibraltar: A Reed-Solomon Coding Library for Storage Applications on Programmable Graphics Processors

Reed-Solomon coding is a method for generating arbitrary amounts of erasure correction information from original data via matrix-vector multiplication in finite fields. Previous work has shown that modern CPUs are not well-matched to this type of computation, requiring applications that depend on Reed-Solomon coding at high speeds (such as high-performance storage arrays) to use hardware implementations. This work demonstrates that high performance is possible with current cost-effective graphics processing units across a wide range of operating conditions and describes how performance will likely evolve in similar architectures. It describes the characteristics of the graphics processing unit architecture that enable high-speed Reed-Solomon coding. A high-performance practical library, Gibraltar, has been prototyped that performs Reed-Solomon coding on graphics processors in a manner suitable for storage arrays, along with applications with similar data resiliency needs. This library enables variably resilient erasure correcting codes to be used in a broad range of applications. Its performance is compared with that of a widely available CPU implementation, and a rationale for its API is presented. Its practicality is demonstrated through a usage example. Copyright (C) 2011 John Wiley & Sons, Ltd.