article

Gibraltar: A Reed-Solomon coding library for storage applications on programmable graphics processors

Authors:

Matthew L. Curry,

Anthony Skjellum,

Ron BrightwellAuthors Info & Claims

Concurrency and Computation: Practice & Experience, Volume 23, Issue 18

Pages 2477 - 2495

https://doi.org/10.1002/cpe.1810

Published: 01 December 2011 Publication History

Abstract

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 © 2011 John Wiley & Sons, Ltd.

(Gibraltar is available at, along with sample applications to test it.)

References

[1]

Chen PM, Lee EK, Gibson GA, Katz RH, Patterson DA. RAID: High performance, reliable secondary storage. ACM Computing Surveys 1994; 26(2):145–185.

[2]

Reed IS, Chen X. Error-control Coding for Data Networks. Kluwer Academic Publishers: Dordrecht, Netherlands, 1999.

[3]

Blaum M, Brady J, Bruck J, Menon J. EVENODD: An optimal scheme for tolerating double disk failures in RAID architectures. In Proceedings of the 21st Annual International Symposium on Computer Architecture, 1994;245–254.

[4]

Reed IS, Solomon G. Polynomial codes over certain finite fields. Journal of the Society for Industrial and Applied Mathematics 1960; 8(2):300–304.

[5]

Corbett P, English B, Goel A, Grcanac T, Kleiman S, Leong J, Sankar S. Row-diagonal parity for double disk failure correction. In Proceedings of the 3rd USENIX Symposium on File and Storage Technologies (FAST 04), 2004; 1–14.

[6]

Plank JS. A new MDS erasure code for RAID-6. Technical Report CS-07-602, University of Tennessee, September 2007.

[7]

Peter Anvin H. The mathematics of RAID-6. Available from:, {Accessed on January 6, 2010}.

[8]

Foley JD, van Dam A, Feiner SK, Hughes JF. Computer Graphics: Principles and Practice in C, 2nd edn. Addison-Wesley Professional: Boston, Massachusetts, 1995.

[9]

NVIDIA Corporation. NVIDIA's next generation CUDA compute architecture: Fermi, 2009.

[10]

From a few cores to many: A tera-scale computing research overview, 2006. Available from: .

[11]

Carr NA, Hoberock J, Crane K, Hart JC. Fast GPU ray tracing of dynamic meshes using geometry images. In GI '06: Proceedings of Graphics Interface 2006. Canadian Information Processing Society: Toronto, Ont., Canada, 2006; 203–209.

Digital Library

[12]

Galoppo N, Govindaraju NK, Henson M, Manocha D. LU-GPU: Efficient algorithms for solving dense linear systems on graphics hardware. In SC '05: Proceedings of the 2005 ACM/IEEE Conference on Supercomputing. IEEE Computer Society: Washington, DC, USA, 2005; 3.

[13]

Patidar S, Bhattacharjee S, Singh JM, Narayanan PJ. Exploiting the shader model 4.0 architecture. Technical Report 145, International Institute of Information Technology, Hyderabad, 2007.

[14]

Göddeke D, Strzodka R, Turek S. Accelerating double precision FEM simulations with GPUs. In Proceedings of the 18th Symposium on Simulation Technique (ASIM 2005), Hülsemann F, Kowarschik M, Rüde U (eds). SCS Publishing House e.V: Erlangen, Germany, September 2005; 139–144.

[15]

NVIDIA Corporation. NVIDIA CUDA C programming guide, version 3.2, November 2010.

[16]

AMD. ATI CTM guide, 2006. Available from:, {Accessed on July 27, 2009}.

[17]

AMD. ATI Stream technology: Technical overview, 2008. Available from:, {Accessed on July 27, 2009}.

[18]

Curry ML, Skjellum A, Ward HL, Brightwell R. Accelerating Reed–Solomon coding in RAID systems with GPUs. In IEEE International Symposium on Parallel and Distributed Processing, 2008, April 2008; 1–6.

[19]

Curry ML, Ward HL, Skjellum A, Brightwell R. Arbitrary dimension Reed–Solomon coding and decoding for extended RAID on GPUs. 3rd Petascale Data Storage Workshop held in conjunction with SC08, November 2008.

[20]

