Reconfigurable computing architecture for providing pipelined data paths

• US 6,023,742 A
• Filed: 07/18/1997
• Issued: 02/08/2000
• Est. Priority Date: 07/18/1996
• Status: Expired due to Term

• Current Assignee: University of Washington
• Original Assignee: University of Washington
• Inventors: Franklin, Paul David, Ebeling, William Henry Carl, Cronquist, Darren Charles
• Primary Examiner(s): Sheikh, Ayaz R.
• Assistant Examiner(s): PHAN, RAYMOND NGAN
• Application Number:
  US08/897,094
• Time in Patent Office: 935 Days
• Field of Search: 395/285-287, 395/309, 395/290, 395/800.1, 395/800.11, 395/800.15, 395/800.16, 395/800.21, 395/800.22, 395/800.36, 710/129, 710/131, 712/17
• US Class Current: 710/107
• CPC Class Codes: G06F 15/7867 with reconfigurable architecture
• CPC Class Codes: G06F 9/30036 Instructions to perform operations on packed data, e.g. vector, tile or matrix operations
• CPC Class Codes: Y02D 10/00 Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

A configurable computing architecture (10) has its functionality controlled by a combination of static and dynamic control, wherein the configuration is referred to as static control and instructions are referred to as dynamic control. A reconfigurable data path (12) has a plurality of elements including functional units (32, 36), registers (30), and memories (34) whose interconnection and functionality is determined by a combination of static and dynamic control. These elements are connected together, using the static configuration, into a pipelined data path that performs a computation of interest. The dynamic control signals (21) are suitably used to change the operation of a functional unit and the routing of signals between functional units. The static control signals (23) are provided each by a static memory cell (62) that is written by a host (13). The controller (14) generates control instructions (16) that are interpreted by a control path (18) that computes the dynamic control signals. The control path is configured statically for a given application to perform the appropriate interpretation of the instructions generated by the controller. By using a combination of static and dynamic control information, the amount of dynamic control used to achieve flexible operation is significantly reduced.

Claims

1. A reconfigurable computing architecture for executing a plurality of applications, each application being executed over a plurality of execution cycles, the architecture comprising:

a plurality of functional units that are interconnectably arranged to perform a plurality of functions on data, the data comprising a plurality of bits;

a plurality of interconnectors that selectably interconnect the functional units to control the flow of data between the functional units;

a set of first signals generated to create a state that remains unchanged over the execution cycles of any one of the applications;

a set of second signals generated to create a plurality of states that are changeable over the execution cycles; and

an input and an output for data, wherein the function being performed on the data by the functional units is selectable by the first signals and the second signals and the interconnectors are arranged in a single dimension to transport the data from the input and to the output and to provide the data to the functional units, the interconnectors interconnect the functional units such that the flow of the data between the functional units is selectable.

2. The computing architecture of claim 1, wherein the interconnectors include a plurality of rows of buses.

3. The computing architecture of claim 2, wherein the buses include a plurality of interconnected segmented buses.

4. The computing architecture of claim 3, wherein the segmented buses are interconnected by a plurality of bus connectors that transfer the data between the interconnected segmented buses.

5. The computing architecture of claim 4, wherein the bus connectors are controlled in response to the set of first signals.

6. The computing architecture of claim 4, wherein the bus connectors are controlled in response to the set of second signals.

7. The computing architecture of claim 4, wherein the bus connectors are controlled in response to the set of first signals and the set of second signals.

8. The computing architecture of claim 4, wherein the bus connectors include registers.

9. The computing architecture of claim 2, wherein each functional unit has an input terminal, and wherein the interconnectors further include a plurality of multiplexers, the multiplexers connecting the input terminals of the functional units to the buses.

10. The computing architecture of claim 9, wherein the multiplexers are coupled to receive the second signals, the multiplexers selecting the buses for connection to the functional units in response to the second signals.

11. The computing architecture of claim 9, wherein the multiplexers are coupled to receive the first signals, the multiplexers selecting the buses for connection to the functional units in response to the first signals.

12. The computing architecture of claim 9, wherein the multiplexers are coupled to receive the first and second signals, the multiplexers selecting the buses for connection to the functional units in response to the first and second signals.

