Programmable device using fixed and configurable logic to implement recursive trees

• US 9,600,278 B1
• Filed: 07/15/2013
• Issued: 03/21/2017
• Est. Priority Date: 05/09/2011
• Status: Active Grant

• Current Assignee: Broadcom Corporation (Broadcom, Inc.), Altera Corporation (Intel Corporation)
• Original Assignee: Altera Corporation (Intel Corporation)
• Inventors: Langhammer, Martin
• Primary Examiner(s): Malzahn, David H
• Application Number:
  US13/941,847
• Time in Patent Office: 1,345 Days
• Field of Search: None
• US Class Current: 1/1
• 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/509 for multiple operands, e.g. digital integrators
• CPC Class Codes: G06F 7/5443 Sum of products for applications thereof, see the relevant places, e.g. G06F17/10, H03H17/00
• CPC Class Codes: G06F 9/3001 Arithmetic instructions
• CPC Class Codes: H03K 19/17732 Macroblocks
• CPC Class Codes: H03K 19/17744 for input/output signals

Abstract

A specialized processing block on a programmable integrated circuit device includes a first floating-point arithmetic operator stage, and a floating-point adder stage having at least one floating-point binary adder. Configurable interconnect within the specialized processing block routes signals into and out of each of the first floating-point arithmetic operator stage and the floating-point adder stage. The block has a plurality of block inputs, at least one block output, a direct-connect input for connection to a first other instance of the specialized processing block, and a direct-connect output for connection to a second other instance of the specialized processing block. A plurality of instances of the specialized processing block are together configurable as a binary or ternary recursive adder tree.

Claims

1. First, second, and third specialized processing blocks on a programmable integrated circuit device, each of said first, second and third specialized processing blocks comprising:

a floating-point arithmetic operator stage;

a floating-point adder stage comprising at least one floating-point binary adder;

a plurality of block inputs;

at least one block output;

a direct-connect input; and

configurable interconnect that comprises selectable routing connections at least between said direct-connect input and said floating-point adder stage, a first block input of said plurality of block inputs and said floating-point adder stage, a second block input of said plurality of block inputs and said floating-point arithmetic operator stage, said floating-point arithmetic operator stage and said direct-connect output, and said floating-point adder stage and said at least one block output;

whereby;

said direct-connect input of said first specialized processing block is coupled to said direct-connect output of said second specialized processing block;

said direct-connect output of said first specialized processing block is coupled to said direct-connect input of said third specialized processing block; and

said first, second, and third specialized processing blocks are together configurable to form at least a portion of a recursive adder tree.

2. The first, second, and third specialized processing blocks of claim 1, wherein said configurable interconnect further comprises:

an internal feedback bus from said at least one block output to said first block input of said plurality of block inputs.

3. The first, second, and third specialized processing blocks of claim 2 wherein:

said floating-point adder stage includes only one floating-point binary adder; and

said at least a portion of said recursive adder tree is at least a portion of a binary recursive adder tree.

4. The first, second, and third specialized processing blocks of claim 3 wherein said configurable interconnect further comprises:

a bypass path from said first block input of said plurality of block inputs to said direct-connect output, wherein an output signal of said floating-point adder stage is routed via said internal feedback bus to said first block input of said plurality of block inputs and from said first block input of said plurality of block inputs via said bypass path to said direct-connect output.

5. The first, second, and third specialized processing blocks of claim 1 wherein:

said floating-point adder stage includes only one floating-point binary adder; and

said at least a portion of said recursive adder tree is at least a portion of a ternary recursive adder tree.

6. The first, second, and third specialized processing blocks of claim 1 wherein:

said floating-point adder stage includes two floating-point binary adders; and

said at least a portion of said recursive adder tree is at least a portion of a ternary recursive adder tree.

7. The first, second, and third specialized processing blocks of claim 6 wherein:

said configurable interconnect further comprises an additional selectable routing connection between said two floating-point binary adders that is configurable to route an output of one of said two floating-point binary adders to an input of another of said two floating-point binary adders; and

said two floating-point binary adders form a ternary adder.

8. A programmable integrated circuit device comprising:

a plurality of specialized processing blocks, each of said plurality of specialized processing blocks comprising;

a floating-point arithmetic operator stage;

a floating-point adder stage comprising at least one floating-point binary adder;

a plurality of block inputs;

at least one block output;

a direct-connect input for connection to a first other specialized processing block of said plurality of specialized processing blocks; and

a direct-connect output for connection to a second other specialized processing block of said plurality of specialized processing blocks;

configurable interconnect that comprises selectable routing connections at least between said direct-connect input and said floating-point adder stage, a first block input of said plurality of block inputs and said floating-point adder stage, a second block input of said plurality of block inputs and said first floating-point arithmetic operator stage, said floating-point arithmetic operator stage and said direct-connect output, and said floating-point adder stage and said at least one block output;

