Barrel shifter implemented on a configurable integrated circuit

• US 7,518,400 B1
• Filed: 03/08/2006
• Issued: 04/14/2009
• Est. Priority Date: 03/08/2006
• Status: Expired due to Fees

• Current Assignee: Altera Corporation (Intel Corporation)
• Original Assignee: Tabula Incorporated
• Inventors: Schmit, Herman, Redgrave, Jason
• Primary Examiner(s): Barnie, Rexford
• Assistant Examiner(s): Tabler, Matthew C
• Application Number:
  US11/371,194
• Time in Patent Office: 1,133 Days
• Field of Search: 326 38- 41, 326/133
• US Class Current: 326/41
• CPC Class Codes: G06F 5/015 having at least two separately controlled shifting levels, e.g. using shifting matrices G06F5/012 takes precedence

Abstract

Some embodiments provide a barrel shifter on a configurable integrated circuit (IC). The barrel shifter has a first set of tiles and a second set of tiles with configurable circuits. The barrel shifter also has a first set of non-neighboring offset connections (NNOCs) connecting at least one of the tiles in the first set to at least one of the tiles in the second set.

Claims

1. A barrel shifter implemented on an integrated circuit (IC), said barrel shifter comprising:

a) a first plurality of configurable tiles comprising configurable circuits;

b) a second plurality of configurable tiles comprising configurable circuits; and

c) a first set of non-neighboring offset connections (NNOCs) connecting at least two tiles of said first plurality of configurable tiles to at least two tiles of said second plurality of configurable tiles, wherein said first set of NNOCs is for shifting data words by a particular number of bits, and wherein NNOCs directly connect pairs of tiles that are not aligned with each other and do not neighbor each other, wherein the first set of NNOCs are topologically parallel to each other.

2. The barrel shifter of claim 1, wherein each NNOC of said first set of NNOCs connects to a multiplexer of said second plurality of configurable tiles.

3. The barrel shifter of claim 1 further comprising a first plurality of sets of NNOCs, each set of NNOCs connecting said at least two tiles of said first plurality of configurable tiles to at least two tiles of said second plurality of tiles.

4. The barrel shifter of claim 3 further comprising:

a) a third plurality of configurable tiles; and

b) a second plurality of sets of NNOCs connecting at least two tiles of said second plurality of configurable tiles to at least two tiles of said third plurality of configurable tiles.

5. The barrel shifter of claim 4, wherein the first plurality of sets of NNOCs is for shifting an original data word into a first shifted data word while copying or moving the original data word from the first plurality of tiles to the second plurality of configurable tiles.

6. The barrel shifter of claim 5, wherein the first plurality of sets of NNOCs is for shifting said original data word by multiples of four bits.

7. The barrel shifter of claim 5, wherein the second plurality of sets of NNOCs is for shifting a first shifted data word into a second shifted data word while copying or moving the first shifted data word from the second plurality of configurable tiles to the third plurality of configurable tiles.

8. The barrel shifter of claim 7, wherein the second plurality of sets of NNOCs is for shifting said first shifted data word by multiples of four bits.

9. The barrel shifter of claim 1 further comprising direct connections between tiles that are vertically or horizontally aligned with each other.

22. The IC of claim 1, wherein said NNOCs do not comprise intervening interconnect circuits between said tiles.

39. The barrel shifter of claim 1, wherein the first set of NNOCs are also physically parallel to each other.

10. An integrated circuit (IC) for implementing a barrel shifter, said IC comprising:

a) a first plurality of configurable tiles;

b) a second plurality of configurable tiles comprising a first set of interconnect circuits;

c) a third plurality of configurable tiles;

d) a first set of connections connecting the first plurality of configurable tiles to the second plurality of configurable tiles, comprising a first set of non-neighboring offset connections (NNOCs) connecting at least two tiles of said first plurality of configurable tiles to interconnect circuits of at least two tiles of said second plurality of configurable tiles, wherein said first set of NNOCs is for shifting data words by a first number of bits while passing said data words between said first plurality of configurable tiles and said interconnect circuits of said at least two tiles of said second plurality of configurable tiles; and

