Computing Spectral Transforms Used in Digital Logic on the GPU

Dusan Gajic, Radomir S. Stankovic
Dept. of Computer Science, Faculty of Electronic Engineering, University of Nis, Nis, Serbia
Chapter 2 in book "GPU Computing with Applications in Digital Logic", 2012
@article{gajic2012computing,

   title={Computing Spectral Transforms Used in Digital Logic on the GPU},

   author={Gajic, D. and Stankovic, R.S.},

   journal={GPU Computing with Applications in Digital Logic},

   pages={25},

   year={2012}

}

Download Download (PDF)   View View   Source Source   
GPU computing originated in the opening of the graphics processing units (GPUs), which are devices intended to produce computer graphics, for general purpose computations. Since computer graphics is based on matrix operations, GPUs are purposely designed to implement such operations efficiently. Spectral transforms are defined in terms of sets of basis functions, which can be conveniently arranged as columns of certain matrices whose entries could be complex numbers, real numbers, integers, or elements of some finite fields. In this way, spectral transforms are defined by transform matrices and the determining spectra of discrete functions, which are conveniently defined by function vectors, reduces to matrix-vector operations. In many cases, basis functions and due to that also the related transform matrices, express some specific properties enabling us to derive fast computation algorithms by exploiting instruction parallelism. The matrix specification and the parallelism in related algorithms make computing the spectral transform a task well suited for implementation on GPUs. A direct mapping of existing fast algorithms, however, does not lead to implementations that take full advantage of all GPU features regarding computational power and memory bandwidth. Therefore, a suitable reformulation of the existing algorithms is necessary. Most of the related work is devoted to the implementation of the Fast Fourier Transform (FFT), that is an algorithm for efficient computation of the Discrete Fourier Transform (DFT), due to its numerous applications. Since computing of DFT involves complex number arithmetic, which in programming implementations doubles the computing requirements (for the real and the imaginary part), the advantages of using GPUs are impressive. In this chapter, we point out that a considerable speedup in computing can be achieved even in the case of integer valued transforms or Boolean valued transforms such as transforms that are used in digital logic for processing logic (Boolean) functions. The chapter discusses the implementation of the Walsh, the Reed-Muller, and the arithmetic transforms, as examples of the Kronecker product representable transforms, and the Haar transform, as an example of the layered-Kronecker transforms. In the reformulation of the algorithms to make them well suited for computation on GPUs, special attention is paid to the organization of the computations, impact of the integer and Boolean arithmetic, different structure of fast algorithms, memory transfers reduction, and related issues. Furthermore, the chapter presents a discussion of the implementation of two kinds of FFT-like algorithms, the Cooley-Tukey algorithms and the so-called algorithms with constant geometry. Performances of GPU implementations are compared with the classical C/C++ implementations on the Central Processing Unit (CPU). Experiments show that, even though the spectral transforms considered involve arithmetic over integers (in the case of the Walsh, the arithmetic, and the Haar transforms) and Boolean values in the case of the Reed-Muller transform, significant speedups can be achieved by implementing the algorithms in OpenCL and performing them on the GPU. As an illustration of the possible applications, the procedures developed for the Walsh transform are used to compute the correlation and autocorrelation of discrete functions in terms of Boolean variables viewed as functions on finite dyadic groups.
VN:F [1.9.22_1171]
Rating: 5.0/5 (1 vote cast)
Computing Spectral Transforms Used in Digital Logic on the GPU, 5.0 out of 5 based on 1 rating

You must be logged in to post a comment.

* * *

* * *

* * *

Free GPU computing nodes at hgpu.org

Registered users can now run their OpenCL application at hgpu.org. We provide 1 minute of computer time per each run on two nodes with two AMD and one nVidia graphics processing units, correspondingly. There are no restrictions on the number of starts.

The platforms are

Node 1
  • GPU device 0: AMD/ATI Radeon HD 5870 2GB, 850MHz
  • GPU device 1: AMD/ATI Radeon HD 6970 2GB, 880MHz
  • CPU: AMD Phenom II X6 @ 2.8GHz 1055T
  • RAM: 12GB
  • OS: OpenSUSE 11.4
  • SDK: AMD APP SDK 2.8
Node 2
  • GPU device 0: AMD/ATI Radeon HD 7970 3GB, 1000MHz
  • GPU device 1: nVidia GeForce GTX 560 Ti 2GB, 822MHz
  • CPU: Intel Core i7-2600 @ 3.4GHz
  • RAM: 16GB
  • OS: OpenSUSE 12.2
  • SDK: nVidia CUDA Toolkit 5.0.35, AMD APP SDK 2.8

Completed OpenCL project should be uploaded via User dashboard (see instructions and example there), compilation and execution terminal output logs will be provided to the user.

The information send to hgpu.org will be treated according to our Privacy Policy

HGPU group © 2010-2014 hgpu.org

All rights belong to the respective authors

Contact us:

contact@hgpu.org