PROGRAMMABLE DEVICE, HEIRARCHICAL PARALLEL MACHINES, METHODS FOR PROVIDING STATE INFORMATION

• US 20110307433A1
• Filed: 03/01/2011
• Published: 12/15/2011
• Est. Priority Date: 06/10/2010
• Status: Active Grant

• Current Assignee: Micron Technology, Inc.
• Original Assignee: Micron Technology, Inc.
• Inventors: Dlugosch, Paul
• Granted Patent: US 8,766,666 B2
• Time in Patent Office: Days
• US Class Current: 706/45
• CPC Class Codes: G06F 11/3024 where the computing system component is a central processing unit [CPU]
• CPC Class Codes: G06F 11/3409 for performance assessment
• CPC Class Codes: G06F 15/17312 Routing techniques specific to parallel machines, e.g. wormhole, store and forward, shortest path problem congestion routing on a LAN H04L45/00
• CPC Class Codes: G06F 15/17362 hierarchical topologies
• CPC Class Codes: G06F 15/825 Dataflow computers
• CPC Class Codes: G06F 9/544 Buffers; Shared memory; Pipes
• CPC Class Codes: G06N 5/02 Knowledge representation; Symbolic representation

Abstract

Programmable devices, hierarchical parallel machines and methods for providing state information are described. In one such programmable device, programmable elements are provided. The programmable elements are configured to implement one or more finite state machines. The programmable elements are configured to receive an N-digit input and provide a M-digit output as a function of the N-digit input. The M-digit output includes state information from less than all of the programmable elements. Other programmable devices, hierarchical parallel machines and methods are also disclosed.

Claims

1. A programmable device comprising:

a plurality of programmable elements, wherein the programmable elements are configured to implement one or more finite state machines, wherein the plurality of programmable elements are configured to receive a N-digit input and provide a M-digit output as a function of the N-digit input, wherein the M-digit output includes state information from less than all of the programmable elements.

2. The programmable device of claim 1, wherein the plurality of programmable elements comprises one of two or more groups of programmable elements.

3. The programmable device of claim 2, further comprising:

a N-digit input interface coupled to the one group of programmable elements and configured to receive the N-digit input; and

a M-digit output interface coupled to the one group of programmable elements and configured to provide the M-digit output.

4. The programmable device of claim 2, wherein the one group of programmable elements comprises a block of programmable elements.

5. The programmable device of claim 4, wherein the block of programmable elements comprises a plurality of rows of programmable elements, wherein each of the rows is coupled to a respective one of a plurality of intra-block switches.

6. The programmable device of claim 5, wherein the programmable elements in each of the rows comprises:

a plurality of groups of two state machine elements; and

another programmable element.

7. The programmable device of claim 2, further comprising:

a programmable switch configured to selectively couple the one group of programmable elements to another one of the groups of programmable elements, an input port, and/or an output port.

8. The programmable device of claim 7, further comprising:

a register configured to store a program configured to program the plurality of programmable elements and the plurality of programmable switches.

9. The programmable device of claim 1, wherein N equals M.

10. The programmable device of claim 1, wherein M is an integer multiple of N.

11. The programmable device of claim 1, further comprising:

OR logic configured to aggregate output from two or more of the programmable elements used to implement a same one of the finite state machines.

12. The programmable device of claim 11, wherein the programmable elements are configured to implement a logical group of N state machines, wherein the outputs of the N state machines are aggregated to provide the M-digit output.

13. The programmable device of claim 11, wherein the logic comprises an OR gate.

14. The programmable device of claim 1, wherein the state information included in the M-digit output comprises compressed state information.

15. The programmable device of claim 1, wherein the plurality of programmable elements comprise state machine elements.

16. The programmable device of claim 1, wherein the M-digit output comprises a difference vector.

17. The programmable device of claim 16, wherein each state in the implemented one or more finite state machines corresponds to a respective digit in a state vector, and wherein the difference vector includes only those digits in the state vector that change in response to an input symbol provided to the programmable device.

18. The programmable device of claim 1, wherein each state in the implemented one or more finite state machines corresponds to a respective digit in a state vector, and wherein the M-digit output comprises only a subset of the digits in the state vector.

19. The programmable device of claim 1, wherein the subset of the digits comprises those digits corresponding to final states in the one or more finite state machines.

20. The programmable device of claim 1, wherein all state machines implemented in the device receive the N-digit input.