13. The computing architecture of claim 2, wherein each functional unit has an output terminal, and wherein the interconnectors further include a plurality of switches, the switches connecting the output terminals of the functional units to the buses.

14. The computing architecture of claim 13, wherein the switches are coupled to receive the first signals, the switches selecting the buses for connection to the functional units in response to the first signals.

15. The computing architecture of claim 13, wherein the switches are coupled to receive the second signals, the switches selecting the buses for connection to the functional units in response to the second signals.

16. The computing architecture of claim 13, wherein the switches are coupled to receive the first and second signals, the switches selecting the buses for connection to the functional units in response to the first and second signals.

17. The computing architecture of claim 1, wherein the function performed by the functional unit is selectable by the first signal.

18. The computing architecture of claim 1, wherein the function performed by the functional unit is selectable by the second signal.

19. The computing architecture of claim 1, wherein the function performed by the functional unit is selectable by the first and second signals.

20. The computing architecture of claim 1, wherein the functional units include a multiplier.

21. The computing architecture of claim 1, wherein the functional units include an arithmetic logic unit.

22. The computing architecture of claim 1, wherein the functional units include a memory cell array.

23. The computing architecture of claim 1, wherein the functional units include a register.

24. The computing architecture of claim 1, wherein the functional units include a general purpose configurable unit.

25. The computing architecture of claim 1, wherein the functional units provide a set of third signals for use in generating the set of second signals.

26. The computing architecture of claim 1, wherein the first signals are stored in a plurality of memory cells, the memory cells being coupled to provide the first signals to the functional units.

27. The computing architecture of claim 1, wherein the first signals are stored in a plurality of memory cells, the memory cells being coupled to provide the first signals to the interconnectors.

53. The computing architecture of claim 1, wherein the data comprises at least 4 bits.

28. A reconfigurable computing architecture for executing a plurality of applications, each application being executed over a plurality of execution cycles, the architecture comprising:

means for generating a set of first signals having a state that remains unchanged over the execution cycles of any one of the applications;

means for generating a set of instructions having states that are changeable over the execution cycles;

a linear array of interpreters that receive the set of instructions and provide a set of second signals having states that are changeable over the execution cycles;

means for interconnecting the interpreters;

means for inputting and outputting data;

a linear array of interconnectable functional units, each functional unit being arranged to perform a plurality of functions on the data, the function being performed on the data by the functional units being selectable by the first signals and the second signals; and

means for interconnecting the functional units that are arranged in a single dimension to transport the data between the input and output means and to provide the data to the functional units, the functional units being interconnected by the means for interconnecting the functional units such that the flow of data between the functional units is selectable, wherein the data operated on by the functional units comprises a plurality of bits.

29. The computing architecture of claim 28, wherein the means for interconnecting the interpreters include a plurality of rows of control buses.

30. The computing architecture of claim 29, wherein the buses include a plurality of interconnected segmented control buses.

31. The computing architecture of claim 30, wherein the segmented control buses are interconnected by a plurality of control bus connectors.

32. The computing architecture of claim 31, wherein the control bus connectors include registers.

33. The computing architecture of claim 31, wherein the control bus connectors are controlled in response to the set of first signals.

34. The computing architecture of claim 28, wherein each interpreter includes means for generating an output signal.

35. The computing architecture of claim 34, wherein the output signal-generating means generates the set of second signals.

36. The computing architecture of claim 34, wherein the output signal-generating means includes an input terminal coupled to receive an input signal, the output signal being selected from a group of signals consisting of the input signal, a logic complement of the input signal, a logic zero, and a logic 1.

37. The computing architecture of claim 36, wherein the output signal-generating means includes a lookup table.

38. The computing architecture of claim 37, wherein the lookup table includes a one-input lookup table.

39. The computing architecture of claim 29, wherein each interpreter includes means for generating an output signal.

40. The computing architecture of claim 39, wherein the output signal-generating means includes an input terminal, and wherein the means for interconnecting the interpreters further includes a plurality of multiplexers, the multiplexers connecting the input terminals of the output signal-generating means to the control buses.

41. The computing architecture of claim 39, wherein the means for generating the output signal has an output terminal, and wherein the means for interconnecting the control buses further includes a plurality of switches, the switches connecting the output terminals of the output signal-generating means to the control buses.

