ISA Support for Fingerprinting and Erasure Codes

Using small, pre-computed tables is a well-known technique for improving the performance of expensive computations with small operands. However, as the performance gap between CPU and memory continues to increase, table lookup in main memory may no longer be beneficial. Instead of doing table lookups in memory, this paper proposes table lookup instruction support to accelerate Rabin fingerprinting and Reed-Solomon erasure coding over Galois fields. Both are core computations in emerging main-stream systems such as bandwidth optimized protocol engines, capacity optimized storage systems, and content-distribution networks. We show that the proposed instructions are both beneficial and easy to implement. A simple table lookup instruction that addresses four 256-entry tables in parallel can speed up Rabin fingerprinting and anchoring by a factor of 2.6 and Reed-Solomon coding by a factor of 1.5.