21. The programmable device of claim 1, wherein the plurality of programmable elements comprise one of two or more groups of programmable elements, wherein each of the groups has its own dedicated input.

22. The programmable device of claim 1, wherein the N-digit input is on a bottom of a semiconductor die, and wherein the M-digit output is on a top of the semiconductor die.

23. The programmable device of claim 1, wherein the plurality of programmable elements comprise one of two or more groups of programmable elements, and wherein the programmable device is configured to provide state information from one of the groups to another one of the groups in the programmable device.

24. A hierarchical parallel machine, comprising:

a first parallel machine comprising a plurality of programmable elements, wherein the programmable elements are configured to implement one or more finite state machines, wherein the plurality of programmable elements are configured to receive a N-digit input and provide a M-digit output as a function of the N-digit input, wherein the M-digit output includes state information from less than all of the programmable elements; and

a second parallel machine configured to receive and process at least part of the M-digit output.

25. The hierarchical parallel machine of claim 24, wherein the second parallel machine is configured to receive and process the whole M-digit output.

26. The hierarchical parallel machine of claim 24, further comprising:

an input bus coupled to the first parallel machine and configured to provide the N-digit input; and

an output bus coupled between the first parallel machine and the second parallel machine, the output bus being configured to provide at least part of the M-digit output to the second parallel machine.

27. The hierarchical parallel machine of claim 26, wherein the input bus and output bus are equal in size.

28. The hierarchical parallel machine of claim 27, wherein the corresponding groups in the first and second parallel machines are coupled by a respective group of interconnects.

29. The hierarchical parallel machine of claim 24, wherein the M-digit output is provided to each state machine implemented in the second parallel machine.

30. The hierarchical parallel machine of claim 24, wherein the second parallel machine comprises a plurality of programmable elements grouped into a plurality of groups, wherein the M-digit output is provided to a respective one of the groups according to a pre-defined manner.

31. The hierarchical parallel machine of claim 24, wherein the second parallel machine comprises a plurality of programmable elements configured to send address information to the second parallel machine, wherein the address information indicates to which of the groups in the second parallel machine the M-digit output is being provided.

32. The hierarchical parallel machine of claim 24, wherein the parallel machines are stacked.

33. The hierarchical parallel machine of claim 24, wherein the plurality of programmable elements comprise one of two or more groups of programmable elements, further comprising logic corresponding to each group, wherein the logic corresponding to a respective one of the groups aggregates state information from two or more programmable elements in that group, and wherein one or more digits of the M-digit output from that group is a function of such logic.

34. The hierarchical parallel machine of claim 24, wherein the M-digit output is formed by compressing state information from the programmable elements.

35. A programmable device comprising:

a plurality of programmable elements wherein the programmable elements are configured to implement one or more finite state machines, wherein the plurality of programmable elements are configured to receive a N-digit input and provide a M-digit output as a function of the N-digit input, wherein the M-digit output is formed by compressing state information from each of the programmable elements.

36. The programmable device of claim 35, wherein N equals M.

37. The programmable device of claim 35, wherein M is an integer multiple of N.

38. The programmable device of claim 35, further comprising:

logic configured to aggregate output from two or more of the programmable elements used to implement a same one of the finite state machines.

39. The programmable device of claim 38, wherein the programmable elements are configured to implement a logical group of N state machines, wherein the outputs of the N state machines are aggregated to provide the M-digit output.

40. A hierarchical parallel machine, comprising:

a first parallel machine comprising a plurality of programmable elements, wherein the programmable elements are configured to implement one or more finite state machines, wherein the plurality of programmable elements are configured to receive a N-digit input and provide a M-digit output as a function of the N-digit input, wherein the M-digit output is formed by compressing state information from each of the programmable elements.

41. The hierarchical parallel machine of claim 40, wherein N equals M.

42. The hierarchical parallel machine of claim 40, wherein M is an integer multiple of N.

43. A method of providing state information from a parallel machine to another device, wherein the parallel machine includes a plurality of programmable elements, wherein each of the programmable elements is configured to have a corresponding state, comprising:

determining state information, wherein the state information comprises the state of each of the programmable elements in the parallel machine;

compressing the state information; and

providing the compressed state information to the other device.

44. The method of claim 43, wherein compressing the state information includes applying a lossless compression algorithm to the state information.

45. The method of claim 43, wherein providing the compressed state information to the other device comprises providing the compressed state information to another parallel machine.