whereby;

a recursive adder tree is configurable on said programmable integrated circuit device using said plurality of specialized processing blocks.

9. The programmable integrated circuit device of claim 8 wherein:

said floating-point adder stage includes only one floating-point binary adder; and

said recursive adder tree configurable on said programmable integrated circuit device is a binary recursive adder tree.

10. The programmable integrated circuit device of claim 9 wherein:

said binary recursive adder tree is configured using said plurality of specialized processing blocks; and

in one of said plurality of specialized processing blocks, said configurable interconnect further comprises a first additional selectable routing connection between said floating-point adder stage and said first block input of said plurality of block inputs of said one of said plurality of specialized processing blocks and a second additional selectable routing connection between said first block input of said plurality of block inputs and said direct-connect output of said one of said plurality of specialized processing blocks.

11. The programmable integrated circuit device of claim 10 further comprising:

general-purpose programmable interconnect outside of said plurality of specialized processing blocks that is coupled at least to said at least one block output of said one of said plurality of specialized processing blocks, wherein a signal is routed from an output of said floating-point adder stage of said one of said plurality of specialized processing blocks via said at least one block output and via said general-purpose programmable interconnect of said programmable integrated circuit device to said first block input of said plurality of block inputs of another one of said plurality of specialized processing blocks.

12. The programmable integrated circuit device of claim 11 wherein said one of said plurality of specialized processing blocks further comprises an internal feedback bus from said at least one block output of said one of said plurality of specialized processing blocks to said first block input of said plurality of block inputs of said one of said plurality of specialized processing blocks.

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

said floating-point adder stage includes only one floating-point binary adder; and

said recursive adder tree configurable on said programmable integrated circuit device is a ternary recursive adder tree.

14. The programmable integrated circuit device of claim 8 wherein:

said floating-point adder stage includes two floating-point binary adders; and

said recursive adder tree configurable on said programmable integrated circuit device is a ternary recursive adder tree.

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

said configurable interconnect further comprises an additional selectable routing connection between said two floating-point binary adders that is configurable to route an output of one of said two floating-point binary adders to an input of another of said two floating-point binary adders; and

said two floating-point binary adders form a ternary adder.

16. The programmable integrated circuit device of claim 14 wherein:

said configurable interconnect further comprises a first additional selectable routing connection between said two floating-point binary adders that is configurable to route an output of one of said two floating-point binary adders to an input of another of said two floating-point binary adders, and a second additional selectable routing connection between said one of said two floating-point binary adders and said direct-connect output that is configurable to route an output of one of said two floating-point binary adders to said direct-connect output; and

said two floating-point binary adders in one of said plurality of specialized processing blocks and one of said floating-point adders in another of said plurality of specialized processing blocks form a quaternary adder.

17. A method of configuring a programmable integrated circuit device as a recursive adder tree, said programmable integrated circuit device comprising specialized processing blocks, each of said specialized processing blocks including:

a floating-point arithmetic operator stage,

a floating-point adder stage comprising at least one floating-point binary adder,

a plurality of block inputs,

at least one block output,

a direct-connect input for connection to a first other specialized processing block of said specialized processing blocks,

a direct-connect output for connection to a second other specialized processing block of said specialized processing blocks, and

configurable interconnect that comprises selectable routing connections at least between said direct-connect input and said floating-point adder stage, said floating-point adder stage and a first block input of said plurality of block inputs, a second block input of said plurality of block inputs and said floating-point arithmetic operator stage, said first block input of said plurality of block inputs and said direct-connect output, and said floating-point adder stage and said at least one block output;

said method comprising;

configuring a binary recursive adder tree using said specialized processing blocks;

wherein;

in one of said specialized processing blocks, an output of said floating-point adder stage is fed back via said configurable interconnect to said first block input of said plurality of block inputs of said one of said specialized processing blocks and routed from said first block input of said plurality of block inputs via said configurable interconnect to said direct-connect output of said one of said specialized processing blocks.

18. The method of claim 17, wherein said programmable integrated circuit device further comprises general-purpose programmable interconnect outside of said specialized processing blocks that is coupled at least to said at least one block output of said one of said specialized processing blocks, the method further comprising:

feeding back said output of said floating-point adder stage of said one of said specialized processing blocks via said at least one block output of said one of said specialized processing blocks and said general-purpose programmable interconnect of said programmable integrated circuit device to said input of said one of said specialized processing blocks.

19. The method of claim 17 wherein:

said floating-point adder stage includes two floating-point binary adders and said configurable interconnect further comprises an additional selectable routing connection between said two floating-point binary adders that is configurable to route an output of one of said two floating-point binary adders to an input of another of said two floating-point binary adders;

said method comprising;

routing said output of said one of said two floating-point binary adders to said input of said another of said two floating-point binary adders to form a ternary adder.

