Implementing division in a programmable integrated circuit device

• US 8,255,448 B1
• Filed: 10/02/2008
• Issued: 08/28/2012
• Est. Priority Date: 10/02/2008
• Status: Active Grant

• Current Assignee: Altera Corporation (Intel Corporation)
• Original Assignee: Altera Corporation (Intel Corporation)
• Inventors: Langhammer, Martin
• Primary Examiner(s): Ngo, Chuong D
• Application Number:
  US12/244,565
• Time in Patent Office: 1,426 Days
• Field of Search: 708/250, 708/253, 708/254, 708/650, 708/653, 708/654, 708/230, 708/232
• US Class Current: 708/653
• CPC Class Codes: G06F 2207/5355 Using iterative approximation not using digit recurrence, e.g. Newton Raphson or Goldschmidt
• CPC Class Codes: G06F 7/5324 partitioned, i.e. using repetitively a smaller parallel parallel multiplier or using an array of such smaller multipliers
• CPC Class Codes: G06F 7/535 Dividing only

Abstract

Division can be performed in a programmable integrated circuit device by computing a relatively small number of bits of the inverse of the divisor, and then programming multipliers in a specialized processing block of the device to perform multiplication of the dividend and the inverted divisor. The specialized processing block is constructed to be able to be programmed to support such asymmetric multiplication by providing programmable shifting of partial products, so that the partial products can be shifted one number of bits for symmetric multiplication and a different number of bits for asymmetric multiplication. The process is performed recursively, by chaining a plurality of the specialized processing blocks, so that the result converges notwithstanding the relatively low precision of the inverted divisor.

Claims

1. A method of configuring a programmable integrated circuit device to use dedicated symmetrical multipliers to perform a division operation that provides a quotient of a dividend input value and a divisor input value, said quotient having a first precision, said method comprising:

configuring logic of said programmable integrated circuit device to use at least a first of said dedicated symmetrical multipliers to operate on said divisor input value to provide an inverted divisor approximation having a second precision less precise than said first precision;

configuring logic of said programmable integrated circuit device to recursively compute a remainder by initializing said remainder to said dividend input value at said first precision and then, in each recursive stage, subtracting from said remainder a product, computed by a plurality of said dedicated symmetrical multipliers configured as an asymmetrical multiplier, of (a) said remainder represented at said second precision, (b) said divisor input value represented at said first precision, and (c) said inverted divisor approximation;

configuring logic of said programmable integrated circuit device to compute a respective component of said quotient in each said recursive stage, by computing, using at least one of said dedicated symmetrical multipliers, a product of (1) said remainder represented at said second precision, and (2) said inverted divisor approximation; and

configuring logic of said programmable integrated circuit device to add said respective components of said quotient to provide said quotient.

2. The method of claim 1 wherein said configuring logic of said programmable integrated circuit device to recursively compute a remainder comprises configuring said logic to shorten said remainder as computed in each said recursive stage to at most a number of bits representing said first precision.

3. The method of claim 2 wherein said configuring said logic to shorten said remainder to at most said first number of bits comprises configuring said logic to truncate said remainder to said number of bits representing said first precision.

4. The method of claim 2 wherein said configuring said logic to shorten said remainder to at most said number of bits representing said first precision comprises configuring said logic to round said remainder to a number of bits determined by a desired level of precision.

5. The method of claim 1 wherein:

there are four said recursive stages; and

said dividend input value, said divisor input value and said quotient are double-precision values.

6. The method of claim 1 wherein:

there are five said recursive stages; and

said dividend input value, said divisor input value and said quotient are extended double-precision values.

7. The method of claim 1 wherein said configuring logic of said programmable integrated circuit device to add said respective components of said quotient comprises configuring logic of said programmable integrated circuit device as a single adder for adding said components of said quotient from all said stages.

8. The method of claim 7 further comprising configuring logic of said programmable integrated circuit device to shift each component of said quotient from each successive one of said stages by a successive multiple of a predetermined number of bits.

9. The method of claim 8 wherein said predetermined number of bits is less than a number of bits representing said second precision.

10. The method of claim 1 wherein:

said configuring logic of said programmable integrated circuit device to add said respective components of said quotient comprises configuring each said stage to add its respective component of said quotient to a sum of components of said quotient from a preceding stage; and

in a first one of said plurality of stages, said sum of components of said quotient from a preceding stage is considered to be zero.

11. The method of claim 10 further comprising configuring each said stage after said first one of said plurality of stages to shift its respective component of said quotient by a successive multiple of a predetermined number of bits.

12. The method of claim 11 wherein said predetermined number of bits is less than a number of bits representing said second precision.

13. A programmable integrated circuit device configurable to perform a division operation that provides a quotient of a dividend input value and a divisor input value, each of which has a first precision, said programmable integrated circuit device comprising:

