Granted Patent B2

US 12,197,510 · App. 15/692,972 · Granted Jan 14, 2025

Inventor: Jeffery M. Tanner (Boise, ID)

Assignee: Micron Technology, Inc.

G06F16/90344G06F9/4498G06F16/248G06F16/9024H04L67/10

Abstract

Claims (74)

1. A state machine engine, comprising:

a plurality of configurable elements programmed to correspond to a graph problem to be solved, wherein the graph problem to be solved comprises a determination of a shortest path from a plurality of paths corresponding to whether a target node as a first configurable element of the plurality of configurable elements is reachable from an origin node as a second configurable element of the plurality of configurable elements, wherein the shortest path between the origin node and the target node from the plurality of paths is determined upon determining that the target node is reachable from the origin node by:

(a) the state machine engine receiving a list of nodes as a query string from a processor, wherein the query string is at least a part of an input data stream transmitted to the state machine engine, wherein each node of the list of nodes corresponds to a respective character of a set of characters;

(b) each automaton comprising a portion of the plurality of configurable elements within the state machine engine evaluating whether or not it contains an edge that originates on one of the nodes in the query string;

(c) when an automaton does match this condition, reporting via the automaton a destination node of an edge it represents, wherein the destination node corresponds to a first character of the set of characters, to allow the processor to begin at any arbitrary node as the origin node to determine what nodes can be reached from the origin node;

(d) returning a list of nodes that can be reached from a set of query nodes as the origin node and/or additionally provided nodes from the state machine engine to the processor as destination nodes having a corresponding level associated with a maximum number of hops undertaken to reach the destinations nodes;

(e) utilizing a set of one-hop reachable nodes to deliver to the state machine engine as a new query for analysis;

(f) porting from the state machine engine a set of nodes reachable from the one-hop reachable nodes as representative of two-hop reachable nodes; and

(g) discovering new nodes reachable at increasingly greater distances from the origin node until the processor finds the target node within a result set or the state machine engine returns an empty result set indicating the target node is not reachable from the origin node; and

wherein, each configurable element of the plurality of configurable elements comprising a state transition element (STE) comprising a memory cell programmed with configuration data to selectively set a state of the memory cell to a binary high value or a binary low value, wherein the STE is configured to analyze at least a portion of the input data stream based on the state of the memory cell and to output a result of the analysis as an event representative of a satisfaction of traversal of a portion of the graph problem to be solved based on the at least a portion of the input data stream, wherein the STE is configured to represent a node of a graph edge as the portion of the graph problem to be solved, wherein the STE evaluates the at least a portion of the input data stream to determine whether the node matches the at least a portion of the input data stream, wherein the STE is configured to report the node of the graph edge as the result of the analysis upon an occurrence of the node of the graph edge matching the at least a portion of the input data stream.

2. The state machine engine of claim 1 , wherein the STE is configured to report the event representative of the satisfaction of traversal of the portion of the graph problem to be solved based on a match of the at least a portion of the input data stream with a stored value as the state of the memory cell.

3. The state machine engine of claim 1 , wherein the STE is configured to report only one instance of the event representative of the satisfaction of traversal of the portion of the graph problem to be solved.

4. The state machine engine of claim 1 , comprising a second STE, wherein the second STE comprises a second memory cell programmed with second configuration data to selectively set a state of the second memory cell to a binary high value or a binary low value, wherein the second STE is configured to analyze at least a second portion of the input data stream based on the state of the second memory cell and to output a second result of the analysis as an event representative of a satisfaction of a traversal of a second portion of the graph problem to be solved based on the second portion of the input data stream.

5. The state machine engine of claim 1 , wherein the STE is configured to report the event representative of the satisfaction of traversal of the portion of the graph problem to be solved to a host device coupled to the state machine engine.

6. The state machine engine of claim 1 , wherein the STE is configured to analyze the at least a portion of the input data stream to match a character present in the input data stream with a programmed value as the configuration data of the STE.

7. The state machine engine of claim 1 , wherein at least one configurable element of the plurality of configurable elements is utilized in analysis of the input data stream until an end of data signal is received.

8. The state machine engine of claim 1 , wherein the STE is configured to report the event when an end of data signal in the input data stream is received.