Plank JS, Simmerman S, Schuman CD. Jerasure: a library in C/C++ facilitating erasure coding for storage applications, - Version 1.2. Technical Report CS-08-627, University of Tennessee, August 2008.

[21]

Seagate Technology LLC. Barracuda ES.2 data sheet, 2008. Available from: .

[22]

Pinheiro E, Weber W-D, Barroso LA. Failure trends in a large disk drive population. In Proceedings of the 5th USENIX Conference on File and Storage Technologies. USENIX Association: Berkeley, CA, USA, 2007; 17–28.

[23]

Schroeder B, Gibson GA. Disk failures in the real world: what does an MTTF of 1,000,000 hours mean to you? In Proceedings of the 5th USENIX Conference on File and Storage Technologies. USENIX Association: Berkeley, CA, USA, 2007; 1–1.

[24]

Pâris J-F, Long DDE. Using device diversity to protect data against batch-correlated disk failures. In StorageSS '06: Proceedings of the Second ACM Workshop on Storage Security and Survivability. ACM Press: New York, NY, USA, 2006; 47–52.

[25]

Bairavasundaram LN, Goodson GR, Pasupathy S, Schindler J. An analysis of latent sector errors in disk drives. In SIGMETRICS '07: Proceedings of the 2007 ACM SIGMETRICS international conference on Measurement and modeling of computer systems. ACM: New York, NY, USA, 2007; 289–300.

[26]

Grochowski E, Halem RD. Technological impact of magnetic hard disk drives on storage systems. IBM Systems Journal 2003; 42(2):338–346.

[27]

Plank JS. A tutorial on Reed–Solomon coding for fault-tolerance in RAID-like systems. Software—Practice & Experience September 1997; 27(9):995–1012.

[28]

Lidl R, Niedrreiter H. Introduction to Finite Fields and their Applications. Cambridge University Press: New York, 1994.

[29]

Raghav B, Dubey PK, Kumar V, Rudra A. Efficient Galois field arithmetic on SIMD architectures. In SPAA '03: Proceedings of the Fifteenth Annual ACM Symposium on Parallel Algorithms and Architectures. ACM Press: New York, NY, USA, 2003; 256–257.

[30]

DasGupta A. The matching birthday and the strong birthday problem: a contemporary review. Journal of Statistical Planning and Inference 2005; 130(1–2):377–389. Herman Chernoff: Eightieth Birthday Felicitation Volume.

[31]

Levinthal D. Performance analysis guide for Intel Core i7 processor and Intel Xeon 5500 processors, version 1.0. Available from: .

[32]

Narayanan D, Thereska E, Donnelly A, Elnikety S, Rowstron A. Migrating server storage to SSDs: analysis of tradeoffs. In EuroSys '09: Proceedings of the fourth ACM european conference on Computer systems. ACM: New York, NY, USA, 2009; 145–158.

[33]

Kiayias A, Yung M. Cryptography and decoding Reed–Solomon codes as a hard problem. In Theory and Practice in Information-Theoretic Security, 2005. IEEE Information Theory Workshop on, Oct. 2005; 48–48.

[34]

Shamir A. How to share a secret. Communications of the ACM 1979; 22(11):612–613.

[35]

Curry ML, Ward HL, Skjellum A, Brightwell R. A lightweight, GPU-based software RAID system. In International Conference on Parallel Processing, 2010; 565–572.

Cited By

Hu JKosaian JRashmi K(2024)Rethinking Erasure-Coding Libraries in the Age of Optimized Machine LearningProceedings of the 16th ACM Workshop on Hot Topics in Storage and File Systems10.1145/3655038.3665943(23-30)Online publication date: 8-Jul-2024
https://dl.acm.org/doi/10.1145/3655038.3665943
Shi HLu XCuicchi CQualters IKramer W(2020)INECProceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis10.5555/3433701.3433788(1-17)Online publication date: 9-Nov-2020
https://dl.acm.org/doi/10.5555/3433701.3433788
Haddock WBangalore PCurry MSkjellum A(2019)High performance erasure coding for very large stripe sizesProceedings of the High Performance Computing Symposium10.5555/3338075.3338088(1-12)Online publication date: 29-Apr-2019
https://dl.acm.org/doi/10.5555/3338075.3338088
Show More Cited By

Gibraltar: A Reed-Solomon coding library for storage applications on programmable graphics processors

