Authors: Stanković, Radomir 
Astola, Jaakko
Moraga, Claudio
Gajić, Dušan
Title: Constant geometry algorithms for galois field expressions and their implementation on GPUs
Journal: Proceedings of The International Symposium on Multiple-Valued Logic
First page: 79
Last page: 84
Conference: 44th IEEE International Symposium on Multiple-Valued Logic, ISMVL 2014; Bremen; Germany; 19 May 2014 through 21 May 2014
Issue Date: 1-Jan-2014
ISBN: 978-1-479-93534-5
ISSN: 0195-623X
DOI: 10.1109/ISMVL.2014.22
Galois field (GF) expressions are analytical representations of multiple-valued functions. For practical applications it is important to provide fast algorithms for computing coefficients in these expressions. From the FFT-theory point of view, these algorithms are Cooley-Tukey type algorithms based on the Good-Thomas factorization derived from the Kronecker product structure of the GF-transform matrices. These algorithms are good for reducing the number of operations in Central Processing Unit (CPU) implementations. When implemented over Graphics Processing Units (GPUs), the address arithmetic becomes an important factor determining the efficiency of the implementations, due to the differences between the CPU and GPU based architectures and the corresponding programming philosophies. In this paper, we define the constant geometry algorithms for computing the coefficients in GF-expressions by an analogy with the corresponding algorithms in Fourier analysis on finite Abelian groups. We performed an experimental verification of the proposed algorithms compared to the Cooley-Tukey algorithms over two GPU platforms (Nvidia and AMD) and two programming environments (CUDA and OpenCL) with the corresponding CPU implementations. The speedup achieved by constant geometry algorithms increases with the number of variables and, therefore, the constant geometry algorithms are more advantageous in the case of functions with a larger number of variables.
Keywords: Fast algorithms | Galois field expressions | GPU computing | Spectral transforms
Publisher: IEEE

Show full item record


checked on May 28, 2024

Page view(s)

checked on May 9, 2024

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.