9. A device, comprising:

a processor when in operation transmits an input data stream to be analyzed by a plurality of configurable elements programmed to correspond to a graph problem to be solved, wherein the graph problem to be solved comprises a determination of a shortest path from a plurality of paths corresponding to whether a target node as a first configurable element of the plurality of configurable elements is reachable from an origin node as a second configurable element of the plurality of configurable elements, wherein the shortest path between the origin node and the target node from the plurality of paths is determined upon determining that the target node is reachable from the origin node by:

(a) a state machine engine comprising the plurality of configurable elements receiving a list of nodes as a query string from the processor, wherein the query string is at least a part of the input data stream transmitted to the state machine engine, wherein each node of the list of nodes corresponds to a character;

(b) each automaton comprising a portion of the plurality of configurable elements within the state machine engine evaluating whether or not it contains an edge that originates on one of the nodes in the query string;

(c) when an automaton does match this condition, reporting via the automaton a destination node of an edge it represents, wherein the destination node corresponds to a first character of a set of characters, to allow the processor to begin at any arbitrary node as the origin node to determine what nodes can be reached from the origin node;

(d) returning a list of nodes that can be reached from a set of query nodes as the origin node and/or additionally provided nodes from the state machine engine to the processor as destination nodes having a corresponding level associated with a maximum number of hops undertaken to reach the destinations nodes;

(e) utilizing a set of one-hop reachable nodes to deliver to the state machine engine as a new query for analysis;

(f) reporting from the state machine engine a set of nodes reachable from the one-hop reachable nodes as representative of two-hop reachable nodes; and

(g) discovering new nodes reachable at increasingly greater distances from the origin node until the processor finds the target node within a result set or the state machine engine returns an empty result set indicating the target node is not reachable from the origin node; and

wherein, each configurable element of the plurality of configurable elements comprising a state transition element (STE) comprising a memory element programmed with configuration data to selectively set a data state of the memory element as one of a high state and a low state, wherein the STE is configured to analyze at least a portion of the input data stream based on the data state of the memory element and to output a result of the analysis as an event, wherein the STE is configured to represent a node of a graph edge as the portion of the graph problem to be solved, wherein the STE evaluates the at least a portion of the input data stream to determine whether the node matches the at least a portion of the input data stream, wherein the STE is configured to report the node of the graph edge as the event upon an occurrence of the node matching the at least a portion of the input data stream, wherein the processor when in operation receives a report of the event representative of a satisfaction of traversal of a portion of a graph problem to be solved based on the at least a portion of the input data stream.

10. The device of claim 9 , wherein the processor when in operation identifies the report as corresponding to a respective edge and a respective node of the graph problem to be solved.

11. The device of claim 10 , wherein the processor when in operation transmits a second portion of the input data stream to be analyzed by a second STE based on the graph problem to be solved.

12. The device of claim 10 , comprising a memory coupled to the processor, wherein the processor when in operation categorizes the report and stores the categorized report in the memory.

13. A device, comprising:

a state transition element (STE), wherein the STE comprises a memory element programmed with configuration data corresponding to programming a portion of a graph problem to be solved, wherein the graph problem to be solved comprises a determination of a shortest path from a plurality of paths corresponding to whether a target node as a first configurable element of a plurality of configurable elements is reachable from an origin node as a second configurable element of the plurality of configurable elements, wherein the shortest path between the origin node and the target node from the plurality of paths is determined upon determining that the target node is reachable from the origin node by:

(a) a state machine engine comprising the plurality of configurable elements receiving a list of nodes as a query string from a processor, wherein the query string is at least a part of an input data stream transmitted to the state machine engine, wherein each node of the list of nodes corresponds to a respective character of a set of characters;

(b) each automaton comprising a portion of the plurality of configurable elements within the state machine engine evaluating whether or not it contains an edge that originates on one of the nodes in the query string;

(c) when an automaton does match this condition, reporting via the automaton a destination node of an edge it represents, wherein the destination node corresponds to a first character of the set of characters, to allow the processor to begin at any arbitrary node as an origin node to determine what nodes can be reached from the origin node;

