Efficient Computation of Galois Field Expressions on Hybrid CPU-GPU Platforms
Milos M. Radmanovic, Dusan B. Gajic and Radomir S. Stankovic
This paper proposes an efficient method for the computation of Galois field (GF) expressions for multiple-valued logic functions. The algorithm is based on the partitioning of the input function vector and uses both CPUs (central processing units) and GPUs (graphics processing units) for performing the computations in parallel. After the first step of the fast Fourier transform (FFT)-like algorithm is performed on the CPU, the function vector is divided into disjoint subvectors that are further processed in parallel on the CPU and GPU. The proposed computational method reduces the time needed for computing the coefficients in the GF-expressions and, in this way, might extend the possibilities for their practical application. The experimental comparison of the proposed solution and previously used methods for computing GF-expressions for ternary and quaternary functions, confirms the validity of the method.
Keywords: Multiple-valued logic, spectral methods, fast Fourier transform, Galois field expressions, parallel algorithms, GPU computing.