a plurality of specialized processing blocks each having a plurality of dedicated symmetrical multiplier circuits;

logic configurable to use at least a first of said dedicated symmetrical multiplier circuits to operate on said divisor input value to provide an inverted divisor approximation having a second precision less precise than said first precision;

logic configurable to recursively compute a remainder by initializing said remainder to said dividend input value at said first precision and then, in each recursive stage, subtracting from said remainder a product, computed using a plurality of said dedicated symmetrical multiplier circuits configured as an asymmetrical multiplier circuit, of (a) said remainder represented at said second precision, (b) said divisor input value represented at said first precision, and (c) said inverted divisor approximation;

logic configurable to compute a respective component of said quotient in each said recursive stage, by computing, using at least one of said dedicated symmetrical multiplier circuits, a product of (1) said remainder represented at said second precision, and (2) said inverted divisor approximation; and

logic configurable to add said respective components of said quotient to provide said quotient.

14. The programmable integrated circuit device of claim 13 wherein said logic configurable to recursively compute a remainder comprises configuring said logic to shorten said remainder as computed in each said recursive stage to at most a number of bits representing said first precision.

15. The programmable integrated circuit device of claim 14 wherein said logic configurable to shorten said remainder to at most said first number of bits comprises configuring said logic to truncate said remainder to said number of bits representing said first precision.

16. The programmable integrated circuit device of claim 14 wherein said logic configurable to shorten said remainder to at most said number of bits representing said first precision comprises configuring said logic to round said remainder to a number of bits determined by a desired level of precision.

17. The programmable integrated circuit device of claim 13 wherein:

there are four said recursive stages; and

said dividend input value, said divisor input value and said quotient are double-precision values.

18. The programmable integrated circuit device of claim 13 wherein:

there are five said recursive stages; and

said dividend input value, said divisor input value and said quotient are extended double-precision values.

19. The programmable integrated circuit device of claim 13 wherein said logic configurable to add said respective components of said quotient comprises logic configurable as a single adder for adding said components of said quotient from all said stages.

20. The programmable integrated circuit device of claim 19 further comprising logic configurable to shift each component of said quotient from each successive one of said stages by a successive multiple of a predetermined number of bits.

21. The programmable integrated circuit device of claim 20 wherein said predetermined number of bits is less than a number of bits representing said second precision.

22. The programmable integrated circuit device of claim 13 wherein:

said logic configurable to add said respective components of said quotient comprises logic in each said stage configurable to add its respective component of said quotient to a sum of components of said quotient from a preceding stage; and

in a first one of said plurality of stages, said sum of components of said quotient from a preceding stage is considered to be zero.

23. The programmable integrated circuit device of claim 22 further comprising logic in each said stage after said first one of said plurality of stages configurable to shift its respective component of said quotient by a successive multiple of a predetermined number of bits.

24. The programmable integrated circuit device of claim 23 wherein said predetermined number of bits is less than a number of bits representing said second precision.

25. The programmable integrated circuit device of claim 13 wherein said programmable integrated circuit device is a programmable logic device.

26. A programmable integrated circuit device configured to perform a division operation that provides a quotient of a dividend input value and a divisor input value, each of which has a first precision, said programmable integrated circuit device comprising:

a plurality of specialized processing blocks each having a plurality of dedicated symmetrical multiplier circuits;

logic configured to use at least a first of said dedicated symmetrical multiplier circuits to operate on said divisor input value to provide an inverted divisor approximation having a second precision less precise than said first precision;

logic configured to recursively compute a remainder by initializing said remainder to said dividend input value at said first precision and then, in each recursive stage, subtracting from said remainder a product, computed using a plurality of said dedicated symmetrical multiplier circuits configured as an asymmetrical multiplier circuit, of (a) said remainder represented at said second precision, (b) said divisor input value represented at said first precision, and (c) said inverted divisor approximation;

logic configured to compute a respective component of said quotient in each said recursive stage, by computing, using at least one of said dedicated symmetrical multiplier circuits, a product of (1) said remainder represented at said second precision, and (2) said inverted divisor approximation; and

logic configured to add said respective components of said quotient to provide said quotient.

27. The configured programmable integrated circuit device of claim 26 wherein said logic configured to recursively compute a remainder comprises configuring said logic to shorten said remainder as computed in each said recursive stage to at most a number of bits representing said first precision.

28. The configured programmable integrated circuit device of claim 27 wherein said logic configured to shorten said remainder to at most said first number of bits comprises configuring said logic to truncate said remainder to said number of bits representing said first precision.

29. The configured programmable integrated circuit device of claim 27 wherein said logic configured to shorten said remainder to at most said number of bits representing said first precision comprises configuring said logic to round said remainder to a number of bits determined by a desired level of precision.

30. The configured programmable integrated circuit device of claim 26 wherein:

there are four said recursive stages; and

said dividend input value, said divisor input value and said quotient are double-precision values.

