Adder-rounder circuitry for specialized processing block in programmable logic device

• US 7,822,799 B1
• Filed: 06/26/2006
• Issued: 10/26/2010
• Est. Priority Date: 06/26/2006
• Status: Active Grant

• Current Assignee: Tahoe Research Limited (f/k/a Learndale Limited) (Vector Capital Corporation)
• Original Assignee: Altera Corporation (Intel Corporation)
• Inventors: Lin, Yi-Wen, Nguyen, Triet M., Langhammer, Martin
• Primary Examiner(s): Mai; Tan V
• Application Number:
  US11/426,403
• Time in Patent Office: 1,583 Days
• Field of Search: 708700-714, 708550-553
• US Class Current: 708/551
• CPC Class Codes: G06F 7/49963 Rounding to nearest G06F7/49957 takes precedence
• CPC Class Codes: G06F 7/5016 forming at least one of the output signals directly from the minterms of the input signals, i.e. with a minimum number of gate levels
• CPC Class Codes: G06F 7/508 using carry look-ahead circuits
• CPC Class Codes: G06F 7/509 for multiple operands, e.g. digital integrators

Abstract

Adder/rounder circuitry for use in a programmable logic device computes a rounded sum quickly, and ideally within one clock cycle. The rounding position is selectable within a range of bit positions. In an input stage, for each bit position in that range, bits from both addends and a rounding bit are processed, while for each bit position outside that range only bits from both addends are processed. The input stage processing aligns its output in a common format for bits within and outside the range. The input processing may include 3:2 compression for bit positions within the range and 2:2 compression for bit positions outside the range, so that further processing is performed for all bit positions on a sum vector and a carry vector. Computation of the sum proceeds substantially simultaneously with and without the rounding input, and rounding logic makes a selection later in the computation.

Claims

1. Combined adding and rounding circuitry for a programmable logic device, for adding two multi-bit input numbers and rounding a resulting sum to a user-programmable bit position selectable from among a subset of available bit positions, said combined rounding and adding circuitry comprising:

multi-bit addition circuitry; and

input circuitry for (a) accepting, in each bit position, bits of said two multi-bit input numbers and (b) accepting, for each respective bit position in said subset, an additional input of a rounding bit indicative of whether said respective bit position is said user-programmable bit position, said input circuitry outputting data to said multi-bit addition circuitry in a format common to each bit position regardless of the number of inputs to said input circuitry at said bit position.

2. The combined adding and rounding circuitry of claim 1 wherein said input circuitry comprises:

a 2;

2 compressor for each bit position outside said subset; and

a 3;

2 compressor for each bit position in said subset.

3. The combined adding and rounding circuitry of claim 2 wherein said multi-bit addition circuitry comprises:

a first multi-bit adder for accepting at each bit position only one bit from each of said multi-bit numbers; and

a second multi-bit adder for accepting data from said compressors.

4. The combined adding and rounding circuitry of claim 3 further comprising rounding logic for selecting between said first and second multi-bit adders.

5. The combined adding and rounding circuitry of claim 2 wherein:

said bit positions in said subset are in a consecutive range of bit positions;

said 3;

2 compressor for each bit position in said subset comprises one 3;

2 compressor corresponding to all bit positions in said subset; and

said 2;

2 compressor for each bit position outside said subset comprises one 2;

2 compressor corresponding to all bit positions below said range, and one 2;

2 compressor corresponding to all bit positions above said range.

6. The combined adding and rounding circuitry of claim 2 further comprising a prefix network;

wherein;

said input circuitry is a first part of said prefix network; and

a second part of said prefix network is part of said multi-bit addition circuitry.

7. The combined adding and rounding circuitry of claim 6 wherein said prefix network is a Kogge-Stone prefix network.

8. The combined adding and rounding circuitry of claim 6 wherein:

said second part of said prefix network outputs a first set of outputs representing a first rounding condition and a second set of outputs representing a second rounding condition;

said multi-bit addition circuitry further comprises;

a full multi-bit adder, and

