Article

Screaming fast Galois field arithmetic using intel SIMD instructions

Authors:

James S. Plank,

Kevin M. Greenan,

Ethan L. MillerAuthors Info & Claims

FAST'13: Proceedings of the 11th USENIX conference on File and Storage Technologies

Pages 299 - 306

Published: 12 February 2013 Publication History

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.

References

[1]

H. P. Anvin. The mathematics of RAID- 6. http://kernel.org/pub/linux/kernel/ people/hpa/raid6.pdf, 2011.

[2]

M. Blaum, J. Brady, J. Bruck, and J. Menon. EVENODD: An efficient scheme for tolerating double disk failures in RAID architectures. IEEE Transactions on Computing, 44(2):192- 202, February 1995.

Digital Library

[3]

M. Blaum, J. L. Hafner, and S. Hetzler. Partail-MDS codes and their application to RAID type of architectures. IBM Research Report RJ10498 (ALM1202-001), February 2012.

[4]

M. Blaum and R. M. Roth. On lowest density MDS codes. IEEE Transactions on Information Theory, 45(1):46-59, January 1999.

Digital Library

[5]

J. Blomer, M. Kalfane, M. Karpinski, R. Karp, M. Luby, and D. Zuckerman. An XOR-based erasure-resilient coding scheme. Technical Report TR-95-048, International Computer Science Institute, August 1995.

[6]

B. Calder, J. Wang, A. Ogus, N. Nilakantan, A. Skjolsvold, S. McKelvie, Y. Xu, S. Srivastav, J. Wu, H. Simitci, J. Haridas, C. Uddaraju, H. Khatri, A. Edwards, V. Bedekar, S. Mainali, R. Abbasi, A. Agarwal, M. Fahim ul Haq, M. Ikram ul Haq, D. Bhardwaj, S. Dayanand, A. Adusumilli, M. Mc-Nett, S. Sankaran, K. Manivannan, and L. Rigas. Windows Azure Storage: A highly available cloud storage service with strong consistency. In 23rd ACM Symposium on Operating Systems Principles, October 2011.

Digital Library

[7]

P. Corbett, B. English, A. Goel, T. Grcanac, S. Kleiman, J. Leong, and S. Sankar. Row diagonal parity for double disk failure correction. In 3rd Usenix Conference on File and Storage Technologies, San Francisco, CA, March 2004.

Digital Library

[8]

A. G. Dimakis, K. Ramchandran, Y. Wu, and C. Suh. A survey on network codes for distributed storage. Proceedings of the IEEE, 99(3), March 2011.

[9]

K. Greenan, E. Miller, and T. J. Schwartz. Optimizing Galois Field arithmetic for diverse processor architectures and applications. In MASCOTS 2008: 16th IEEE Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems, Baltimore, MD, September 2008.

[10]

Y. Hu, H. C. H. Chen, P. P. C. Lee, and Y. Tang. NCCloud: Applying network coding for the storage repair in a cloud-of-clouds. In FAST-2012: 10th Usenix Conference on File and Storage Technologies, San Jose, February 2012.

Digital Library

[11]

C. Huang, M. Chen, and J. Li. Pyramid codes: Flexible schemes to trade space for access efficienty in reliable data storage systems. In NCA- 07: 6th IEEE International Symposium on Network Computing Applications, Cambridge, MA, July 2007.

[12]

C. Huang, H. Simitci, Y. Xu, A. Ogus, B. Calder, P. Gopalan, J. Li, and S. Yekhanin. Erasure coding in Windows Azure storage. In USENIX Annual Technical Conference, Boston, June 2012.

Digital Library

[13]

C. Huang and L. Xu. STAR: An efficient coding scheme for correcting triple storage node failures. IEEE Transactions on Computers, 57(7):889-901, July 2008.

Digital Library

[14]

Intel Corporation. Intel Integrated Performance Primitives for Intel architecture, reference manual IPP 7.1. http://software.intel.com, 2000-2012.

[15]

Intel Corporation. Intel 64 and IA-32 architectures software developers manual, combined volumes: 1, 2A, 2B, 2C, 3A, 3B and 3C. Order Number: 325462-044US, August 2012.

[16]

S. Kalcher and V. Lindenstruth. Accelerating Galois Field arithmetic for Reed-Solomon erasure codes in storage applications. In IEEE International Conference on Cluster Computing, 2011.