31. The configured programmable integrated circuit device of claim 26 wherein:

there are five said recursive stages; and

said dividend input value, said divisor input value and said quotient are extended double-precision values.

32. The configured programmable integrated circuit device of claim 26 wherein said logic configured to add said respective components of said quotient comprises logic configured as a single adder for adding said components of said quotient from all said stages.

33. The configured programmable integrated circuit device of claim 32 further comprising logic configured to shift each component of said quotient from each successive one of said stages by a successive multiple of a predetermined number of bits.

34. The configured programmable integrated circuit device of claim 33 wherein said predetermined number of bits is less than a number of bits representing said second precision.

35. The configured programmable integrated circuit device of claim 26 wherein:

said logic configured to add said respective components of said quotient comprises logic in each said stage configurable to add its respective component of said quotient to a sum of components of said quotient from a preceding stage; and

in a first one of said plurality of stages, said sum of components of said quotient from a preceding stage is considered to be zero.

36. The configured programmable integrated circuit device of claim 35 further comprising logic in each said stage after said first one of said plurality of stages configurable to shift its respective component of said quotient by a successive multiple of a predetermined number of bits.

37. The configured programmable integrated circuit device of claim 36 wherein said predetermined number of bits is less than a number of bits representing said second precision.

38. The configured programmable integrated circuit device of claim 26 wherein said programmable integrated circuit device is a programmable logic device.

39. A machine-readable data storage medium encoded with machine-executable instructions for configuring a programmable integrated circuit device to use dedicated symmetrical multipliers to perform a division operation that provides a quotient of a dividend input value and a divisor input value, said quotient having a first precision, said instructions comprising:

instructions to configure logic of said programmable integrated circuit device to use at least a first of said dedicated symmetrical multipliers to operate on said divisor input value to provide an inverted divisor approximation having a second precision less precise than said first precision;

instructions to configure logic of said programmable integrated circuit device to recursively compute a remainder by initializing said remainder to said dividend input value at said first precision and then, in each recursive stage, subtracting from said remainder a product, computed using a plurality of said dedicated symmetrical multipliers configured as an asymmetrical multiplier, of (a) said remainder represented at said second precision, (b) said divisor input value represented at said first precision, and (c) said inverted divisor approximation;

instructions to configure logic of said programmable integrated circuit device to compute a respective component of said quotient in each said recursive stage, by computing, using at least one of said dedicated symmetrical multipliers, a product of (1) said remainder represented at said second precision, and (2) said inverted divisor approximation; and

instructions to configure logic of said programmable integrated circuit device to add said respective components of said quotient to provide said quotient.

40. The machine-readable data storage medium of claim 39 wherein said instructions to configure logic of said programmable integrated circuit device to recursively compute a remainder comprises instructions to configure said logic to shorten said remainder as computed in each said recursive stage to at most a number of bits representing said first precision.

41. The machine-readable data storage medium of claim 40 wherein said instructions to configure said logic to shorten said remainder to at most said first number of bits comprises instructions to configure said logic to truncate said remainder to said number of bits representing said first precision.

42. The machine-readable data storage medium of claim 40 wherein said instructions to configure said logic to shorten said remainder to at most said number of bits representing said first precision comprises instructions to configure said logic to round said remainder to a number of bits determined by a desired level of precision.

43. The machine-readable data storage medium of claim 39 wherein:

there are four said recursive stages; and

said dividend input value, said divisor input value and said quotient are double-precision values.

44. The machine-readable data storage medium of claim 39 wherein:

there are five said recursive stages; and

said dividend input value, said divisor input value and said quotient are extended double-precision values.

45. The machine-readable data storage medium of claim 39 wherein said instructions to configure logic of said programmable integrated circuit device to add said respective components of said quotient comprises instructions to configure logic of said programmable integrated circuit device as a single adder for adding said components of said quotient from all said stages.

46. The machine-readable data storage medium of claim 45 further comprising instructions to configure logic of said programmable integrated circuit device to shift each component of said quotient from each successive one of said stages by a successive multiple of a predetermined number of bits.

47. The machine-readable data storage medium of claim 46 wherein said predetermined number of bits is less than a number of bits representing said second precision.

48. The machine-readable data storage medium of claim 39 wherein:

said instructions to configure logic of said programmable integrated circuit device to add said respective components of said quotient comprises instructions to configure each said stage to add its respective component of said quotient to a sum of components of said quotient from a preceding stage; and

in a first one of said plurality of stages, said sum of components of said quotient from a preceding stage is considered to be zero.

49. The machine-readable data storage medium of claim 48 further comprising instructions to configure each said stage after said first one of said plurality of stages to shift its respective component of said quotient by a successive multiple of a predetermined number of bits.

50. The machine-readable data storage medium of claim 49 wherein said predetermined number of bits is less than a number of bits representing said second precision.