Loosely-biased heterogeneous reconfigurable arrays

• US 20040001445A1
• Filed: 07/01/2002
• Published: 01/01/2004
• Est. Priority Date: 07/01/2002
• Status: Active Grant

• Current Assignee: Panasonic Corporation (Panasonic Holdings Corporation)
• Original Assignee: Elixent Ltd. (Panasonic Holdings Corporation)
• Inventors: Stansfield, Anthony I.
• Granted Patent: US 7,471,643 B2
• Time in Patent Office: Days
• US Class Current: 370/254
• CPC Class Codes: G06F 15/7867 with reconfigurable architecture
• CPC Class Codes: G06F 9/3001 Arithmetic instructions
• CPC Class Codes: G06F 9/3842 Speculative instruction execution
• CPC Class Codes: G06F 9/3885 using a plurality of independent parallel functional units
• CPC Class Codes: G06F 9/3897 with adaptable data path
• CPC Class Codes: H03K 19/1737 using multiplexers H03K19/1738 takes precedence
• CPC Class Codes: H03K 19/17728 Reconfigurable logic blocks, e.g. lookup tables
• CPC Class Codes: H03K 19/17736 Structural details of routing resources
• CPC Class Codes: H03K 19/17748 Structural details of configuration resources
• CPC Class Codes: H03K 19/17796 for physical disposition of blocks

Abstract

A heterogeneous array includes clusters of processing elements. The clusters include a combination of ALUs and multiplexers linked by direct connections and various general-purpose routing networks. The multiplexers are controlled by the ALUs in the same cluster, or alternatively by ALUs in other clusters, via a dedicated multiplexer control network. Components of applications configured onto the array are selectively implemented in either multiplexers or ALUs, as determined by the relative efficiency of implementing the component in one or the other type of processing element, and by the relative availability of the processing element types. Multiplexer control signals are generated from combinations of ALU status signals, and optionally routed to control multiplexers in different clusters.

Claims

1. A heterogeneous reconfigurable array, comprising:

a general-purpose routing network,

a plurality of clusters connected to the general-purpose routing network, each cluster comprising a plurality of processing elements, each plurality of processing elements comprising;

a first processing element, and

a second processing element;

wherein the first processing element is of a first type and the second processing element is of a second type;

wherein the first processing element comprises a first input, a second input, a first output and a second output;

wherein the first input and first output are adapted to be connected to the general-purpose routing network without passing through any processing elements;

wherein the second output is adapted to be connected to the second processing element without connecting to the general-purpose routing network;

wherein the second processing element comprises a third input, a fourth input and a third output; and

wherein the third input and third output are adapted to be connected to the general-purpose routing network without passing through any processing elements.

2. The heterogeneous reconfigurable array of claim 1, wherein the first processing element is adapted to be configured for use either combined with the second processing element or independent of the second processing element;

and

wherein the second processing element is adapted to be configured for use either combined with the first processing element or independent of the first processing element.

3. The heterogeneous reconfigurable array of claim 1, wherein the first processing element is adapted to be configured such that:

a first connection is made between the general-purpose routing network and the first input without passing through any other processing elements,

a second connection is made between the general-purpose routing network and the first output without passing through any other processing elements, and

a third connection is made between the second output and an input of the second processing element, the third connection being independent of the general-purpose routing network.

4. The heterogeneous reconfigurable array of claim 1, wherein the second processing element is adapted to be configured such that:

a fourth connection is made between the general-purpose routing network and the third input without passing through any other processing elements,

a fifth connection is made between the general-purpose routing network and the third output without passing through any other processing elements, and

a sixth connection is made between the fourth input and an output of the first processing element, the sixth connection being independent of the general-purpose routing network.

5. The heterogeneous reconfigurable array of claim 1, wherein the general-purpose routing network comprises a plurality of first busses each comprising a first bit width;

wherein the first bit width is greater than one;

wherein the second output comprises a second bus comprising a second bit width; and

wherein the second bit width is not equal to the first bit width.

6. The heterogeneous reconfigurable array of claim 5, wherein the second bit width is one.

7. The heterogeneous reconfigurable array of claim 1, wherein the general-purpose routing network comprises a plurality of first busses each comprising a first bit width;

wherein the first bit width is greater than one;

wherein the fourth input comprises a second bus comprising a second bit width; and

wherein the second bit width is not equal to the first bit width.

8. The heterogeneous reconfigurable array of claim 7, wherein the second bit width is one.