Digital Library

[17]

O. Khan, R. Burns, J. S. Plank, W. Pierce, and C. Huang. Rethinking erasure codes for cloud file systems: Minimizing I/O for recovery and degraded reads. In FAST-2012: 10th Usenix Conference on File and Storage Technologies, San Jose, February 2012.

Digital Library

[18]

A. Leventhal. Triple-parity RAID and beyond. Communications of the ACM, 53(1):58-63, January 2010.

Digital Library

[19]

X. Li, A. Marchant, M. A. Shah, K. Smathers, J. Tucek, M. Uysal, and J. J. Wylie. Efficient eventual consistency in Pahoehoe, an erasurecoded key-blob archive. In DSN-10: International Conference on Dependable Systems and Networks, Chicago, 2010. IEEE.

[20]

J. Lopez and R. Dahab. High-speed software multiplication in f_2m. In Annual International Conference on Cryptology in India, 2000.

Digital Library

[21]

J. Luo, K. D. Bowers, A. Oprea, and L. Xu. Efficient software implementations of large finite fields GF(2ⁿ) for secure storage applications. ACM Transactions on Storage, 8(2), February 2012.

Digital Library

[22]

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

Digital Library

[23]

J. S. Plank, M. Blaum, and J. L. Hafner. SD codes: Erasure codes designed for how storage systems really fail. In FAST-2013: 11th Usenix Conference on File and Storage Technologies, San Jose, February 2013.

[24]

J. S. Plank and Y. Ding. Note: Correction to the 1997 tutorial on reed-solomon coding. Technical Report CS-03-504, University of Tennessee, April 2003.

[25]

J. S. Plank, K. M. Greenan, E. L. Miller, and W. B. Houston. GF-Complete: A comprehensive open source library for Galois Field arithmetic. Technical Report UT-CS-13-703, University of Tennessee, January 2013.

[26]

J. S. Plank, J. Luo, C. D. Schuman, L. Xu, and Z. Wilcox-O'Hearn. A performance evaluation and examination of open-source erasure coding libraries for storage. In FAST-2009: 7th Usenix Conference on File and Storage Technologies, pages 253-265, February 2009.

Digital Library

[27]

I. S. Reed and G. Solomon. Polynomial codes over certain finite fields. Journal of the Society for Industrial and Applied Mathematics, 8:300-304, 1960.

[28]

J. K. Resch and J. S. Plank. AONT-RS: blending security and performance in dispersed storage systems. In FAST-2011: 9th Usenix Conference on File and Storage Technologies, pages 191-202, San Jose, February 2011.

Digital Library

[29]

S. Rhea, P. Eaton, D. Geels, H. Weatherspoon, B. Zhao, and J. Kubiatowitz. Pond: The OceanStore prototype. In FAST-2003: 2nd Usenix Conference on File and Storage Technologies, San Francisco, January 2003.

Digital Library

[30]

L. Rizzo. Effective erasure codes for reliable computer communication protocols. ACM SIGCOMM Computer Communication Review, 27(2):24-36, 1997.

Digital Library

[31]

M. W. Storer, K. M. Greenan, E. L. Miller, and K. Voruganti. Pergamum: Replacing tape with energy efficient, reliable, disk-based archival storage. In FAST-2008: 6th Usenix Conference on File and Storage Technologies, pages 1-16, San Jose, February 2008.

Digital Library

[32]

M. W. Storer, K. M. Greenan, E. L. Miller, and K. Voruganti. POTSHARDS - a secure, long-term storage system. ACM Transactions on Storage, 5(2), June 2009.

Digital Library

[33]

L. Xu and J. Bruck. X-Code: MDS array codes with optimal encoding. IEEE Transactions on Information Theory, 45(1):272-276, January 1999.

Digital Library

Cited By

Chen JYang SWang YYe MLei F(2024)Data repair accelerating scheme for erasure-coded storage system based on FPGA and hierarchical parallel decoding structureCluster Computing10.1007/s10586-024-04401-x27:6(7803-7823)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1007/s10586-024-04401-x
Li SCao QWan SXia WXie C(2023)gPPM: A Generalized Matrix Operation and Parallel Algorithm to Accelerate the Encoding/Decoding Process of Erasure CodesACM Transactions on Architecture and Code Optimization10.1145/362500520:4(1-25)Online publication date: 21-Sep-2023
https://dl.acm.org/doi/10.1145/3625005
Zhou TTian CMerchant AWeatherspoon H(2019)Fast erasure coding for data storageProceedings of the 17th USENIX Conference on File and Storage Technologies10.5555/3323298.3323329(317-329)Online publication date: 25-Feb-2019
https://dl.acm.org/doi/10.5555/3323298.3323329
Show More Cited By

