Study on DSP algorithm implementation techniques and memory access reduction for DSP algorithm implementation on Digital Signal Processor.

摘要

Digital Signal Processor (DSP) has been developed rapidly in the past several decades. It was originally designed for digital signal processing. DSP algorithms are developed and widely used on DSP. They are a class of algorithms designed to run on digital signal processors for specific purpose. With the rapid development of digital signal processor technology, how to design computationally efficient DSP algorithms based on existing DSP architectures has become the major research focus. In this dissertation, we study methods to design and implement DSP algorithms, we also study methods to reduce memory access to lower power consumption and decrease execution time, respectively.;As one of important DSP algorithms, Fast Fourier Transform (FFT) is used to perform signal transformation between time and frequency domain. We study several existing implementation techniques together with proposed recursive programming techniques on FFT. Those existing techniques are TFBBGM (Twiddle Factor Based Butterfly-Grouping Method) [21], TFRM (Twiddle Factor Reduction Method) [22] and further expansion, which are all proposed by Dr. Yiyan Tang. We combine these techniques in different ways and applied to regular DIF/DIT FFT algorithms to get 20 FFT codes. Extensive experiment was performed with these 20 FFT codes on major DSPs and ARM processor in industry. This comparative study constitutes the first attempt to evaluate the real performance of different FFT approaches.;As another one of important DSP algorithms, Discrete Cosine Transform (DCT) has a unique property of energy compaction. Owing to this superior property, DCT has been adopted as the most appropriate transform among various image signal processing applications. However, memory access in DSPs has been known to be expensive because it has long instruction latency and is extremely power consuming. Regular fast DCT algorithms together with fast DCT pruning algorithms involve a large number of memory accesses. Since DCT pruning is proved to be faster than DCT by keeping a subset of DCT coefficients. We propose a novel memory access reduction to the fast DCT Pruning algorithm, and implement the method together with conventional approach on DSP. As a result, we achieve average of 40% memory access reduction, 48.6% clock cycle reduction and 32.6% memory space saving for weighting factors to compute Pruning FCT on DSP comparing to the conventional implementation. We further extend and apply the memory access reduction method to the vector-radix two-dimensional DCT Pruning, which is an important algorithm used in digital signal processing systems for image processing.