Optimization of Number Representations - Signal Processing Systems - page 1292

4.3 Integer Code Generation

The IWL information file generated in the range estimation step includes the scope
of a variable that indicates whether it is global or local, the variable name and
its IWL. In the automatic scaling integer program converter for C, this information is
attached to the symbol table of the floating-point program. The conversion of types
and expression trees is conducted in the integer C code generation stage. The symbol
tables are modified to replace floating-point types with integer types. Not only the
float type but also the float-based types such as pointers to float, float arrays, and
float functions are converted to corresponding integer-based types. The expression
tree conversion that inserts scaling shifts uses the fixed-point arithmetic rules shown
in Table 1 . It is performed from the bottom to the top of a parse tree, and the IWL
information of each tree node is also propagated in the same way. In this step, the
pointer operations that involve different IWL's are also checked.

4.3.1 Shift Optimization

In many programmable DSP's, an implementation that needs no or less scaling
shift operations is not only faster but also requires a smaller code size. Since no
shift operation is needed for addition or assignment of operands having the same
IWL, the number of scaling shifts can be reduced by equalizing the IWL's of
relevant variables. An example implementation with shift reduction is illustrated in
Fig. 6 a . Note that it is only allowed to increase the initial IWL's that are determined
according to Eq. ( 2 ) , thus the equalization can increase the quantization noise level.
Scaling shift reduction requires global optimization because IWL modification of
a variable in an expression can incur additional scaling shifts in other expressions.
Shift optimization also depends on the architecture of a DSP. For example, if a DSP
has a barrel shifter, the number of bits for one scaling shift, unless it is zero, does
not affect the number of execution cycles. However, if it has no barrel shifter and
should conduct the scaling by employing one-bit shift operations, the shift cost is
also affected by the number of bits for one scaling operation. It is also needed for
minimizing the execution time to reduce the number of scaling operations that are
inside of a long loop. Thus, this optimization requires program-profiling results.
The IWL modification that minimizes the overhead for scaling is conducted
as follows. First, the number of shifts for each expression is formulated with
the IWL's of the relevant variables and constants. Second, the cost function that
corresponds to the total overhead of scaling shifts is made based on the results of
the first step, the target DSP architecture, and the program-profiling information.
Finally, the cost function is minimized by modifying the IWL's using the integer
linear programming or the simulated annealing algorithms. Note that shift reduction
using a DSP architecture without a barrel shifter can be modeled as an integer linear
programming problem. The simulated annealing algorithm is a general optimization
method, but the optimization can take much time. Detailed methods for shift
reduction can be found in [ 13 ] .