e) a second set of connections, connecting the second plurality of configurable tiles to the third plurality of configurable tiles, comprising a second set of NNOCs connecting at least two tiles of said second plurality of configurable tiles to at least two tiles of said third plurality of configurable tiles, wherein said second set of NNOCs is for shifting data words by a second number of bits while passing said data words between said second plurality of configurable tiles and said third plurality of configurable tiles,

wherein NNOCs directly connect pairs of tiles that are not aligned with each other and do not neighbor each other, and wherein the first set of connections is for shifting said data words by a number of bits between zero and (N−

1) inclusive, wherein N is an integer, and wherein the second set of connections is for shifting said data words by N times M bits, wherein M is an integer or zero.

11. The IC of claim 10, wherein said first set of NNOCs connects to a plurality of inputs of said first set of interconnect circuits.

12. The IC of claim 11, wherein said second set of NNOCs connects to a plurality of outputs of said first set of interconnect circuits.

13. The IC of claim 10 further comprising:

a) a fourth plurality of configurable tiles; and

b) a third set of NNOCs connecting said third plurality of configurable tiles to said fourth plurality of configurable tiles, wherein said third set of NNOCs is for implementing a third barrel shifter by shifting data words by a third number of bits while passing said data words from said third plurality of configurable tiles to said fourth plurality of configurable tiles.

14. The IC of claim 10 further comprising a third set of NNOCs connecting said first plurality of configurable tiles to said third plurality of configurable tiles.

15. The IC of claim 14, wherein said third plurality of configurable tiles further comprises a second plurality of interconnect circuits.

16. The IC of claim 15, wherein said third plurality of configurable tiles further comprises a plurality of intra-tile connectors.

17. The IC of claim 16, wherein said plurality of intra-tile connectors connects corresponding outputs of each tile of said third plurality of configurable tiles to corresponding inputs of each tile of said third set of configurable tiles.

18. The IC of claim 10, wherein said barrel shifter is for shifting a data word by a number of bits between zero and fifteen inclusive.

19. The IC of claim 10, wherein said barrel shifter is for shifting a data word by a number of bits between zero and thirty-one inclusive.

20. The IC of claim 10 further comprising a first plurality of sets of NNOCs connecting said first plurality of configurable tiles to said second plurality of configurable tiles, wherein each set of NNOCs of said first plurality of sets of NNOCs is for implementing a shift of a particular number of bits.

21. The IC of claim 20 further comprising a second plurality of sets of NNOCs directly connecting said second plurality of configurable tiles to said third plurality of configurable tiles, wherein each set of NNOCs of said second plurality of sets of NNOCs is for implementing a shift of a particular number of bits.

23. A method of barrel shifting data on an integrated circuit (IC) comprising a plurality of configurable tiles comprising a first plurality of configurable tiles and a second plurality of configurable tiles, said first plurality of configurable tiles comprising a plurality of configurable circuits, said method comprising:

a) receiving data at one set of inputs of a plurality of sets of inputs, wherein said one set of inputs comprises one input on each tile of said first plurality of configurable tiles, and wherein said one set of inputs is connected to a set of outputs of said second plurality of configurable tiles by a first set of topologically parallel non-neighboring offset connections (NNOCs), wherein NNOCs directly connect pairs of configurable tiles that are not aligned with each other and do not neighbor each other; and

b) ignoring data at multiple other sets of inputs of said plurality of sets of inputs wherein each set of inputs of said multiple other sets of inputs comprises one input on each tile, wherein receiving data at said first set of inputs and ignoring data on said other sets of inputs facilitates a shift of a particular number of bits.

24. The method of claim 23 further comprising activating said first set of inputs by sending a set of selection bits to each of said second plurality of configurable tiles, wherein said set of selection bits are not configuration data of the IC.

25. The method of claim 24, wherein each tile receives the same selection bits from a common source.

26. The method of claim 23, wherein some sets of said plurality of other sets of inputs is connected to said set of outputs on said second plurality of configurable tiles by its own set of NNOCs.

27. The method of claim 23, wherein a second set of inputs of said multiple other sets of inputs is connected to said set of outputs by non-offset connections.

28. An integrated circuit (IC) comprising:

a) a first plurality of tiles comprising outputs;

