Algorithms and Implementations

Another direction in our research is at the interface of the theory of DSP algorithms and their efficient implementations. The goal is to use deep understanding of the algorithm space to develop automatic implementation frameworks. The below papers are only a few representatives. See the SPIRAL project for more details and an extensive list of papers on DSP software and hardware.

Papers

• Adam C. Zelinski, Markus Püschel, Smarahara Misra, and James C. Hoe
  Automatic Cost Minimization for Multiplierless Implementations of Discrete Signal Transforms
  Proc. ICASSP 2004

  The computation of linear DSP transforms consists entirely of additions and multiplications by constants, which, in a hardware realization, can be implemented as a network of wired shifts and additions. Thus, a light weight fixed point implementation that approximates an exact transform can be built from only adders. This paper presents an automatic approach for minimizing the number of additions required for a given transform under the constraint of a particular quality measure. We present an evaluation of our approach. For example, one experiment shows that the IMDCT transform within an MP3 decoder can be reduced from 643 additions to 170 additions while maintaining Limited Accuracy as defined by the MP3 ISO standard.

  approxopt.pdf (79 KB)

• Aca Gacic, Markus Püschel, and José Moura
  Automatically Generated High-Performance Code for Discrete Wavelet Transforms
  Proc. ICASSP 2004

  A growing number of performance-critical DSP application use the discrete wavelet transform (DWT), thus prompting the need for highly efficient DWT software implementations. Unfortunately, the rapid evolution of computing platforms and compiler technology makes carefully hand-tuned code obsolete almost as fast as it is written. In this paper we describe our work on the automatic generation of DWT implementations that are tuned to a given platform. Our approach captures the various DWT algorithms in a concise mathematical framework that enables the integration of DWTs into the SPIRAL code generation system. Experiments show the quality of our automatically generated code and provide interesting insights; for example, the fastest code differs between platforms and is usually based on a non-obvious combination of DWT algorithms.

  dwt.pdf (106 KB)

• Yevgen Voronenko and Markus Püschel
  Automatic Generation of Implementations for DSP Transforms on Fused Multiply-Add Architectures
  Proc. ICASSP 2004

  Many modern computer architectures feature fused multiply-add (FMA) instructions, which offer potentially faster performance for numerical applications. For DSP transforms, compilers can only generate FMA code to a very limited extent because optimal use of FMAs requires modifying the chosen algorithm. In this paper we present a framework for automatically generating FMA code for every linear DSP transform, which we implemented as an extension to the SPIRAL code generation system. We show that for many transforms and transform sizes, our generated FMA code matches the best-known hand-derived FMA algorithms in terms of arithmetic cost. Further, we present actual runtime results that show the speed-up obtained by using FMA instructions.

  fma.pdf (95 KB)

• Markus Püschel and José Moura
  Generation and Manipulation of DSP Transform Algorithms
  Proc. 10th Digital Signal Processing Workshop, 2002

  SPIRAL generates automatically high quality implementations for a variety of DSP signal transforms. The generated code is adapted to the machine configuration and architecture. SPIRAL achieves this through an intelligent search in the Cartesian product of the space of algorithms and the space of coding variants. This paper describes the mathematical framework that SPIRAL uses to represent, generate, and manipulate transform algorithms.

• Markus Püschel, Bryan Singer, Manuela Veloso, and José Moura
  Fast Automatic Generation of DSP Algorithms
  Proc. ICCS 2001, Lecture Notes of Computer Science 2073, pp. 97-106

  SPIRAL is a generator of optimized, platform-adapted libraries for digital signal processing algorithms. SPIRAL's strategy translates the implementation task into a search in an expanded space of alternatives. These result from the many degrees of freedom in the DSP algorithm itself and in the various coding choices. This paper describes the framework to represent and generate efficiently these alternatives: the formula generator module in SPIRAL. We also address the search module that works in tandem with the formula generator in a feedback loop to find optimal implementations. These modules are implemented using the computer algebra system GAP/AREP.

  formgen.ps (162 KB)