Raghav Bhaskar, Pradeep Dubey, Vijay Kumar, Atri Rudra and Animesh Sharma

Efficient Galois Field Arithmetic on SIMD Architectures

Abstract : In this work we proposed techniques to utilize the data parallelism capabilities of a SIMD architecture in computations involving finite field arithmetic. Finite field arithmetic finds wide use in engineering applications, involving error-correcting code and cryptography. Often these applications involve extensive arithmetic on small (8-bit) numbers, and straightforward implementation may highly under-utilize the wide-word capabilities of a SIMD processor. Prior to our work, there was only a limited, application specific implementations of finite field based applications targeting SIMD architectures. In this work we present techniques and an algorithm which, given the specification of the computation, produce an efficient SIMD implementation. To evaluate the quality of the output of our algorithm, we applied it to two applications that use finite field arithmetic: AES block cipher and Reed-Solomon error-correcting codes, We got significant performance improvements in both the applications. Our algorithm uses the technique of bit-slicing and its generalization data-slicing to fully explore the potential of SIMD instructions. The implementations require minimal architectural support from any wide-path SIMD processor: parallel table lookup, bitwise EXOR/AND and LOAD/STORE operations. Further, in the case of bit-slicing only the last four instructions are required. This has the advantage of portability of our implementations across wider range of SIMD architectures.