(d) returning a list of nodes that can be reached from a set of query nodes as the origin node and/or additionally provided nodes from the state machine engine to the processor as destination nodes having a corresponding level associated with a maximum number of hops undertaken to reach the destinations nodes;

(e) utilizing a set of one-hop reachable nodes to deliver to the state machine engine as a new query for analysis;

(f) reporting from the state machine engine a set of nodes reachable from the one-hop reachable nodes as representative of two-hop reachable nodes; and

(g) discovering new nodes reachable at increasingly greater distances from the origin node until the processor finds the target node within a result set or the state machine engine returns an empty result set indicating the target node is not reachable from the origin node; and

wherein the configuration data sets a data state of the memory element as one of a high state and a low state, wherein the STE is configured to analyze portions of the input data stream based on the data state of the memory element and to output a result of the analysis as and generate an indication of an event representative of satisfaction of traversal of a portion of the graph problem to be solved based on the portions of the input data stream, wherein the STE is configured to represent a node of a graph edge as the portion of the graph problem to be solved, wherein the STE evaluates the portions of the input data stream to determine whether the node matches the portions of the input data stream, wherein the STE is configured to report the node of the graph edge as the result of the analysis upon an occurrence of the node matching the portions of the input data stream.

14. The device of claim 13 , comprising a second STE, wherein the second STE is configured to analyze second portions of the input data stream and generate an indication of a second event representative of satisfaction of traversal of a second portion of the graph problem to be solved.

15. The device of claim 14 , wherein the STE and the second STE are configured to transmit the indication of the event and the indication of the second event, respectively, in parallel.

16. The device of claim 14 , wherein the STE and the second STE are configured to transmit the indication of the event and the indication of the second event, respectively, in response to receipt of an end of data character at the STE and the second STE.

17. The device of claim 13 , wherein the STE is configured to analyze the portions of the input data stream via comparison of a character present in the portions of the input data stream with a stored value as the data state in the STE.

18. The device of claim 17 , wherein the STE is configured to generate the indication of the event based on the comparison of the character present in the portions of the input data stream with the stored value as the data state in the STE.

19. The device of claim 17 , wherein the STE comprises a second STE, wherein the second STE is configured analyze the portions of the input data stream via comparison of a second character present in the portions of the input data stream with a stored value as a second data state in the second STE.

20. The device of claim 19 , wherein the STE is configured to store a first portion of a node identification value of a node of the graph as the stored value in the STE.

21. The device of claim 20 , wherein the second STE is configured to store a second portion of the node identification value of the node of the graph as the stored value in the second STE.

22. The device of claim 13 , comprising a host processor coupled to the STE, wherein the host processor is configured to receive the indication of the event generated by the STE.

23. The device of claim 22 , wherein the host processor is configured to generate a second data stream and transmit the second data stream to the STE for analysis.

24. The device of claim 23 , wherein the host processor is configured to generate the second data stream based upon the indication of the event generated by the STE.

25. A device, comprising:

a memory configured to store instructions executable by the device, wherein the instructions comprise a compiler configured to a program a plurality of state transition elements (STEs) of a finite state machine lattice to correspond to a graph problem to be solved, wherein the graph problem to be solved comprises a determination of a shortest path from a plurality of paths corresponding to whether a target node as a first configurable element of a plurality of configurable elements is reachable from an origin node as a second configurable element of the plurality of configurable elements by:

(a) a state machine engine comprising the plurality of configurable elements receiving a list of nodes as a query string from a processor, wherein the query string is at least a part of an input data stream transmitted to the state machine engine, wherein each node of the list of nodes corresponds to a respective character of a set of characters;

(b) each automaton comprising a portion of the plurality of configurable elements within the state machine engine evaluating whether or not it contains an edge that originates on one of the nodes in the query string;

(c) when an automaton does match this condition, reporting via the automaton a destination node of an edge it represents, wherein the destination node corresponds to a first character of the set of characters, to allow the processor to begin at any arbitrary node as the origin node to determine what nodes can be reached from the origin node;

(d) returning a list of nodes that can be reached from a set of query nodes as the origin node and/or additionally provided nodes from the state machine engine to the processor as destination nodes having a corresponding level associated with a maximum number of hops undertaken to reach the destinations nodes;

