Computing with Fixed Point Numeric Representations David Buehler University of Idaho Computer Science David M Buehler UI ECE Colloquium 11 9 2006 1 Motivation What my research is about Why Perform calculations that are often performed using floating point numeric representations using only integers Floating point is expensive Floating point is frequently not required it is just easy and fixed point is hard So what should we do Make fixed point as easy as floating point David M Buehler UI ECE Colloquium 11 9 2006 2 Outline Computing with real values commonalities between fixed and floating point How fixed point differs from floating point How to implement a calculation using the fixedpoint numeric representation SIFOpt a tool for designing fixed point numeric representations David M Buehler UI ECE Colloquium 11 9 2006 3 Computing with Real Values Many calculations that we want to perform with computers require values from the mathematical field of reals which mathematicians denote by Examples 3 795 0 000337 1 234 1022 0 625 Computers naturally represent integer values to represent real values we use an alternate representation floating point representation fixed point representation David M Buehler UI ECE Colloquium 11 9 2006 4 Computing with Real Values Floating point and fixed point representations both represent real values by associating a scaling factor with an integer value The scaling factor possibly moves the radix point from the right hand edge of the integer value to some other location In a binary computer the scaling factor will be a power of 2 only need to know the exponent David M Buehler UI ECE Colloquium 11 9 2006 5 Integer Scaling Factor Pairs Value Represented Integer Scaling Factor 0 625 5 2 3 20 34765625 5209 2 8 3 0 325 325 10 20 35 2035 10 2 David M Buehler UI ECE Colloquium 11 9 2006 6 Computing with Real Values So real values are modeled by integer scaling factor exponent pairs 0 325 325 10 3 325 3 20 35 2035 10 2 2035 2 304 1 456 4 100 4 Resembles IEEE 754 mantissa exponent Mathematical operations get mapped down to integer mathematical operations David M Buehler UI ECE Colloquium 11 9 2006 7 Addition of Real Values The addition has to be mapped into integer operations integer addition on integral values 1 25 20 6 125 2 2060 2 125 2060 2 2185 2 21 85 David M Buehler UI ECE Colloquium 11 9 2006 8 Addition of Real Values The scaling factors must be made the same before addition is performed This equalized scaling factor will be the scaling factor of the result Shifting the value one digit changes the scaling factor by one 1 25 20 6 1250 3 206 1 1250 3 20600 3 1250 206000 3 218500 3 21 85 David M Buehler UI ECE Colloquium 11 9 2006 9 Multiplication of Real Values Again multiplications get mapped into integer operations The scaling factor result is the product of the two scaling factors which means we sum the exponents 1 25 20 6 125 2 206 1 125 206 2 1 25750 3 25 75 David M Buehler UI ECE Colloquium 11 9 2006 10 Issues with word size mantissa size Addition Every addition has the potential to carry out Assume we have a 4 digit word size 0 7432 0 6067 7432 4 6067 4 7432 6067 4 13499 4 1349 3 1 349 David M Buehler 0 7432 0 6067 7432 4 6067 4 743 3 606 3 743 606 3 1349 3 1 349 UI ECE Colloquium 11 9 2006 11 Issues with word size mantissa size Multiplication Every multiplication doubles the number of significant bits In a real computing environment this growth quickly becomes unacceptable and we will have to rescale values Floating point search for the highest set bit and rescale Fixed point decide in advance what bits to keep David M Buehler UI ECE Colloquium 11 9 2006 12 Differences between Fixed Point and Floating Point The difference between fixed point and floatingpoint representations is the data available and computations performed at run time Floating point floating point values carry both the integer and scaling factor values around at run time Scaling factors and alignment and rescaling shifts must be computed at run time Fixed point fixed point values carry just the integer value part of the calculation around at run time Scaling factors and alignment and rescaling shifts are predetermined and do not change at run time David M Buehler UI ECE Colloquium 11 9 2006 13 Advantages of Floating Point Disadvantages of Fixed Point Direct mapping of run time values to real numbers Flexibility Easy to write program code The calculation implementation doesn t care about the range of input values it will dynamically adjust to fit the range of values provided The program code writer doesn t have to worry about scaling factors or shifting for alignment or rescaling because they are handled dynamically at run time Minimizes relative error David M Buehler UI ECE Colloquium 11 9 2006 14 Advantages of Fixed Point Disadvantages of Floating Point Simplicity of run time inexpensive All operations are integer operations All operations are fixed runtime behavior does not change depending on the scaling factors of the input data Controls absolute error and the absolute error may be predictable David M Buehler UI ECE Colloquium 11 9 2006 15 Where Fixed Point is Appropriate When the input values to a calculation are well characterized and do not change In particular when the values are integer values with constant scaling factors When the overhead costs of floating point are prohibitive Floating point can be expensive Run time computations software floating point Hardware cost and power consumption hardware floatingpoint David M Buehler UI ECE Colloquium 11 9 2006 16 Fixed point is perfect for embedded systems The input values to calculations are well characterized and do not change Input values come from instruments that are part of the system The data representations output by the instruments are know at design time The overhead costs of floating point are prohibitive The incremental costs of floating point processors add up quickly in mass produced products cell phones music players Power consumption is important for many embedded systems deep space probes David M Buehler UI ECE Colloquium 11 9 2006 17 Fixed point implementations of calculations are still hard to design Good software tools to help design a fixed point implementation of a calculation are not available There are good tools to analyze a fixed point implementation MATLab fixed point toolbox There are tools to take a floating point implementation of a calculation and a characteristic dataset and generate a fixed