9. The heterogeneous reconfigurable array of claim 1, wherein the first processing element comprises an arithmetic logic unit (“

ALU”

).

10. The heterogeneous reconfigurable array of claim 9, wherein the ALU is adapted to process a data word of a first bit width.

11. The heterogeneous reconfigurable array of claim 9, wherein the first input comprises an ALU data input, the second input comprises an ALU instruction input, and the second output comprises an ALU output, wherein the ALU output is adapted to transmit an output signal derived from one or more input signals received by one or more of the ALU data or ALU instruction inputs.

12. The heterogeneous reconfigurable array of claim 11, wherein the output signal is adapted to be derived from an input signal received by the ALU data input.

13. The heterogeneous reconfigurable array of claim 11, wherein the output signal is adapted to be derived from an input signal received by the ALU instruction input.

14. The heterogeneous reconfigurable array of claim 11, wherein the output signal is adapted to be derived from a logical combination of input signals received by the ALU data and ALU instruction inputs.

15. The heterogeneous reconfigurable array of claim 11, wherein the output signal comprises an ALU carry out signal.

16. The heterogeneous reconfigurable array of claim 11, wherein the output signal comprises a sign bit generated by the ALU, the sign bit being equal to the correct sign of a signed arithmetic operation.

17. The heterogeneous reconfigurable array of claim 11, wherein the output signal comprises a match signal that indicates equality of a first ALU data value and a second ALU data value.

18. The heterogeneous reconfigurable array of claim 11, wherein the output signal comprises a match signal that indicates inequality of a first ALU data value and a second ALU data value.

19. The heterogeneous reconfigurable array of claim 11, wherein the output signal comprises an ALU instruction bit received by the ALU instruction input.

20. The heterogeneous reconfigurable array of claim 1, wherein the second processing element comprises a multiplexer, the third input comprises a multiplexer input, the fourth input comprises a select input and the third output comprises a multiplexer output.

21. The heterogeneous reconfigurable array of claim 20, wherein the select input is adapted to be connected to the first processing element without using the general-purpose routing network.

22. The heterogeneous reconfigurable array of claim 20, wherein the multiplexer output is connected to an inverter.

23. The heterogeneous reconfigurable array of claim 20, wherein the multiplexer is adapted to process a data word of a first bit width, wherein the first bit width is greater than one.

24. The heterogeneous reconfigurable array of claim 1, wherein at least one of the plurality of processing elements further comprises a register.

25. The heterogeneous reconfigurable array of claim 24, wherein each of the plurality of processing elements further comprises a register.

26. The heterogeneous reconfigurable array of claim 20, wherein the multiplexer input receives a constant value signal.

27. The heterogeneous reconfigurable array of claim 20, wherein the second processing element further comprises a register.

28. The heterogeneous reconfigurable array of claim 27, wherein the multiplexer input is adapted to receive a feedback signal from the register.

29. A heterogeneous reconfigurable array, comprising:

a general-purpose routing network; and

a plurality of clusters;

each cluster comprising an arithmetic logic unit (“

ALU”

) and a multiplexer;

the multiplexer comprising;

a plurality of multiplexer inputs comprising;

a multiplexer select input, and

a first multiplexer input; and

a multiplexer output;

the ALU comprising;

a plurality of ALU inputs, comprising;

a first ALU data input,

a second ALU data input, and

an ALU instruction input; and

an ALU output

wherein the multiplexer select input is adapted to receive a multiplexer select signal generated by the ALU; and

wherein the multiplexer and the ALU are connected to the general-purpose routing network;

30. The heterogeneous reconfigurable array of claim 29, wherein the multiplexer select signal comprises an instruction input signal bit.

31. The heterogeneous reconfigurable array of claim 29, wherein the multiplexer select signal comprises a combinatorial function.

32. The heterogeneous reconfigurable array of claim 31, wherein multiplexer select signal is generated using one or more input signals received on at least one of the first ALU data input, second ALU data input or ALU instruction input.

33. The heterogeneous reconfigurable array of claim 32, wherein at least one of the input signals comprises more than one bit.

34. The heterogeneous reconfigurable array of claim 30, wherein the first ALU input, ALU output, first multiplexer input and multiplexer output are adapted to be connected to the general-purpose routing network.

35. The heterogeneous reconfigurable array of claim 30, wherein one or more of the ALU inputs comprise word-wide inputs and the ALU output comprises a word-wide output, the first multiplexer input comprises a word-wide input and the multiplexer output comprises a word-wide output, and the word-wide inputs and outputs are adapted to be connected to the general-purpose routing network.

