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.
Versions