42. The computing architecture of claim 34, wherein each output signal generating means includes an input terminal and an output terminal, the input terminal of one of the output signal generating means being coupled to the output terminal of a different output signal generating means.

43. The computing architecture of claim 34, wherein the output signal-generating means includes a lookup table.

44. The computing architecture of claim 43, wherein the lookup table is a three-input lookup table.

45. The computing architecture of claim 34, wherein the output signal-generating means are controlled by the first signals.

46. The computing architecture of claim 28, wherein the functional units provide a set of third signals to the interpreters.

47. The computing architecture of claim 28, wherein the means for generating the set of instructions includes a processor.

48. The architecture of claim 28, wherein the means for generating the set of instructions includes an array of memory cells.

49. A method of mapping a computational application to a reconfigurable computing architecture for executing a plurality of applications, each application being executed over a plurality of execution cycles, the architecture including means for generating a set of first signals having a state that remains unchanged over the execution cycles of any one of the applications;

means for generating a set of instructions having states that are changeable over the execution cycles;

a linear array of interpreters that receive the set of instructions and provide a set of second signals having states that are changeable over the execution cycles;

means for interconnecting the interpreters;

means for inputting and outputting data;

a linear array of interconnectable functional units, each functional unit being arranged to perform a plurality of functions on the data, the function being performed on the data by the array being selectable by the first signals and the second signals; and

means for interconnecting the functional units that are arranged to receive the data from the input and output means and to provide the data to the functional units, the functional units being interconnected by the means for interconnecting the functional units such that the flow of data between the functional units is selectable, the method comprising;

specifying a number of computational stages to map to the array;

specifying a control tree that represents execution cycles within the application;

specifying a computation to be mapped to the stages;

converting the computation specification to a specification of the interconnected functional units, the second control signals being labeled with a set of the first expressions derived from variables in the control tree;

generating a set of second expressions from the set of first expressions, the second expressions representing the set of instructions that are input to the interpreters;

generating a configuration of the interpreters for enabling the interpreters to convert the second expressions into the first expressions; and

generating the configuration of the remaining signals in the first set.

50. The method of claim 49, further comprising revising the specification of interconnected functional units.

51. The method of claim 50, wherein revising the specification of interconnected functional units adds registers to the specification of interconnected functional units.

52. The method of claim 50, wherein revising the specification of interconnected functional units deletes registers from the specification of interconnected functional units.

54. A reconfigurable computing architecture for executing a plurality of applications, each application being executed over a plurality of execution cycles, the architecture comprising:

means for generating a set of first signals having a state that remains unchanged over the execution cycles of any one of the applications;

means for generating a set of second signals having states that are changeable over the execution cycles;

means for inputting and outputting data;

a linear array of interconnectable functional units, each functional unit being arranged to perform a plurality of functions on the data, the function being performed on the data by the functional units is selectable by the first signals and the second signals; and

means for interconnecting the functional units, the interconnecting means being arranged to transport the data between the input and output means and to provide the data to the functional units, the interconnecting means interconnecting the functional units such that flow of the data between the functional units is selectable,

wherein each functional unit has an input terminal and wherein the interconnecting means include a plurality of rows of buses and a plurality of multiplexers, the multiplexers connecting the input terminals of the functional units to the buses.

55. The computing architecture of claim 54, wherein the multiplexers are coupled to receive the second signals, the multiplexers selecting the buses for connection to the functional units in response to the second signals.

56. The computing architecture of claim 54, wherein the multiplexers are coupled to receive the first signals, the multiplexers selecting the buses for connection to the functional units in response to the first signals.

57. The computing architecture of claim 54, wherein the multiplexers are coupled to receive the first and second signals, the multiplexers selecting the buses for connection to the functional units in response to the first and second signals.

58. A reconfigurable computing architecture for executing a plurality of applications, each application being executed over a plurality of execution cycles, the architecture comprising:

means for generating a set of first signals having a state that remains unchanged over the execution cycles of any one of the applications;

means for generating a set of second signals having states that are changeable over the execution cycles;

means for inputting and outputting data;

a linear array of interconnectable functional units, each functional unit being arranged to perform a plurality of functions on the data, the function being performed on the data by the functional units is selectable by the first signals and the second signals; and