36. The heterogeneous reconfigurable array of claim 31, wherein the multiplexer select signal comprises a carry out signal.

37. The heterogeneous reconfigurable array of claim 31, wherein the multiplexer select signal comprises a sign signal.

38. The heterogeneous reconfigurable array of claim 31, wherein the multiplexer select signal comprises an overflow signal.

39. The heterogeneous reconfigurable array of claim 29, wherein the cluster is adapted to be configured into a data selection circuit.

40. The heterogeneous reconfigurable array of claim 29, wherein the cluster is adapted to be configured into a condition processing circuit.

41. The heterogeneous reconfigurable array of claim 29, wherein the cluster is adapted to be configured into a datapath control circuit.

42. The heterogeneous reconfigurable array of claim 29, wherein the multiplexer select signal input is adapted to bypass the general-purpose routing network.

43. The heterogeneous reconfigurable array of claim 29, wherein an output signal generated by the ALU and routed through the ALU output is propagated to the general-purpose routing network, and wherein the ALU output is not directly connected to the general-purpose routing network.

44. The heterogeneous reconfigurable array of claim 43, wherein the general-purpose routing network has a first bit width, the first bit width comprising two or more bits, and the output signal has a second bit width, the second bit width comprising one or more bits the first bit width being greater than the second bit width.

45. The heterogeneous reconfigurable array of claim 44, wherein the output signal is converted from the second bit width to the first bit width.

46. The heterogeneous reconfigurable array of claim 43, wherein the output signal is propagated to the general-purpose routing network by being routed through the multiplexer.

47. The heterogeneous reconfigurable array of claim 29, further comprising an output register connected to the multiplexer output.

48. The heterogeneous reconfigurable array of claim 47, wherein the multiplexer output is adapted to be routed through the register.

49. The heterogeneous reconfigurable array of claim 47, wherein the multiplexer and the output register are adapted to be configured into a register with enable circuit.

50. The heterogeneous reconfigurable array of claim 47, wherein the multiplexer and the output register are adapted to be configured into a register with reset circuit.

51. The heterogeneous reconfigurable array of claim 29, further comprising input selection logic connected to one of the plurality of multiplexer inputs.

52. The heterogeneous reconfigurable array of claim 51, wherein the input selection logic comprises a second multiplexer comprising at least one input adapted to receive a constant value.

53. The heterogeneous reconfigurable array of claim 51, further comprising an application configured onto the heterogeneous reconfigurable array wherein the input selection logic is not controlled dynamically by the application.

54. The heterogeneous reconfigurable array of claim 51, wherein the input selection logic is adapted to create a feedback path from the multiplexer output to one of the plurality of multiplexer inputs.

55. The heterogeneous reconfigurable array of claim 51, wherein the input selection logic is adapted to provide a carry out signal from the ALU to the multiplexer.

56. The heterogeneous reconfigurable array of claim 29, wherein the array is adapted to provide a feedback path from the multiplexer output to one of the plurality of ALU inputs.

57. The heterogeneous reconfigurable array of claim 56, wherein the feedback path is provided after an output selection switch connected to the multiplexer output.

58. The heterogeneous reconfigurable array of claim 57, wherein the feedback path creates an asynchronous latch.

59. The heterogeneous reconfigurable array of claim 29, further comprising an inverter connected to the multiplexer output.

60. The heterogeneous reconfigurable array of claim 54, wherein the multiplexer output is adapted to be routed through the inverter.

61. A method of configuring an heterogeneous reconfigurable array, the heterogeneous reconfigurable array comprising a plurality of clusters, each cluster comprising a first processing element and a second processing element, the method comprising:

receiving an application,

selecting a first portion of the application,

selecting a second portion of the application,

selecting a third portion of the application,

implementing the first portion in the plurality of first processing elements,

implementing the second portion in the plurality of second processing elements, and

selectively implementing the third portion in either the plurality of first processing elements, the plurality of second processing elements, or a combination thereof, based upon an availability criterion.

62. The method of claim 61, wherein the first portion comprises an application element adapted to be implemented using a first processing element.

63. The method of claim 61, wherein the second portion comprises an application element adapted to be implemented using a second processing element.

64. The method of claim 61, wherein the third portion comprises an application element adapted to be implemented using either a first processing element or a second processing element.