b) a second plurality of configurable tiles, each configurable tile of said second plurality of configurable tiles comprising at least one interconnect circuit;

c) a bus passing through said first and second pluralities of configurable tiles wherein, between said first and second pluralities of configurable tiles, said bus comprises;

i) a first plurality of connections for passing data words from said outputs of said first plurality of tiles to said second plurality of configurable tiles without shifting said data words, and

ii) a second plurality of connections for shifting data words by a first number of bits while passing said data words from said first plurality of tiles to said second plurality of configurable tiles, wherein each connection of said second plurality of connections is a non-neighboring offset connection, wherein NNOCs directly connect pairs of tiles that are not aligned with each other and do not neighbor each other; and

d) at least one circuit for determining whether to pass the data words in the bus to the first plurality of connections or the second plurality of connections.

29. The IC of claim 28, wherein each connection of said second plurality of connections does not comprise an intervening interconnect circuit.

30. The IC of claim 28, wherein said first plurality of connections and said second plurality of connections are for using each plurality independently of the other.

31. The IC of claim 28, wherein said bus further comprises multiple additional pluralities of connections, wherein each of the multiple additional pluralities of connections is for shifting data words by a number of bits associated with that additional plurality of connections while passing said data words from said first plurality of tiles to said second plurality of configurable tiles and each connection of said additional pluralities of connections directly connects a pair of configurable tiles that are not aligned with each other and do not neighbor each other.

32. The IC of claim 31, wherein each of the multiple additional plurality of said connections is for shifting data words by an integer multiple of said first number of bits.

33. The IC of claim 28, wherein each tile of said first plurality of tiles is a configurable tile comprising configurable logic circuits and configurable interconnect circuits.

34. The IC of claim 33, wherein each tile of said second plurality of configurable tiles further comprises a configurable logic circuit.

35. An IC comprising:

a) a first plurality of tiles each tile comprising an output;

b) a second plurality of configurable tiles each comprising a plurality of selectable inputs; and

c) a plurality of direct connections connecting said outputs to said selectable inputs, wherein said plurality of direct connections comprise non-neighboring offset connections (NNOCs) wherein NNOCs directly connect pairs of tiles that are not aligned with each other and do not neighbor each other;

wherein each of a plurality of said outputs is connected to selectable inputs of multiple tiles of said second plurality of configurable tiles by multiple direct connections, wherein at least one of said multiple direct connections is an NNOC, and

wherein, when said IC is configured to shift a data word, selectable inputs connected to NNOCs are selected to accept data, wherein at least some NNOCs shifting the data word by a particular number of bits are topologically parallel to each other.

36. The configurable IC of claim 35, wherein said selectable inputs are inputs of interconnect circuits.

37. The configurable IC of claim 36, wherein said interconnect circuits are multiplexers.

38. The configurable IC of claim 35, wherein a plurality of selectable inputs on each of multiple tiles of said second plurality of configurable tiles is connected to multiple outputs by NNOCs.

40. An integrated circuit (IC) for implementing a barrel shifter, said IC comprising:

a) a first, second, and third plurality of configurable tiles, the second plurality of configurable tiles comprising a first set of interconnect circuits;

b) a first set of non-neighboring offset connections (NNOCs) connecting at least two tiles of said first plurality of configurable tiles to interconnect circuits of at least two tiles of said second plurality of configurable tiles, wherein said first set of NNOCs is for shifting data words by a first number of bits while passing said data words between said first plurality of configurable tiles and said interconnect circuits of said at least two tiles of said second plurality of configurable tiles;

c) a second set of NNOCs connecting at least two tiles of said second plurality of configurable tiles to at least two tiles of said third plurality of configurable tiles, wherein said second set of NNOCs is for shifting data words by a second number of bits while passing said data words between said second plurality of configurable tiles and said third plurality of configurable tiles,

wherein NNOCs directly connect pairs of tiles that are not aligned with each other and do not neighbor each other, wherein connections connecting the first plurality of configurable tiles to the second plurality of configurable tiles are for shifting said data words by any specified numbers of bits within a small range of numbers of bits, and wherein connections connecting the second plurality of configurable tiles to the third plurality of configurable tiles are for shifting said data words by any specified multiple of a preset number of bits within a larger range of numbers of bits.