# Development of a specific hardware architecture for a particular algorithm

How does a technical and theoretical study of a project of implementing an algorithm on a specific hardware architecture? Function example:

%Expresion 1:
y1 = exp (- (const1 + x) ^ 2 / ((conts2 ^ 2)),
y2 = y1 * const3


Where x is the input variable, y2 is the output and const1, const3 const2 and are constant. I need to determine the error you get in terms of architecture that decides to develop, for example it suppose that is not the same architecture with 11 bits for the exponent and 52 bits for mantissa. This is the concept of error I handle:

Relative Error = (Real Data - Architecture Data) / (Real Data) * 100


I consider as 'Real Data' the ouput of my algorithm I get from Matlab (Matlab use double precission float point, IEEE 754, 52 bits to mantisa, 11 bits for exponent, one bit fo sign ) with the expression 1 and I consider as 'Architecture Data' the ouput of my algorithm running in an particular architecture (For instance a architecture that uses 12 bits for mantisa, 5 bits for exponent and 1 bit for sign)

EDIT: NOTE: The kind of algorithm I am refering to are all those which use matemathical functions that can be descompose in terms of addition, multiplication, subtrations and division.

Thank you!

-

You have several issues to consider. First, your output format allows very many fewer output values than the double standard. If your exponent is 2-based, your output will be of the form $\pm m*2^e$ where m has 2048 values available and e has 32 values (maybe they range from -15 to +16). The restricted range of e means that you will underflow/overflow quite often. If you are within range, you will still have an error as large as one part in 4096 assuming your calculation is perfect and the only error is representing the output value.

A second issue is precision of the input and error propagation. If your input values are represented in the same format, they will be in error by up to 1 part in 4096 for the same reason. Then when you calculate $f(x)=c_3 \exp {\frac{-(c_1+x)^2}{c_2}}$ (where I absorbed the squaring of $c_2$ into its definition) the error will propagate. You can assess this by evaluating $\frac{\text{d}\ln f(x)}{\text{d}x}=\frac{\text{d}\ln (c_3 \exp {\frac{-(c_1+x)^2}{c_2}})}{\text{d}x}$ to get the fractional error in $f(x)$ depending on the error in $x$

All this assumes your calculation is perfect and the only problem is the accuracy of representing the data. If not, you also need to assess the error that is inherent in the computation.

-
How can I be sure that my "calculation is perfect" ( I´m refering to the last paragraph)? (Direct responses a based on information contained in any link are much appreciated). Thank you! – Peterstone Dec 14 '10 at 18:47
@Peterstone: You can do an error analysis of your algorithm. Say, for example, that you evaluate the exponential by summing the Taylor series (not the best way). If you cannot represent a number greater than 2^16, you cannot do exp of much over 11. The terms are x^n/n!, which we can estimate as (11e)^n/n^n. This gets less than 16 at n=27, which is a relative error of less than one part in 2^12. Generally, if you carry lots of digits in the internal calculation and only reduce to your output format at the end, you will be OK, but if the internals are short you need to be careful. – Ross Millikan Dec 14 '10 at 19:03

I specially recomend you reading What Every Computer Scientist Should Know About Floating-Point Arithmetic by David Goldberg. It should illuminate a lot of issues regarding floating-point computations Errors.

This paper is a tutorial on those aspects of floating-point arithmetic (floating-point hereafter) that have a direct connection to systems building. It consists of three loosely connected parts. The first section, Rounding Error, discusses the implications of using different rounding strategies for the basic operations of addition, subtraction, multiplication and division. It also contains background information on the two methods of measuring rounding error, ulps and relative error. The second part discusses the IEEE floating-point standard, which is becoming rapidly accepted by commercial hardware manufacturers. Included in the IEEE standard is the rounding method for basic operations. The discussion of the standard draws on the material in the section Rounding Error. The third part discusses the connections between floating-point and the design of various aspects of computer systems.

I specially recomend you to design your algorithm according The IEEE 754 rounding methods. I also recomend you to read the third part because it discussed the implications of floating point arithmetic on the design of computer systems.

-