Optimization theory

Introduction to code optimization

Most practical DSP applications have a clock-cycle and/or memory budget. Initial implementations typically don't meet these budgets;therefore, the code must be optimized. Code development usually follows six steps:

• Develop algorithm on paper
• Simulate in MATLAB
• Develop and simulate more efficient implementations
• Implement algorithm in C
• Use library routines when available
• Use optimizing compiler
• Manually write assembly routines for key routines

Develop algorithm on paper

The algorithm to be implemented should first be designed on paper. In addition to equations describing the algorithm, its design shouldinclude inputs and outputs of each routine and a flow chart of the operation of the complete program. Never design an algorithm or a program at a computer. While it may be possible to implement some basic algorithms and programs this way, compilers cannot overcome any designflaws that are likely to be introduced.

Simulate in matlab

Before any C code is written, the algorithm should be developed and simulated in MATLAB since problems with the algorithm design can befound more easily. This is done by applying the algorithm to test vectors and inspecting and/or plotting the results. Once thealgorithm is completely defined, C implementation can begin. Recall that in each of the previous labs a MATLAB simulation step was givenbefore assembly implementation.

Develop and simulate more efficient implementations

An efficient algorithm used as few multiplications and additions as possible. Applying DSP theory to "simplify" the algorithm is a commonway of doing this. The autocorrelation function is a simple example: a simple-minded way of implementing this is tocompute sums for each lag, but careful inspection of the autocorrelation function reveals that it is actually a function of the absolute value of the lag. Therefore each value at a negative lag is identical to the value at the correspondingpositive lag. Approximately half the apparent multiplications and additions aretherefore required. If the entire autocorrelation sequence is needed, the autocorrelation can be optimized even furtherif it is treated as a convolution of two sequences. An FFT and an inverse FFT can then be used to compute the autocorrelation.

C implementation

After the algorithm has been designed and optimized, an initial implentation in C is done. Tips on writing code with efficiency inmind can be found here . It is important, however, to get a working implementation ofthe algorithm in a reasonable amount of time as some optimizations cannot be anticipated by the programmer.Some of these coding techniques in the URL reference can be applied later on when it is clear which routines need the most optimization.This implementation can serve as a reference implementation to compare the correctness and speed of optimized versions.