means for interconnecting the functional units, the interconnecting means being arranged to transport the data between the input and output means and to provide the data to the functional units, the interconnecting means interconnecting the functional units such that flow of the data between the functional units is selectable, wherein each functional unit has an output terminal and wherein the interconnecting means include a plurality of rows of buses and a plurality of switches, the switches connecting the output terminals of the functional units to the buses.

59. The computing architecture of claim 58, wherein the switches are coupled to receive the first signals, the switches selecting the buses for connection to the functional units in response to the first signals.

60. The computing architecture of claim 58, wherein the switches are coupled to receive the second signals, the switches selecting the buses for connection to the functional units in response to the second signals.

61. The computing architecture of claim 58, wherein the switches are coupled to receive the first and second signals, the switches selecting the buses for connection to the functional units in response to the first and second signals.

62. A reconfigurable computing architecture for executing a plurality of applications, each application being executed over a plurality of execution cycles, the architecture comprising:

means for generating a set of first signals having a state that remains unchanged over the execution cycles of any one of the applications;

means for generating a set of instructions having states that are changeable over the execution cycles;

a linear array of interpreters that receive the set of instructions and provide a set of second signals having states that are changeable over the execution cycles;

means for interconnecting the interpreters;

means for inputting and outputting data;

a linear array of interconnectable functional units, each functional unit being arranged to perform a plurality of functions on the data, the function being performed on the data by the functional units is selectable by the first signals and the second signals; and

means for interconnecting the functional units that are arranged to transport the data between the input and output means and to provide the data to the functional units, the functional units being interconnected by the means for interconnecting the functional units such that the flow of data between the functional units is selectable, wherein each interpreter includes means for generating an output signal and the output signal-generating means generates the set of second signals.

63. A reconfigurable computing architecture for executing a plurality of applications, each application being executed over a plurality of execution cycles, the architecture comprising:

means for generating a set of first signals having a state that remains unchanged over the execution cycles of any one of the applications;

means for generating a set of instructions having states that are changeable over the execution cycles;

a linear array of interpreters that receive the set of instructions and provide a set of second signals having states that are changeable over the execution cycles;

means for interconnecting the interpreters;

means for inputting and outputting data;

a linear array of interconnectable functional units, each functional unit being arranged to perform a plurality of functions on the data, the function being performed on the data by the functional units is selectable by the first signals and the second signals; and

means for interconnecting the functional units that are arranged to transport the data between the input and output means and to provide the data to the functional units, the functional units being interconnected by the means for interconnecting the functional units such that the flow of data between the functional units is selectable, wherein each interpreter includes means for generating an output signal and the output signal-generating means includes an input terminal coupled to receive an input signal, the output signal being selected from a group of signals consisting of the input signal, a logic complement of the input signal, a logic zero, and a logic 1.

64. The computing architecture of claim 63, wherein the output signal-generating means includes a lookup table.

65. The computing architecture of claim 64, wherein the lookup table includes a one-input lookup table.

66. A reconfigurable computing architecture for executing a plurality of applications, each application being executed over a plurality of execution cycles, the architecture comprising:

means for generating a set of first signals having a state that remains unchanged over the execution cycles of any one of the applications;

means for generating a set of instructions having states that are changeable over the execution cycles;

a linear array of interpreters that receive the set of instructions and provide a set of second signals having states that are changeable over the execution cycles;

means for interconnecting the interpreters;

means for inputting and outputting data;

a linear array of interconnectable functional units, each functional unit being arranged to perform a plurality of functions on the data, the function being performed on the data by the functional units is selectable by the first signals and the second signals; and

means for interconnecting the functional units that are arranged to transport the data between the input and output means and to provide the data to the functional units, the functional units being interconnected by the means for interconnecting the functional units such that the flow of data between the functional units is selectable, wherein the means for interconnecting the interpreters include a plurality of rows of control buses and each interpreter includes means for generating an output signal.

67. The computing architecture of claim 66, wherein the output signal-generating means includes an input terminal, and wherein the means for interconnecting the interpreters further includes a plurality of multiplexers, the multiplexers connecting the input terminals of the output signal-generating means to the control buses.

68. The computing architecture of claim 66, wherein the means for generating the output signal has an output terminal, and wherein the means for interconnecting the control buses further includes a plurality of switches, the switches connecting the output terminals of the output signal-generating means to the control buses.