Recommendations

A performance study of general-purpose applications on graphics processors using CUDA

Graphics processors (GPUs) provide a vast number of simple, data-parallel, deeply multithreaded cores and high memory bandwidths. GPU architectures are becoming increasingly programmable, offering the potential for dramatic speedups for a variety of ...
Relational query coprocessing on graphics processors

Graphics processors (GPUs) have recently emerged as powerful coprocessors for general purpose computation. Compared with commodity CPUs, GPUs have an order of magnitude higher computation power as well as memory bandwidth. Moreover, new-generation GPUs ...
Accuracy and performance of graphics processors: A Quantum Monte Carlo application case study

The tradeoffs of accuracy and performance are as yet an unsolved problem when dealing with Graphics Processing Units (GPUs) as a general-purpose computation device. Their high performance and low cost makes them a desirable target for scientific ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Concurrency and Computation: Practice & Experience

Concurrency and Computation: Practice & Experience Volume 23, Issue 18

December 2011

137 pages

ISSN:1532-0626

EISSN:1532-0634

Issue’s Table of Contents

Publisher

John Wiley and Sons Ltd.

United Kingdom

Publication History

Published: 01 December 2011

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Hu JKosaian JRashmi K(2024)Rethinking Erasure-Coding Libraries in the Age of Optimized Machine LearningProceedings of the 16th ACM Workshop on Hot Topics in Storage and File Systems10.1145/3655038.3665943(23-30)Online publication date: 8-Jul-2024
https://dl.acm.org/doi/10.1145/3655038.3665943
Shi HLu XCuicchi CQualters IKramer W(2020)INECProceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis10.5555/3433701.3433788(1-17)Online publication date: 9-Nov-2020
https://dl.acm.org/doi/10.5555/3433701.3433788
Haddock WBangalore PCurry MSkjellum A(2019)High performance erasure coding for very large stripe sizesProceedings of the High Performance Computing Symposium10.5555/3338075.3338088(1-12)Online publication date: 29-Apr-2019
https://dl.acm.org/doi/10.5555/3338075.3338088
Shi HLu XShankar DPanda DWeissman JButt ASmirni E(2019)UMR-ECProceedings of the 28th International Symposium on High-Performance Parallel and Distributed Computing10.1145/3307681.3325406(219-230)Online publication date: 17-Jun-2019
https://dl.acm.org/doi/10.1145/3307681.3325406
Shi HLu XTaufer MBalaji PPeña A(2019)TriECProceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis10.1145/3295500.3356178(1-34)Online publication date: 17-Nov-2019
https://dl.acm.org/doi/10.1145/3295500.3356178
Shi HLu XShankar DPanda D(2018)High-Performance Multi-Rail Erasure Coding Library over Modern Data Center ArchitecturesProceedings of the ACM Symposium on Cloud Computing10.1145/3267809.3275472(530-531)Online publication date: 11-Oct-2018
https://dl.acm.org/doi/10.1145/3267809.3275472
Liu CWang QChu XLeung Y(2018)G-CRS: GPU Accelerated Cauchy Reed-Solomon CodingIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2018.279143829:7(1484-1498)Online publication date: 1-Jul-2018
https://dl.acm.org/doi/10.1109/TPDS.2018.2791438
Song TPirahandeh MAhn CKim D(2018)GPU-accelerated high-performance encoding and decoding of hierarchical RAID in virtual machinesThe Journal of Supercomputing10.1007/s11227-017-1969-y74:11(5865-5888)Online publication date: 1-Nov-2018
https://dl.acm.org/doi/10.1007/s11227-017-1969-y
Shi HLu XPanda D(2018)EC-Bench: Benchmarking Onload and Offload Erasure Coders on Modern Hardware ArchitecturesBenchmarking, Measuring, and Optimizing10.1007/978-3-030-32813-9_18(215-230)Online publication date: 10-Dec-2018
https://dl.acm.org/doi/10.1007/978-3-030-32813-9_18
(2016)Toward high-performance key-value stores through GPU encoding and locality-aware encodingJournal of Parallel and Distributed Computing10.1016/j.jpdc.2016.04.01596:C(27-37)Online publication date: 1-Oct-2016
https://dl.acm.org/doi/10.1016/j.jpdc.2016.04.015
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents