|
|
|
|
|
|
|||
|
|
|||
Research in Algebraic Signal Processing and Transforms |
||
|
Introduction |
||
| |
||
SPIRALWith the growing complexity and diversity of computer platforms, the design of high-performance software implementations of digital signal processing (DSP) algorithms has become an increasingly more difficult task. When high performance is an issue, the designers have to fine tune software implementations to utilize the specific features of the target platform. This requires expert knowledge in both algorithm development and computer architecture, and the hand-coding of the implementations becomes a tedious and time-consuming task. Furthermore, the ever-changing hardware and compiler technology requires frequent re-implementation, since the platforms are often changed or upgraded. These problems are tackled by what are commonly known as automatic software performance tuning systems, which are automatically adapting software implementations to a wide range of platforms. Because of the complexity of the problem, most performance tuning systems implement only basic functions that are used as building blocks in more complex applications. There is a growing interest in automatic tuning of DSP algorithms since DSP applications typically require high-performance algorithm implementations. Many DSP applications include digital filtering and wavelet-based processing, and the number of new applications is increasing fast. In our work, we develop SPIRAL, a generator of Libraries of tuned software implementations of fast DSP transforms. SPIRAL generates fast code for a number of different transforms, including the discrete Fourier transform, the discrete trigonometric transforms, i.e., the discrete cosine and discrete sine transforms (all their sixteen variants), the Walsh-Hadamard transform, the wavelet transform, as well as other digital signal processing kernels like filtering. SPIRAL is now looking also at reconfigurable hardware (e.g., FPGAs) implementations, as well as joint harwdare/ software implementations, of signal processing algorithms. The work in SPIRAL is featured in a paper in the February 2005 IEEE Proceedings Special Issue on Performance Tuning. Major support for SPIRAL was initially provided by the DARPA ACMP OPAL Initiative through an ARMY research grant. SPIRAL has been supported by an NSF ITR medium size grant as well as several other NSF grants, by a major grant from DARPA under the Discovery and Exploitation of Structure in Algorithms (DESA) Program, and an ONR grant. SPIRAL has been also supported by several industrial grants from INTEL, Mercury among others. INTEL licensed SPIRAL technology. SPIRAL is currently commercialized by SPIRALGEN, a start-up cofunded by Moura and four coleagues that licensed the SPIRAL Technology from CMU. SPIRAL Journal Papers (for additional papers see the SPIRALweb site)
Some of the First SPIRAL Conference Papers (additional papers at the SPIRALweb site)
Some Outdated SPIRAL Presentations
Some of the Early Students (complete list of researchers and students, see SPIRAL)
For additional team information, papers, presentations and information visit the SPIRAL website: http://www.spiral.net/.
|
||
|
|
||
|
|
||
DSP on GraphsWe are interested in developing digital signal processing concepts like the Fourier transform, filtering, spectrum for signals that are indexed by arbitrary graphs. This builds on the algebraic signal processing, part of a previous project, called SMART. SMARTMany algorithms in digital signal processing are based on the use of linear discrete signal transforms. Mathematically, such a transform is a matrix-vector multiplication y=M .x where x is the sampled signal, and M is the transform over some base field K. Crucial for the applicability of a signal transform M is the existence of fast algorithms that allow its computation with O(n\log n) operations (or better) compared to O(n^2) arising from a direct matrix-vector multiplication. The problem of finding these algorithms for different transforms has been a major research topic leading to a vast number of publications in signal processing and mathematics. Probably the most famous example of a signal transform is the discrete Fourier transform (DFT), which is used in harmonic analysis to decompose a signal into its frequency components. Important algorithms for the DFT include the "fast Fourier transform" (FFT) found by Cooley/Tukey in 1965 (originally due to Gauss), Rader's algorithm for prime size (1968), Winograd's algorithms (1980), and several others. Another important class of transforms consists of the 8 different
types of discrete cosine and sine transforms (DCTs and DSTs),
respectively, also called discrete trigonometric transforms Each of these algorithms has been derived through insightful manipulation of the transform matrix entries. The algorithms are highly structured, a property that can be used to write them as sparse factorizations of the transform matrix in a very concise way using mathematical operators. In SMART (see papers below), we present an algebraic approach to the class of the 16 trigonometric transforms in the framework of algebra representation theory. In particular, the work presents the discrete cosine and sine transforms as decomposition matrices of certain regular modules associated to four series of Chebyshev polynomials. SMART uses algebraic methods to derive most of their known fast algorithms. SMART gives insight into the structure and the existence of these algorithms and extends the relationship between signal processing and algebra that is currently mainly restricted to the discrete Fourier transform. SMART has been supported by two grants from NSF, CISE Division, CCR Program. SMART Papers (for additional papers see the SMART web site)
|
||
Home | Research | Publications
& Seminars | Affiliated Researchers | Professional
Activities
Bio Data & Teaching |
Site Index
Electrical & Computer Engineering Home | Carnegie Mellon Home
Last updated 02 April 2004.