20. The method of claim 17 wherein in each of said specialized processing blocks:

said floating-point adder stage includes two floating-point binary adders and said configurable interconnect further comprises;

a first additional selectable routing connection between said two floating-point binary adders that is configurable to route one output of one of said two floating-point binary adders to an input of another of said two floating-point binary adders, and

a second additional selectable routing connection between said one of said two floating-point binary adders and said direct-connect output that is configurable to route another output of said one of said two floating-point binary adders to said direct-connect output;

said method comprising;

routing said one output of said one of said two floating-point binary adders in said one of said specialized processing blocks to said input of said another of said two floating-point binary adders in said one of said specialized processing blocks;

routing said another output of said one of said two floating-point binary adders in another of said specialized processing blocks to said direct-connect output of said another of said specialized processing blocks;

routing said direct-connect output of said another of said specialized processing blocks to said direct-connect input of said one of said specialized processing blocks; and

routing said direct-connect input of said one of said specialized processing blocks to said input of said another of said two floating-point binary adders in said one of said specialized processing blocks;

thereby;

forming a quaternary adder from said one of said two floating-point binary adders and said another of said two floating-point binary adders in said one of said specialized processing blocks and said one of said two floating-point binary adders in said another of said specialized processing blocks.

21. A non-transitory machine-readable data storage medium encoded with machine-executable instructions for performing a method of configuring a programmable integrated circuit device as a recursive adder tree, said programmable integrated circuit device comprising specialized processing blocks, each of said specialized processing blocks including:

a floating-point arithmetic operator stage,

a floating-point adder stage comprising at least one floating-point binary adder,

a plurality of block inputs,

at least one block output,

a direct-connect input for connection to a first other specialized processing block of said specialized processing blocks,

a direct-connect output for connection to a second other specialized processing block of said specialized processing blocks, and

configurable interconnect that comprises selectable routing connections at least between said direct-connect input and said floating-point adder stage, said floating-point adder stage and a first block input of said plurality of block inputs, a second block input of said plurality of block inputs and said floating-point arithmetic operator stage, said first block input of said plurality of block inputs and said direct-connect output, and said floating-point adder stage and said at least one block output;

said instructions comprising;

instructions to configure a binary recursive adder tree using said specialized processing blocks;

wherein;

in one of said specialized processing blocks, an output of said floating-point adder stage is fed back via said configurable interconnect to said first block input of said plurality of block inputs of said one of said specialized processing blocks and routed via said configurable interconnect to said direct-connect output of said one of said specialized processing blocks.

22. The non-transitory machine-readable data storage medium of claim 21, wherein said programmable integrated circuit device further comprises general-purpose programmable interconnect outside of said specialized processing blocks that is coupled at least to said at least one block output of said one of said specialized processing blocks, wherein said instructions comprise instructions to feed back said output of said floating-point adder stage of said one of said specialized processing blocks via said at least one block output of said one of said specialized processing blocks and said general-purpose programmable interconnect of said programmable integrated circuit device to said first block input of said plurality of block inputs of said one of said specialized processing blocks.

23. The non-transitory machine-readable data storage medium of claim 21 wherein:

said floating-point adder stage includes two floating-point binary adders and said configurable interconnect further comprises an additional selectable routing connection between said two floating-point binary adders that is configurable to route an output of one of said two floating-point binary adders to an input of another of said two floating-point binary adders;

said instructions comprising;

instructions to route said output of said one of said two floating-point binary adders to said input of said another of said two floating-point binary adders to form a ternary adder.

24. The non-transitory machine-readable data storage medium of claim 21 wherein:

said floating-point adder stage includes two floating-point binary adders and said configurable interconnect further comprises;

a first additional selectable routing connection between said two floating-point binary adders that is configurable to route an output of one of said two floating-point binary adders to an input of another of said two floating-point binary adders, and

a second additional selectable routing connection between said one of said two floating-point binary adders and said direct-connect output that is configurable to route another output of said one of said two floating-point binary adders to said direct-connect output;

said instructions comprising;

instructions to route said output of said one of said two floating-point binary adders in said one of said specialized processing blocks to said input of said another of said two floating-point binary adders in said one of said specialized processing blocks;

instructions to route said output of said one of said two floating-point binary adders in another of said specialized processing blocks to said direct-connect output of said another of said specialized processing blocks;

instructions to route said direct-connect output of said another of said specialized processing blocks to said direct-connect input of said one of said specialized processing blocks; and

instructions to route said direct-connect input of said one of said specialized processing blocks to another input of said another of said two floating-point binary adders in said one of said specialized processing blocks;

thereby;

forming a quaternary adder from said one of said two floating-point binary adders and said another of said two floating-point binary adders in said one of said specialized processing blocks and said one of said two floating-point binary adders in said another of said specialized processing blocks.