Recommendations

Retargetable code optimization with SIMD instructions
CODES+ISSS '06: Proceedings of the 4th international conference on Hardware/software codesign and system synthesis

Retargetable C compilers are nowadays widely used to quickly obtain compiler support for new embedded processors and to perform early processor architecture exploration. One frequent concern about retargetable compilers, though, is their lack of machine-...
Exploiting Parallelism in Geometry Processing with General Purpose Processors and Floating-Point SIMD Instructions

Three-dimensional (3D) graphics applications have become very important workloads running on today's computer systems. A cost-effective graphics solution is to perform geometry processing of 3D graphics on the host CPU and have specialized hardware ...
Automatic generation of custom SIMD instructions for superword level parallelism
DATE '14: Proceedings of the conference on Design, Automation & Test in Europe

Application specific instruction-set processors (ASIPs) have drawn significant attention from System-on-a-Chip (SoC) community due to the capability of fine grain flexibility and customizability. In order to maximize the benefit of ASIP, automatic ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

FAST'13: Proceedings of the 11th USENIX conference on File and Storage Technologies

February 2013

320 pages

Program Chairs:
Keith A. Smith
NetApp
,
Yuanyuan Zhou
University of California, San Diego

Sponsors

USENIX Assoc: USENIX Assoc

In-Cooperation

SIGOPS: ACM Special Interest Group on Operating Systems

Publisher

USENIX Association

United States

Publication History

Published: 12 February 2013

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

27
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Chen JYang SWang YYe MLei F(2024)Data repair accelerating scheme for erasure-coded storage system based on FPGA and hierarchical parallel decoding structureCluster Computing10.1007/s10586-024-04401-x27:6(7803-7823)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1007/s10586-024-04401-x
Li SCao QWan SXia WXie C(2023)gPPM: A Generalized Matrix Operation and Parallel Algorithm to Accelerate the Encoding/Decoding Process of Erasure CodesACM Transactions on Architecture and Code Optimization10.1145/362500520:4(1-25)Online publication date: 21-Sep-2023
https://dl.acm.org/doi/10.1145/3625005
Zhou TTian CMerchant AWeatherspoon H(2019)Fast erasure coding for data storageProceedings of the 17th USENIX Conference on File and Storage Technologies10.5555/3323298.3323329(317-329)Online publication date: 25-Feb-2019
https://dl.acm.org/doi/10.5555/3323298.3323329
Gopi SGuruswami VYekhanin SChan T(2019)Maximally recoverable LRCsProceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3310435.3310565(2154-2170)Online publication date: 6-Jan-2019
https://dl.acm.org/doi/10.5555/3310435.3310565
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 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
Duan SReiter MZhang HLie DMannan MBackes MWang X(2018)BEATProceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security10.1145/3243734.3243812(2028-2041)Online publication date: 15-Oct-2018
https://dl.acm.org/doi/10.1145/3243734.3243812
Bel OChang KBittman DLong DIsozaki HMiller EBreitgand DYadgar GPorter DEyal I(2018)InkpackProceedings of the 11th ACM International Systems and Storage Conference10.1145/3211890.3211899(89-100)Online publication date: 4-Jun-2018
https://dl.acm.org/doi/10.1145/3211890.3211899
Shor RYadgar GHuang WYaakobi EBruck JBreitgand DYadgar GPorter DEyal I(2018)How to Best Share a Big SecretProceedings of the 11th ACM International Systems and Storage Conference10.1145/3211890.3211896(76-88)Online publication date: 4-Jun-2018
https://dl.acm.org/doi/10.1145/3211890.3211896
Schwarz TBreitgand DYadgar GPorter DEyal I(2018)Protecting Single Shingled Write Drives Against Latent Sector FailuresProceedings of the 11th ACM International Systems and Storage Conference10.1145/3211890.3211893(26-36)Online publication date: 4-Jun-2018
https://dl.acm.org/doi/10.1145/3211890.3211893
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Table of Contents