gPPM: A Generalized Matrix Operation and Parallel Algorithm to Accelerate the Encoding/Decoding Process of Erasure Codes
Open Access
- 14 December 2023
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Architecture and Code Optimization
- Vol. 20 (4) , 1-25
Abstract
Erasure codes are widely deployed in modern storage systems, leading to frequent usage of their encoding/decoding operations. The encoding/decoding process for erasure codes is generally carried out using the parity-check matrix approach. However, this approach is serial and computationally expensive, mainly due to dealing with matrix operations, which results in low encoding/decoding performance. These drawbacks are particularly evident for newer erasure codes, including SD and LRC codes. To address these limitations, this article introduces the Partitioned and Parallel Matrix ( PPM ) algorithm. This algorithm partitions the parity-check matrix, parallelizes encoding/decoding operations, and optimizes calculation sequence to facilitate fast encoding/decoding of these codes. Furthermore, we present a generalized PPM ( gPPM ) algorithm that surpasses PPM in performance by employing fine-grained dynamic matrix calculation sequence selection. Unlike PPM, gPPM is also applicable to erasure codes such as RS code. Experimental results demonstrate that PPM improves the encoding/decoding speed of SD and LRC codes by up to 210.81%. Besides, gPPM achieves up to 102.41% improvement over PPM and 32.25% improvement over RS regarding encoding/decoding speed.Keywords
Funding Information
- Major Key Project of PCL (PCL2022A03)
- National Natural Science Foundation of China (62172175 and 61972441)
- Shenzhen Science and Technology Innovation Program (RCYX20210609104510007 and JCYJ20200109113427092)
- Open Project Program of Wuhan National Laboratory for Optoelectronics (2022WNLOKF010)
- Young Innovative Talents Project of general colleges and universities in Guangdong Province (2022KQNCXl59)
- Natural Science Foundation of Shandong Province (ZR2020LZH014)
- Guangdong Provincial Key Laboratory of Novel Security Intelligence Technologies (2022B1212010005)
This publication has 6 references indexed in Scilit:
- A Hierarchical RAID Architecture Towards Fast Recovery and High ReliabilityIEEE Transactions on Parallel and Distributed Systems, 2017
- ${\rm S}^{2}$-RAID: Parallel RAID Architecture for Fast Data RecoveryIEEE Transactions on Parallel and Distributed Systems, 2013
- An Efficient Penalty-Aware Cache to Improve the Performance of Parity-Based Disk Arrays under Faulty ConditionsIEEE Transactions on Parallel and Distributed Systems, 2012
- Automatic recovery from disk failure in continuous-media serversIEEE Transactions on Parallel and Distributed Systems, 2002
- EVENODD: an efficient scheme for tolerating double disk failures in RAID architecturesIEEE Transactions on Computers, 1995
- Polynomial Codes Over Certain Finite FieldsJournal of the Society for Industrial and Applied Mathematics, 1960