Accelerating XOR-Based Erasure Coding Using Program Optimization Techniques
Event Type
Paper

Algorithms
Parallel Programming Systems
TP
TimeThursday, 18 November 20212:30pm - 3pm CST
Location227-228
DescriptionErasure coding (EC) affords data redundancy for large-scale systems. XOR-based EC is an easy-to-implement method for optimizing EC. This paper addresses a significant performance gap between the state-of-the-art XOR-based EC approach (~4.9 GB/s coding throughput) and Intel's high-performance EC library based on another approach (~6.7 GB/s).
We propose a novel approach based on our observation that XOR-based EC virtually generates programs of a Domain Specific Language for XORing byte arrays. We formalize such programs as straight-line programs (SLPs) of compiler construction and optimize SLPs using various program optimization techniques.
Our optimization flow is three-fold:
1) reducing the number of XORs using grammar compression algorithms;
2) reducing memory accesses using deforestation, a functional program optimization method; and
3) reducing cache misses using the (red-blue) pebble game of program analysis.
We provide an experimental library, which outperforms Intel's library with an ~8.92 GB/s throughput.
We propose a novel approach based on our observation that XOR-based EC virtually generates programs of a Domain Specific Language for XORing byte arrays. We formalize such programs as straight-line programs (SLPs) of compiler construction and optimize SLPs using various program optimization techniques.
Our optimization flow is three-fold:
1) reducing the number of XORs using grammar compression algorithms;
2) reducing memory accesses using deforestation, a functional program optimization method; and
3) reducing cache misses using the (red-blue) pebble game of program analysis.
We provide an experimental library, which outperforms Intel's library with an ~8.92 GB/s throughput.
Download PDF
Archive view