46. The method of claim 43, wherein providing the compressed state information to the other device comprises providing the compressed state information to system memory.

47. The method of claim 43, wherein compressing the state information comprises aggregating final states in a finite state machine implemented on the parallel machine.

48. A hierarchical parallel machine, comprising:

a first level parallel machine having at least one N-digit input and a plurality of N-digit outputs, wherein each of the N-digit outputs corresponds to a respective group of N state machines implemented on the first level parallel machine.

49. The hierarchical parallel machine of claim 48, wherein at least one of the state machines implemented on the first level parallel machine includes a plurality of programmable elements corresponding to a plurality of final states of the at least one state machine, wherein the output of the plurality of programmable elements corresponding to the plurality of final states are aggregated together to provide one digit of one of the N-digit outputs.

50. The hierarchical parallel machine of claim 48, wherein data provided on one of the N-digit outputs encodes the status of the final states for the respective group of N state machines implemented on the first level parallel machine.

51. The hierarchical parallel machine of claim 48, wherein the first level parallel machine comprises a finite state machine engine.

52. The hierarchical parallel machine of claim 51, wherein the finite state machine engine comprises an array of groups of programmable elements, and wherein each of the groups of programmable elements is coupled to a respective one of the N-digit outputs.

53. The hierarchical parallel machine of claim 52, wherein the first level parallel machine has a plurality of N-digit input and wherein each of the groups of programmable elements is coupled to a respective one of the N-digit inputs of the first level parallel machine.

54. The hierarchical parallel machine of claim 48, wherein the second level parallel machine comprises a finite state machine engine.

55. The hierarchical parallel machine of claim 54, wherein the finite state machine engine comprises an array of groups of programmable elements, and wherein each of the groups of programmable elements is coupled to a respective one of the N-digit inputs.

56. The hierarchical parallel machine of claim 55, wherein the second level parallel machine has a plurality of N-digit outputs and wherein each of the groups of programmable elements is coupled to a respective one of the N-digit output of the second level parallel machine.

57. The hierarchical parallel machine of claim 48, wherein the first parallel machine comprises a first die, and the second parallel machine comprises a second die stacked with the first die.

58. The hierarchical parallel machine of claim 57, further comprising a third parallel machine and a bus, wherein the third parallel machine comprises a third dies stacked with the first die and the second die, wherein the second die is between the first die and the third die in the stack, and wherein the bus is configured to transfer state information between the first parallel machine and the third parallel machine.

59. The hierarchical parallel machine of claim 58, wherein the bus comprises a plurality of interconnects.

60. The hierarchical parallel machine of claim 59, wherein the interconnects comprise through via interconnects.

61. The hierarchical parallel machine of claim 48, wherein the parallel machines comprise finite state machine engines.

62. The hierarchical parallel machine of claim 61, wherein the finite state machine engines comprise pattern recognition processors.

63. The hierarchical parallel machine of claim 48, wherein the parallel machines comprise field programmable gate arrays.

64. The hierarchical parallel machine of claim 48, wherein the at least one N-digit input of the first level parallel machine is configured to receive raw data.

65. The hierarchical parallel machine of claim 48, wherein each of the N-digit inputs of the second level parallel machine correspond to a respective group of N state machines implemented on the second level parallel machine, wherein each group of N state machines implemented on the second level parallel machine is driven by up to N state machines implemented on the first level parallel machine.

66. A parallel machine comprising a plurality of programmable elements configured to implement at least one finite state machine, wherein the parallel machine is configured to:

determine state information, wherein the state information comprises the state of each of the programmable elements;

compress the state information; and

provide the compressed state information to another device.

67. The parallel machine of claim 66, wherein the other device comprises a second parallel machine, wherein the second parallel machine is configured to receive and process the compressed state information.

68. The parallel machine of claim 66, wherein the parallel machine being configured to compress the state information comprises the parallel machine being configured to aggregate final states of a finite state machine implemented on the parallel machine.

69. The parallel machine of claim 68, further comprising Boolean logic configured to aggregate the final states.

70. The parallel machine of claim 66, wherein the parallel machine being configured to compress the state information comprises the parallel machine being configured to output a difference vector, wherein the difference vector identifies only those states that have changed in response to an input symbol.

71. The parallel machine of claim 66, wherein the parallel machine being configured to compress the state information comprises the parallel machine being configured to output an output vector, wherein the output vector only provides state information for final states in a finite state machine implemented on the parallel machine.