65. The method of claim 61, wherein the availability criterion provides that the third portion is to be implemented in a more plentifully available processing element.

66. The method of claim 65, wherein the third portion comprises a plurality of application elements, and the availability criterion is evaluated once for each application element.

67. The method of claim 61, wherein the plurality of first processing elements comprise arithmetic logic units.

68. The method of claim 61, wherein the plurality of second processing elements comprise multiplexers.

69. A heterogeneous reconfigurable array comprising:

a plurality of arithmetic logic units (“

ALU”

), each comprising an ALU output and a plurality of ALU inputs;

a plurality of multiplexers, each comprising a multiplexer control input;

a general-purpose routing network adapted to form connections between selected ones of the plurality of ALUs and plurality of multiplexers, and

a multiplexer control circuit connecting one of the plurality of ALU outputs to one of the plurality of multiplexer control inputs;

wherein the multiplexer control circuit is adapted to derive a multiplexer control signal from one or more ALU output signals.

70. The heterogeneous reconfigurable array of claim 69, wherein the ALU output signal comprises a signal dependent on one or more ALU input signals.

71. The heterogeneous reconfigurable array of claim 70, wherein the ALU output signal comprises an ALU carryout signal.

72. The heterogeneous reconfigurable array of claim 70, wherein the ALU output signal comprises a correct sign signal.

73. The heterogeneous reconfigurable array of claim 70, wherein the ALU output signal comprises an overflow signal.

74. The heterogeneous reconfigurable array of claim 70, wherein the ALU output signal comprises an ALU data input signal.

75. The heterogeneous reconfigurable array of claim 70, wherein the ALU output signal comprises an ALU instruction input signal.

76. The heterogeneous reconfigurable array of claim 70, wherein the ALU output signal comprises a logical combination of an ALU data and an ALU instruction signal.

77. The heterogeneous reconfigurable array of claim 69, wherein the one or more ALU output signals are encoded into an ALU output encoding.

78. The heterogeneous reconfigurable array of claim 69, wherein the multiplexer control circuit is adapted to derive the multiplexer control signal from the one or more ALU output signals and one or more mask values.

79. The heterogeneous reconfigurable array of claim 78, further comprising an external input connected to the multiplexer control circuit, wherein the one or more mask values are used to select the external input for generation of the multiplexer control signal.

80. The heterogeneous reconfigurable array of claim 79, wherein the multiplexer control circuit is one of a plurality of multiplexer control circuits, further comprising a dedicated high-fanout network, wherein the dedicated high-fanout network is connected only to the plurality of multiplexer control circuits.

81. The heterogeneous reconfigurable array of claim 80, wherein the external input is connected from the dedicated high-fanout network to the multiplexer control circuit.

82. The heterogeneous reconfigurable array of claim 80, further comprising a dedicated high-fanout network output connected from the multiplexer control circuit to the dedicated high-fanout network.

83. The heterogeneous reconfigurable array of claim 69, wherein the multiplexer control circuit is one of a plurality of multiplexer control circuits, further comprising a second general purpose routing network, wherein the second general purpose routing network is connected only to the plurality of multiplexer control circuits.

84. The heterogeneous reconfigurable array of claim 83, wherein the external input is connected from the second general purpose routing network to the multiplexer control circuit.

85. The heterogeneous reconfigurable array of claim 83, further comprising an output connection from the multiplexer control circuit to the second general purpose routing network.

86. A reconfigurable array comprising:

a first general purpose routing network comprising a first plurality of input terminals and a first plurality of output terminals;

a second general purpose routing network comprising a second plurality of input terminals and a second plurality of output terminals; and

a plurality of processing elements, each adapted to be connected to at least one terminal belonging to either the first plurality of input terminals, the first plurality of output terminals, the second plurality of input terminals, or the second plurality of output terminals;

87. The reconfigurable array of claim 86, wherein the first general purpose routing network is connected to the second general purpose routing network only by one or more of the plurality of processing elements

88. The reconfigurable array of claim 86, wherein the first general purpose routing network has a first bit width and the second general purpose routing network has a second bit width, the first bit width being different from the second bit width.

89. The reconfigurable array of claim 86, wherein the first general purpose routing network can be configured to create a connection between any of the first plurality of input terminals and the first plurality of output terminals.

90. The reconfigurable array of claim 86, wherein the second general purpose routing network can be configured to create a connection between any of the second plurality of input terminals and the second plurality of output terminals.