View source for Operation Reduction for Low Power

'''Operation Reduction for Low Power''' is an ASIC [[Program transformation]] technique used to reduce the power consumed by a specific application. A program transformation is any operation that changes the computational structure such as nature and type of computational models, their interconnections, sequencing of operations keeping the input output behavior intact. We basically use Operation reduction to reduce the number of operations to be done to perform a task which reduces the hardware required and in turn power consumption. For example, in a given Application specific [[Engineering:Integrated circuit|IC]] reducing the number of independent additions required automatically reduces the adders required and also the power consumed.

== Operation Substitution ==
Operation Substitution is one of the operation reduction techniques where certain costly operations are substituted by relatively cheaper operations which reduce power consumption. Some typical examples of operation substitution techniques are given as follows:
#'''Multiplication by Adds/Subtracts''': The multiplication of two numbers if costly compared to addition of two numbers therefore substituting it with addition is profitable. For example, to calculate y = x<sup>2</sup> + Ax + B we can calculate x<sup>2</sup>, Ax, and add both of them to B which has 2 multiplications, 3 additions or we can convert it into y = x(x+A) + B where we can calculate x+A multiply it with x and add B where we have 1 multiplication and 2 additions, both approaches have same critical path length but 2nd one has lesser multiplications which saves power.
#'''Computation of Sine/cosine/tan''': Computing trigonometric functions might also turn out to be quite costly where as substituting them with lesser order Taylor expansion makes them less power consuming but we may lose on approximation grounds which is a trade-off one should keep in mind.
#'''Multiply-add by MAC''': [[Multiply–accumulate operation]] is a common step that computes the product of two numbers and adds that product to an accumulator. The hardware used for this purpose is called multiplier–accumulator (MAC). Using MAC's also decrease the power consumed. Basically a MAC does multiplication and addition in one unit.<math>\ a \leftarrow a + ( b \times c )</math>
#'''Reducing Memory Access''': Changing the structure of the program by replacing the operations which require frequent memory access with those need less memory access is also profitable as memory access is a costly operation.

== Butterfly Example ==
A popular example of Operation substitution is Butterfly example. In this example we need to compute two values y<sub>r</sub> =  a<sub>r</sub> * x<sub>r</sub> - a<sub>i</sub> * x<sub>i</sub>, y<sub>i</sub> =  a<sub>i</sub> * x<sub>r</sub> + a<sub>r</sub> * x<sub>i</sub> which can be done sequentially computing the terms as shown in the expressions. But using operation substitution we can compute them using expressions, y<sub>r</sub> = a<sub>r</sub>* (x<sub>i</sub>+x<sub>r</sub>) - x<sub>i</sub> * (a<sub>i</sub>+a<sub>r</sub>), y<sub>i</sub> = a<sub>r</sub>* (x<sub>i</sub>+x<sub>r</sub>) + x<sub>r</sub> * (a<sub>i</sub>-a<sub>r</sub>) where the term (x<sub>i</sub>+x<sub>r</sub>) once computed can be used by both the computations from this we can easily workout that operations changed from number of operations changed from 4 multiplications to 3 and 2 Add/sub to 3. The critical path in the first method was of length 2 where as in the latter it is 3. So again this is a trade-off between delay and power.

== Switching Activity Reduction ==
Based on the frequency of input changing we can model the program so that less activity switching happens i.e. if certain inputs are less frequently changing then they should be made operating in single module so that the particular module is relatively passive compared to others. A+B+C+D can be computed as (A+B)+C+D or (A+B)+(C+D) the first one feeds C,D to 2 separate adders but if they are relatively slow changing then feeding them to same adder is more profitable.

== Power Aware Scheduling and Binding==
Any synthesis has 3 parts Allocation(number and type of resources), Scheduling(operation scheduling), Binding(building the circuit). We can schedule the operations in a particular order based which value in the program activates how many modules. We always want the operations requiring more operations to be completed before hand to be scheduled later.

== Exploiting Mutual Exclusion ==
Consider the following code snippet:<br />
if(C>0){<br />
:A = A*C
}<br />
Let us assume that the profiling has shown that most likely the value of C is 2. Therefore, as C and A are independent and mutually exclusive we can modify the code to be<br />
if (c = = 2) A = A << 1<br />
else If (C >0){<br />
:A = A * C;
}<br />
Here the multiplication is replaced by shifting operation which is triggered in most of the cases and is far cheaper than multiplication.

== References ==
#Chandrakasan, A.P. et al., Optimizing power using transformations, IEEE TCAD  Vol  14,  Jan. 1995, pp.&nbsp;12 – 31
#Low power design Lec-4 (https://www.youtube.com/watch?v=J56ExZ9uGkg)

[[Category:Program transformation]]
[[Category:Software optimization]]

{{Sourceattribution|Operation Reduction for Low Power|1}}