This article, Multidimensional DSP with GPU acceleration, has recently been created via the Articles for creation process. Please check to see if the reviewer has accidentally left this template after accepting the draft and take appropriate action as necessary.
Reviewer tools: Inform author |
Digital signal processing (DSP) is an ubiquitous methodology in scientific and engineering computations. However, practically, to DSP problems are often not only 1-D. For instance, image data are 2-D signals and radar signals are 3-D signals. While the number of dimensions increases, the time and/or storage complexity of processing digital signal grows dramatically. Therefore, solving DSP problems in real-time is extremely difficult in reality.
Modern general purpose graphics processing units (GPGPUs) are considered having excellent throughput on vector operations and numeric manipulations by high degree of parallel computation. While processing digital signals, particularly multidimensional signals, often involves in a series of vector operations on massive amount of independent data samples, GPGPUs are now widely employed to accelerate multidimensional DSP, such as image processing, video codec, radar signal analysis, sonar signal processing, and ultrasound scanning. Conceptually, using GPGPU devices to perform multidimensional DSP is able to dramatically reduce the computation complexity compared with central processing units (CPUs), digital signal processors (DSPs), or other FPGA accelerators.
Motivation
Processing multidimensional signals is a common problem in scientific researches and/or engineering computations. Notwithstanding, with its high degree of time and storage complexity, it is extremely difficult to process multidimensional signals in real-time. In general, the computation complexity of multidimensional DSP grows exponentially with the number of dimensions. Therefore, it is still hard to obtain the computation results with digital signal processors (DSPs). Hence, a better solution of software algorithm or hardware architecture to accelerate multidimensional DSP computations is strongly required.
Existing Approaches
Practically, to accelerate multidimensional DSP, some common approaches have been proposed and developed in the past decades.
Lower Sampling Rate
Using a lower sampling rate can efficiently reduce the number of samples to be processed at one time and thereby decreasing the computation complexity. However, this can lead to the aliasing problem in the sampling theorem and make a poor quality of outputs. In some applications, such as military radars, we are eager to have highly precise and accurate results. In such cases, using a lower sampling rate in multidimensional DSP is not allowable.
Digital Signal Processors (DSPs)
Digital signal processors are designed specifically to process vector operations. They are widely used in DSP computations. However, most digital signal processors are only capable of manipulating two operations in parallel. This kind of designs is sufficient to accelerate audio processing (1-D signals) and image processing (2-D signals). However, with a large amount of data samples in multidimensional signals, this is still not efficient enough to retrieve computation results in real-time.
Adopting Supercomputers
In order to accelerate multidimensional DSP computations, using dedicated supercomputers or cluster computers is required in some situations, e.g., weather forecasting. However, using supercomputers designated to simply perform DSP operations takes considerable cost and energy consumption. It is not suitable for all multidimensional DSP applications.
GPU Acceleration
GPUs are originally designed to accelerate image processing and video rendering. Moreover, since modern GPUs' have good ability to perform numeric computations in parallel with a relatively low cost and better energy efficiency, GPUs are becoming a popular alternative to replace supercomputers performing multidimensional DSP.
GPGPU Computations
Modern GPU designs are mainly based on SIMD computation paradigm. This type of GPU devices are so-called general-purpose GPUs (GPGPUs).
GPGPUs are able to perform an operation on multiple independent data concurrently with their vector or SIMD functional units. With this nature, GPGPUs can be employed as DSP accelerators easily while many DSP problems can be solved by divide-and-conquer algorithms. For example, an M × M matrix multiplication can be processed by M × M concurrent threads on a GPGPU device without any output data dependency. Therefore, theoretically, by means of GPGPU acceleration, we can gain up to M × M speedup compared with a traditional CPU or digital signal processor.
Programming Languages
Examples
Matrix Multiplication
Suppose A and B are two m × m matrices and we would like to compute C = A × B.
To compute each element in C takes m multiplications and (m - 1) additions. Therefore, with a CPU implementation, the time complexity to achieve this computation is Θ(n3).