69. A reconfigurable computing architecture for executing a plurality of applications, each application being executed over a plurality of execution cycles, the architecture comprising:

means for generating a set of first signals having a state that remains unchanged over the execution cycles of any one of the applications;

means for generating a set of instructions having states that are changeable over the execution cycles;

a linear array of interpreters that receive the set of instructions and provide a set of second signals having states that are changeable over the execution cycles;

means for interconnecting the interpreters;

means for inputting and outputting data;

a linear array of interconnectable functional units, each functional unit being arranged to perform a plurality of functions on the data, the function being performed on the data by the functional units is selectable by the first signals and the second signals; and

means for interconnecting the functional units that are arranged to transport the data between the input and output means and to provide the data to the functional units, the functional units being interconnected by the means for interconnecting the functional units such that the flow of data between the functional units is selectable, wherein each interpreter includes means for generating an output signal and each output signal generating means includes an input terminal and an output terminal, the input terminal of one of the output signal generating means being coupled to the output terminal of a different output signal generating means.

70. A reconfigurable computing architecture for executing a plurality of applications, each application being executed over a plurality of execution cycles, the architecture comprising:

means for generating a set of first signals having a state that remains unchanged over the execution cycles of any one of the applications;

means for generating a set of instructions having states that are changeable over the execution cycles;

a linear array of interpreters that receive the set of instructions and provide a set of second signals having states that are changeable over the execution cycles;

means for interconnecting the interpreters;

means for inputting and outputting data;

a linear array of interconnectable functional units, each functional unit being arranged to perform a plurality of functions on the data, the function being performed on the data by the functional units is selectable by the first signals and the second signals; and

means for interconnecting the functional units that are arranged to transport the data between the input and output means and to provide the data to the functional units, the functional units being interconnected by the means for interconnecting the functional units such that the flow of data between the functional units is selectable, wherein each interpreter includes means for generating an output signal and the output signal-generating means includes a lookup table.

71. The reconfigurable computing architecture of claim 70, wherein the lookup table is a three-input lookup table.

72. A reconfigurable computing architecture for executing a plurality of applications, each application being executed over a plurality of execution cycles, the architecture comprising:

means for generating a set of first signals having a state that remains unchanged over the execution cycles of any one of the applications;

means for generating a set of instructions having states that are changeable over the execution cycles;

a linear array of interpreters that receive the set of instructions and provide a set of second signals having states that are changeable over the execution cycles;

means for interconnecting the interpreters;

means for inputting and outputting data;

a linear array of interconnectable functional units, each functional unit being arranged to perform a plurality of functions on the data, the function being performed on the data by the functional units is selectable by the first signals and the second signals; and

means for interconnecting the functional units that are arranged to transport the data between the input and output means and to provide the data to the functional units, the functional units being interconnected by the means for interconnecting the functional units such that the flow of data between the functional units is selectable, wherein each interpreter includes means for generating an output signal and the output signal-generating means are controlled by the first signals.

73. A method of mapping a computational program to a reconfigurable computing architecture configured for executing one of a plurality of applications, each application being executed over a plurality of execution cycles, the method comprising:

specifying a plurality of computational stages to map to the architecture, each computational stage corresponding to one execution cycle;

specifying a control tree that represents all computations to be perform for every execution cycle for each stage within the program, the control list including expressions;

specifying a computation for each of the computational stages based on the expressions in the control tree for that execution cycle;

converting the computation specification to a listing that specifies an arrangement for interconnecting a plurality of functional units in a linear array and that specifies a set of second control signals derived from the control tree, the second control signals providing dynamic controls to change the state during an execution cycle;

generating a set of second expressions that enable a plurality of interpreters to generate dynamic control signals;

generating a set of control instructions that specify the second expression for input to the interpreters for each execution cycle of the control tree;

determining a configuration of the interpreters; and

pipelining the listing to adhere to the architecture, wherein pipelining includes generating static control signals for a part of the list that does not vary, these static control signals being loaded into the architecture to define an application on which the dynamic portion of the program is executed.

74. The method of claim 73, further comprising revising the list of interconnected functional units.

75. The method of claim 73, wherein revising the list of interconnected functional units adds registers to the list of interconnected functional units.

76. The method of claim 73, wherein revising the list of interconnected functional units deletes registers from the list of interconnected functional units.