NDLI: Constant Geometry Algorithms for Galois Field Expressions and Their Implementation on GPUs

Content Provider	IEEE Xplore Digital Library
Author	Stankovic, R.S. Astola, J. Moraga, C. Gajic, D.
Copyright Year	2014
Description	Author affiliation: Inst. of Signal Process., Tampere Univ. of Technol., Tampere, Finland (Astola, J.) \|\| Fac. of Electron. Eng., Dept. of Comput. Sci., Univ. of Nis, Nis, Serbia (Stankovic, R.S.; Gajic, D.) \|\| Eur. Center for Soft Comput., Mieres, Spain (Moraga, C.)
Abstract	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.
Starting Page	79
Ending Page	84
File Size	211957
Page Count	6
File Format	PDF
ISBN	9781479935352
ISSN	0195623X
DOI	10.1109/ISMVL.2014.22
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2014-05-19
Publisher Place	Germany
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Geometry Graphics processing units Signal processing algorithms Instruction sets Transforms Registers Vectors Spectral transforms Galois field expressions Fast algorithms GPU computing
Content Type	Text
Resource Type	Article
Subject	Mathematics Computer Science

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

The Impact of Address Arithmetic on the GPU Implementation of Fast Algorithms for the Vilenkin-Chrestenson Transform

Optimized strategies for mapping three-dimensional FFTs onto CUDA GPUs

Fast Implementation of General Matrix-Vector Multiplication (GEMV) on Kepler GPUs

A Parallel Maximum Subarray Algorithm on GPUs

Parallel implementation of Aggressive PNN method for devices with GPUs

SPLG: A Tuned Signal Processing Library for GPU Architectures

Fast implementation of DGEMM on Fermi GPU

Double precision stencil computations on Kepler GPUs

Efficient Pattern-Based Time Series Classification on GPU

Constant Geometry Algorithms for Galois Field Expressions and Their Implementation on GPUs

Similar Documents

The Impact of Address Arithmetic on the GPU Implementation of Fast Algorithms for the Vilenkin-Chrestenson Transform

Optimized strategies for mapping three-dimensional FFTs onto CUDA GPUs

Fast Implementation of General Matrix-Vector Multiplication (GEMV) on Kepler GPUs

A Parallel Maximum Subarray Algorithm on GPUs

Parallel implementation of Aggressive PNN method for devices with GPUs

SPLG: A Tuned Signal Processing Library for GPU Architectures

Fast implementation of DGEMM on Fermi GPU

Double precision stencil computations on Kepler GPUs

Efficient Pattern-Based Time Series Classification on GPU

Constant Geometry Algorithms for Galois Field Expressions and Their Implementation on GPUs