a multiplexer for selecting between said first and second sets of outputs and inputting said selected set of outputs to said full multi-bit adder; and

said combined adding and rounding circuitry further comprises rounding logic for controlling said multiplexer.

9. The combined adding and rounding circuitry of claim 8 wherein:

said second part of said prefix network comprises a plurality of nodes; and

each one of said nodes comprises multi-bit generate and propagate circuitry fed by at least two nodes above said one of said nodes.

10. The combined adding and rounding circuitry of claim 9 wherein each one of said nodes is fed by a node immediately above said one of said nodes, and by a node above and to the right of said one of said nodes.

11. The combined adding and rounding circuitry of claim 9 wherein each one of said nodes that is fed at least in part by one of said 3:

2 compressors in said subset comprises two sets of said multi-bit generate and propagate circuitry for providing said first set of outputs representing said first rounding condition and said second set of outputs representing said second rounding condition.

12. The combined adding and rounding circuitry of claim 6 wherein said prefix network is populated in every bit position.

13. The combined adding and rounding circuitry of claim 6 wherein said prefix network is populated in every bit position in said subset, and in less than every bit position outside said subset.

14. The combined adding and rounding circuitry of claim 6 wherein said input circuitry comprises:

a 2;

2 compressor for each bit position outside said range; and

for each bit position in said range, a compressor that simultaneously performs 2;

2 compression to provide a 2;

2 compressed output and 3;

2 compression to provide a 3;

2 compressed output.

15. The combined adding and rounding circuitry of claim 14 further comprising rounding logic for selecting, for each bit position in said range, between said 2:

2 compressed output and said 3;

2 compressed output.

16. The combined adding and rounding circuitry of claim 15 further comprising circuitry for combining said selected compressed outputs.

17. A programmable logic device comprising a specialized processing block including the combined adding and rounding circuitry of claim 1.

18. A digital processing system comprising:

processing circuitry;

a memory coupled to said processing circuitry; and

a programmable logic device as defined in claim 17 coupled to the processing circuitry and the memory.

19. A printed circuit board on which is mounted a programmable logic device as defined in claim 18.

20. The printed circuit board defined in claim 19 further comprising:

memory circuitry mounted on the printed circuit board and coupled to the programmable logic device.

21. The printed circuit board defined in claim 20 further comprising:

processing circuitry mounted on the printed circuit board and coupled to the memory circuitry.

22. An integrated circuit device comprising a specialized processing block including the combined adding and rounding circuitry of claim 1.

23. A digital processing system comprising:

processing circuitry;

a memory coupled to said processing circuitry; and

an integrated circuit device as defined in claim 22 coupled to the processing circuitry and the memory.

24. A printed circuit board on which is mounted an integrated circuit device as defined in claim 23.

25. The printed circuit board defined in claim 24 further comprising:

memory circuitry mounted on the printed circuit board and coupled to the programmable logic device.

26. The printed circuit board defined in claim 25 further comprising:

processing circuitry mounted on the printed circuit board and coupled to the memory circuitry.

27. A method of rounding a sum, computed by circuitry for adding two multi-bit input numbers in a programmable logic device, to a user-programmable bit position selectable from among a subset of available bit positions, said method comprising:

for each bit position outside said subset, processing a bit from each of said multi-bit numbers using a first circuit that inputs two bits and produces a first output having a first number of output bits;

for each respective bit position in said subset, processing a bit from each of said multi-bit numbers with a rounding input indicative of whether said respective bit position is said user-programmable bit position, using a second circuit that inputs three bits and produces a second output having said first number of output bits; and

combining said first and second outputs to produce a rounded sum.

28. The method of claim 27 wherein said processing comprises compressing, each of said first and second circuits comprising a compressor.

29. The method of claim 28 wherein:

said processing of each bit position outside said subset comprises 2;

2 compression, said first circuit comprising a 2;

2 compressor; and

said processing of each bit position in said subset comprises 3;

2 compression, said second circuit comprising a 3;

2 compressor.