Configuring floating point operations in a programmable device

• US 8,650,231 B1
• Filed: 11/25/2009
• Issued: 02/11/2014
• Est. Priority Date: 01/22/2007
• Status: Active Grant

• Current Assignee: Altera Corporation (Intel Corporation)
• Original Assignee: Altera Corporation (Intel Corporation)
• Inventors: Langhammer, Martin
• Primary Examiner(s): Tsai, Henry
• Assistant Examiner(s): Phan, Dean
• Application Number:
  US12/625,800
• Time in Patent Office: 1,539 Days
• Field of Search: 708/204
• US Class Current: 708/204
• CPC Class Codes: G06F 2207/3832 Less usual number representations
• CPC Class Codes: G06F 7/483 Computations with numbers represented by a non-linear combination of denominational numbers, e.g. rational numbers, logarithmic number system or floating-point numbers G06F7/4806, G06F7/4824, G06F7/49, G06F7/491, G06F7/544 take precedence
• CPC Class Codes: G06F 7/485 Adding; Subtracting G06F7/4833, G06F7/4836 take precedence
• CPC Class Codes: G06F 7/4876 Multiplying
• CPC Class Codes: H03M 7/02 Conversion to or from weighted codes, i.e. the weight given to a digit depending on the position of the digit within the block or code word

Abstract

A programmable device is programmed to perform arithmetic operations in an internal format that, unlike known standard formats that store numbers in normalized form and require normalization after each computational step, stores numbers in unnormalized form and does not require normalization after each step. Numbers are converted into unnormalized form at the beginning of an operation and converted back to normalized form at the end of the operation. If necessary to avoid data loss, a number may be normalized after an intermediate step. To conserve resources, rather than configuring the every intermediate operation to have the same mantissa size, in the internal format the mantissa size may start out smaller and grow after each operation.

Claims

1. A method of configuring a programmable device to perform floating point operations on input values formatted in accordance with an input standard requiring a first mantissa size and a first exponent size, said method comprising:

configuring logic of said programmable device to reformat said input values to have an initial mantissa size different from said first mantissa size;

configuring logic of said programmable device to perform a tree of successive operations to compute a final result, wherein;

each respective operation in a first level of said tree of successive operations has a first number of said reformatted input values as inputs and provides a respective first intermediate result having a mantissa size increased by at least one bit left of its binal point as compared to said initial mantissa size;

each operation in a respective successive level of said tree of successive operations after said first level of said tree of successive operations, other than a final level, has said first number of inputs and provides a respective intermediate result and said final level provides said final result, and

each of said respective intermediate results and said final result is unnormalized and has a mantissa size increased by at least one bit left of its binal point as compared to an intermediate result on an immediately preceding level; and

configuring logic of said programmable device to reformat said final result in accordance with an output standard.

2. The method of claim 1 wherein:

said output standard is said input standard; and

said configuring logic of said programmable device to reformat said final result comprises configuring said logic of said programmable device to reformat said final result in accordance with said input standard to said first mantissa size.

3. The method of claim 1 wherein each of said input values is in signed number format.

4. The method of claim 1 wherein each of said input values is in signed magnitude format.

5. The method of claim 1 wherein:

said first number is m; and