(e) utilizing a set of one-hop reachable nodes to deliver to the state machine engine as a new query for analysis;

(f) reporting from the state machine engine a set of nodes reachable from the one-hop reachable nodes as representative of two-hop reachable nodes; and

(g) discovering new nodes reachable at increasingly greater distances from the origin node until the processor finds the target node within a result set or the state machine engine returns an empty result set indicating the target node is not reachable from the origin node; and

wherein the shortest path between the origin node and the target node from the plurality of paths is determined upon determining that the target node is reachable from the origin node, wherein each STE of the plurality of STEs is programmed with a respective stored value representative of an identification of a node of the graph problem to be solved for comparison against a character in the input data stream, wherein each STE of the plurality of STEs is configured to report the node as a result of an analysis of a portion of the graph problem to be solved upon an occurrence of the identification matching the character in the input data stream.

26. The device of claim 25 , wherein the compiler is configured to program the finite state machine lattice by generating a binary image of high and low bits for storage in memory cells of the finite state machine lattice as the stored value.

27. The device of claim 26 , where in the compiler is configured to reprogram the finite state machine lattice by generating a second binary image of high and low bits for storage in the memory cells of the finite state machine lattice as the stored value subsequent to generation of a match in the state machine lattice based on the comparison.

28. A tangible, non-transitory computer-readable medium configured to store instructions executable by a processor of an electronic device, wherein the instructions comprise instructions to represent a plurality of configurable elements programmed to correspond to a graph problem to be solved, wherein the graph problem to be solved comprises a determination of a shortest path from a plurality of paths corresponding to whether a target node as a first configurable element of the plurality of configurable elements is reachable from an origin node as a second configurable element of the plurality of configurable elements, wherein the shortest path between the origin node and the target node from the plurality of paths is determined upon determining that the target node is reachable from the origin node by:

(a) a state machine engine comprising the plurality of configurable elements receiving a list of nodes as a query string from the processor, wherein the query string is at least a part of an input data stream transmitted to the state machine engine, wherein each node of the list of nodes corresponds to a respective character of a set of characters;

(b) each automaton comprising a portion of the plurality of configurable elements within the state machine engine evaluating whether or not it contains an edge that originates on one of the nodes in the query string;

(c) when an automaton does match this condition, reporting via the automaton a destination node of an edge it represents, wherein the destination node corresponds to a first character of the set of characters, to allow the processor to begin at any arbitrary node as the origin node to determine what nodes can be reached from the origin node;

(d) returning a list of nodes that can be reached from a set of query nodes as the origin node and/or additionally provided nodes from the state machine engine to the processor as destination nodes having a corresponding level associated with a maximum number of hops undertaken to reach the destinations nodes;

(e) utilizing a set of one-hop reachable nodes to deliver to the state machine engine as a new query for analysis;

(f) reporting from the state machine engine a set of nodes reachable from the one-hop reachable nodes as representative of two-hop reachable nodes; and

(g) discovering new nodes reachable at increasingly greater distances from the origin node until the processor finds the target node within a result set or the state machine engine returns an empty result set indicating the target node is not reachable from the origin node; and

wherein, each configurable element of the plurality of configurable elements comprising a state transition element (STE) comprising a memory element programmed with configuration data to selectively set a data state of the memory element as one of a high state and a low state, wherein the STE is configured to analyze at least a portion of the input data stream based on the data state of the memory element and to output a result of the analysis as an event representative of a satisfaction of traversal of a portion of the graph problem to be solved, wherein the STE is configured to represent a node of a graph edge as the portion of the graph problem to be solved, wherein the STE evaluates the at least a portion of the input data stream to determine whether the node matches the at least a portion of the input data stream, wherein the STE is configured to report the node of the graph edge as the result of the analysis upon an occurrence of the node matching the at least a portion of the input data stream.

29. The computer-readable medium of claim 28 , comprising instructions to receive an input and simulate operation of the STE based on the input.

30. The computer-readable medium of claim 29 , comprising instructions to generate an indication of a result of the simulation of the operation of the STE.

Assignments (7)

Continuity (2)

References Cited (251)