A New Technique for Algebraic Optimization of Arithmetic Expressions Abstract The rapid advancement and specialization of embedded systems has pushed the compiler designers to tune their optimizations towards a specific domain of applications. Multimedia applications have many large arithmetic expressions that are good candidates for optimization. However existing compiler techniques which are targeted towards general purpose applications are unable to fully optimize these expressions commonly found in multimedia applications. This paper presents algorithms for finding common sub-expressions among a set of arithmetic expressions. These algorithms are based on the algebraic techniques for multi-level logic synthesis. Experimental results show an average of 17.6 % improvement over common sub-expression elimination. 1. Introduction In recent years, the huge demand for high performance and low power solutions for embedded systems has created a need for application specific techniques to optimize these systems. A large number of embedded systems use digital signal processing (DSP) algorithms, e.g. cellular phones and video cameras. These algorithms consist of a large number of computation sequences, e.g Finite Impulse Response filters and Fourier transform. Therefore, these applications have a number of large basic blocks, which have many arithmetic operations. Furthermore DSP algorithms often use exponential and trigonometric functions. These functions are generally evaluated by series such as Taylor series. For example, Sin(x) can be evaluated as: !7!5!3)(753xxxxxSin −+−≈ This creates interesting opportunities for optimization that cannot be done by conventional techniques. Consider the set of expressions in Figure 1a. The subscripts for each term represent the term number. Figure 1a. A set of arithmetic expressions A naïve implementation of these expressions would use 16 multiplications and 4 additions/subtractions. (P1 uses 7 multiplications and 1 addition, P2 uses 5 multiplications and 1 addition and 1 subtraction, and P3 uses 4 multiplications and 1 addition. There are a number of optimizations that are well known in the compiler design community [1]. Common sub-expression elimination, scalar replacement of aggregates, value numbering, constant and copy propagation are applied both locally in basic blocks and globally across the control flow graph. The amount of improvement that results from these optimizations depends on the type of hardware and the type of application. Using an iterative algorithm for common sub-expression elimination on an intermediate representation of theexpressions in Figure 1a,, [1] we get the following optimized set of expressions: Figure 1b. Using common sub-expression elimination These expressions consist of a total of 12 multiplications and 4 additions/subtractions. By using slightly more sophisticated algebraic optimizations, we can obtain the following set of expressions. Figure 1c. Using algebraic techniques These expressions now consist of a total of 7 multiplications and 3 additions/subtractions. Therefore there is a saving of 5 multiplications and 1 addition compared to the previous technique. These common factors are impossible to obtain using the conventional techniques. In this paper, we present a new methodology and algorithms to extract common factors and optimize arithmetic expressions. Our optimizations are based on the algebraic techniques developed for multi-level logic synthesis We show that eliminating common expressions P1 = x3y(1) + x2y2z(2) P2 = 4x(3) + 4yz (4)– xyz(5) P3 = 4xy(6) – x2y(7) d1 = x2 d2 = xy d3 = 4x P1 = d1d2 + d1y2z P2 = d3 + 4yz – d2z P3 = d3y – d1y d1 = (x + yz) d2 = (4 – x) d3 = xy P1 = xd1d3 P2 = 4d1 – zd3 P3 = d2d3in arithmetic expressions is similar to finding common functions in a Boolean network. Decomposition and factoring are two major operations in multi-level logic synthesis. The goals of these operations are to find an equivalent representation of a given Boolean network that is optimal with respect to a cost function usually involving area and delay. These operations identify common sub-expressions among different functions forming the network and create new nodes to simplify the original nodes of the network. Various algebraic techniques [2-4] have been established to solve this problem of optimizing Boolean networks. Unfortunately so far there has not been much work on optimization of arithmetic functions in multi-level. We show that it is possible to extend the techniques used to optimize Boolean functions to handle a set of arithmetic expressions, and generate common sub-expressions that are not possible to obtain using the conventional techniques. The rest of the paper is organized as follows: Section 2 presents the representation of arithmetic expressions and the algorithms involved in extracting and eliminating common sub-expressions. We present some related work on arithmetic expressions in Section 3. Experimental results are presented in Section 4. We conclude and talk about future work in Section 5. 2. Optimization of arithmetic expressions The goal of this section is to show our representation of arithmetic expressions, and present algorithms for the extraction and elimination of common sub-expressions. The set of common sub-expressions can be divided into those that consist of only a single product term and those that consist of multiple product terms. Our algorithm first extracts all possible common sub-expressions and then eliminates multiple term and then single term common sub-expressions. 2.1 Representation of arithmetic expressions Each arithmetic expression is represented by an integer matrix where there is one row for each product term (cube), and one column for each variable in the matrix. Each element (i,j) in the matrix is a non-negative integer that represents the order of the variable j in the product term i. There is an additional field in each row of the matrix for the sign (+/-) of the corresponding product term. For example the polynomial F = x3y – xy2z is represented as shown in Figure 2. 2.2 Definitions We use the same terminology to show the close correlation between the problems of optimizing Boolean networks and arithmetic expressions. A literal is a variable Figure 2. Matrix representation of arithmetic expressions or a constant (e.g. a, b, 2, 3.14, …). A cube is a product of the