said at least one bit at a level n of said tree equals ceil(log₂(mⁿ)−

ceil(log₂(m^n-1).

6. The method of claim 1 wherein:

said mantissa size of said final result is increased by a second number of bits left of its binal point as compared to said initial mantissa size; and

said second number of bits is equal to ceil(log₂M) where M is a total number of inputs entering said tree.

7. The method of claim 1 wherein:

at least one of said first intermediate result, said respective intermediate results and said final result has a mantissa size increased by one bit right of its binal point 5 as compared to said initial mantissa size.

8. The method of claim 7 wherein:

said first intermediate result has a mantissa size increased by one bit right of its binal point as compared to said initial mantissa size; and

each of said respective intermediate results and said final result has a mantissa size increased by one bit right of its binal point as compared to a previous intermediate result.

9. The method of claim 7 wherein, whenever addition of a bit left of the binal point of a result of one of said operations results in the mantissa size of the result of that one of said operations exceeding the initial mantissa size to the left of the binal point by an integer multiple of a predetermined number of bits, and no previous one of said operations has resulted in the mantissa size exceeding the initial mantissa size to the left of the binal point by that integer multiple of the predetermined number of bits, the result of that one of said operations has its mantissa size increased by one bit right of its binal point as compared to an immediately preceding intermediate result.

10. A programmable integrated circuit device configured to perform floating point operations on values formatted in accordance with an input standard requiring a first mantissa size and a first exponent size, said configured programmable integrated circuit device comprising:

logic circuitry configured to reformat said input values to have an initial mantissa size different from said first mantissa size;

logic circuitry configured to perform a tree of successive operations to compute a final result, wherein;

each respective operation in a first level of said tree of successive operations has a first number of said reformatted input values as inputs and provides a respective first intermediate result having a mantissa size increased by at least one bit left of its binal point as compared to said initial mantissa size;

each operation in a respective successive level of said tree of successive operations after said first level of said tree of successive operations, other than a final level, has said first number of inputs and provides a respective intermediate result and said final level provides said final result, and

each of said respective intermediate results and said final result is unnormalized and has a mantissa size increased by at least one bit left of its binal point as compared to an intermediate result on an immediately preceding level; and

logic circuitry configured to reformat said final result in accordance with said standard to said first mantissa size configuring logic of said programmable device to reformat said final result in accordance with an output standard.

11. The configured programmable integrated circuit device of claim 10 wherein:

said output standard is said input standard; and

said logic circuitry configured to reformat said final result comprises logic configured to reformat said final result in accordance with said input standard to said first mantissa size.

12. The configured programmable integrated circuit device of claim 10 wherein:

said first number is m; and

said at least one bit at a level n of said tree equals ceil(log₂(mⁿ)−

ceil(log₂(m^n-1).

13. The configured programmable integrated circuit device of claim 10 wherein:

said mantissa size of said final result is increased by a second number of bits left of its binal point as compared to said initial mantissa size; and

said second number of bits is equal to ceil(log₂M) where M is a total number of inputs entering said tree.

14. The configured programmable integrated circuit device of claim 10 wherein said logic circuitry is configured to increase the mantissa size of at least one of said first intermediate result, said respective intermediate results and said final result by at least one bit right of its binal point as compared to said initial mantissa size.

15. The configured programmable integrated circuit device of claim 14 wherein:

said first intermediate result has a mantissa size increased by at least one bit right of its binal point as compared to said initial mantissa size; and

each of said respective intermediate results and said final result has a mantissa size increased by one bit right of its binal point as compared to an immediately preceding intermediate result.

16. The configured programmable integrated circuit device of claim 14 wherein, whenever addition of a bit left of the binal point of a result of one of said operations results in the mantissa size of the result of that one of said operations exceeding the initial mantissa size to the left of the binal point by an integer multiple of a predetermined number of bits, and no previous one of said operations has resulted in the mantissa size exceeding the initial mantissa size to the left of the binal point by that integer multiple of the predetermined number of bits, the result of that one of said operations has its mantissa size increased by one bit right of its binal point as compared to an immediately preceding intermediate result.

17. A non-transistory machine-readable data storage medium encoded with machine-executable instructions for configuring a programmable device to execute a method of performing floating point operations on values formatted in accordance with an input standard requiring a first mantissa size and a first exponent size, said instructions comprising:

instructions to configure logic of said programmable device to reformat said input values to have an initial mantissa size different from said first mantissa size;

instructions to configure logic of said programmable device to perform a tree of successive operations to compute a final result, wherein;

each respective operation in a first level of said tree of successive operations has a first number of said reformatted input values as inputs and provides a respective first intermediate result having a mantissa size increased by at least one bit left of its binal point as compared to said initial mantissa size;

each operation in a respective successive level of said tree of successive operations after said first level of said tree of successive operations, other than a final level, has said number of inputs and provides a respective intermediate result and said final level provides said final result, and

each of said respective intermediate results and said final result is unnormalized and has a mantissa size increased by at least one bit left of its binal point as compared to an intermediate result on an immediately preceding level; and

instructions to configure logic of said programmable device to reformat said final result in accordance with an output standard.

18. The non-transistory machine-readable data storage medium of claim 17 wherein:

said output standard is said input standard; and

instructions to configure logic of said programmable device to reformat said final result comprise instructions to configure said logic of said programmable device to reformat said final result in accordance with said input standard to said first mantissa size.

19. The non-transistory machine-readable data storage medium of claim 17 wherein:

said first number is m; and

said at least one bit at a level n of said tree equals ceil(log₂(mⁿ)−

ceil(log₂(m^n-1).

20. The non-transistory machine-readable data storage medium of claim 17 wherein:

said mantissa size of said final result is increased by a second number of bits left of its binal point as compared to said initial mantissa size; and

said second number of bits is equal to ceil(log₂M) where M is a total number of inputs entering said tree.

21. The non-transistory machine-readable data storage medium of claim 17 wherein said instructions configure said logic to increase the mantissa size of at least one of first intermediate result, said respective intermediate results and 5 said final result by one bit right of its binal point as compared to said initial mantissa size.

22. The non-transistory machine-readable data storage medium of claim 21 wherein said instructions configure said logic to:

increase said mantissa size of said first intermediate result by one bit right of its binal point as compared to said initial mantissa size; and

increase said mantissa size of each of said respective intermediate results and said final result by one bit right of its binal point as compared to a previous intermediate result.

23. The non-transistory machine-readable data storage medium of claim 21 wherein said instructions configure said logic to, whenever addition of a bit left of the binal point of a result of one of said operations results in the mantissa size of the result of that one of said operations exceeding the initial mantissa size to the left of the binal point by an integer multiple of a predetermined number of bits, and no previous one of said operations has resulted in the mantissa size exceeding the initial mantissa size to the left of the binal point by that integer multiple of the predetermined number of bits, increase the mantissa size of the result of that one of said operations increased by one bit right of its binal point as compared to a previous intermediate result.