High-performance table-based state machine

Patent metadata

Field	Value
Publication number	US-11863182-B2
Application number	US-202217832379-A
Country	US
Kind code	B2
Filing date	Jun 3, 2022
Priority date	Sep 15, 2020
Publication date	Jan 2, 2024
Grant date	Jan 2, 2024

Abstract

A table-based state machine is improved by reducing critical dependence path. In one aspect, all current states for a given input are read from a state table circuit, and the next state and output are then selected therefrom by an output multiplexer based on the current state, removing dependence on the current state from the table read, and allowing the read(s) to be pipelined. In a further aspect, multiple input units are configured to operate on multiple inputs in parallel, with each input unit propagating its state table circuit for its current input to the next downstream input unit. Each downstream input unit is configured to use the propagated state table circuit to provide the state table circuit reads to the proper output multiplexer input. The number of possible output states for a given input may be dynamically reduced, reducing the size of the output multiplexer selecting the next state.

First claim

What is claimed is:

1. A system configured to process a stream of inputs in parallel, comprising:
a first table-based state machine configured to generate a first set of state table circuit outputs, each state table circuit output of the first set generated based on a first input and a corresponding predetermined state of a set of predetermined states;
a second table-based state machine configured to generate a second set of state table circuit outputs, each state table circuit output of the second set generated based on a second input and a corresponding predetermined state of the set of predetermined states;
a first output multiplexer (MUX) configured to select a first state machine output from the first set of state table circuit outputs based on a current state;
a state propagator configured to select respective outputs of the second set of state table circuit outputs as a set of state propagator outputs based on the first set of state table circuit outputs; and
a second output MUX configured to select a second state machine output from among the set of state propagator outputs based on the current state.

2. The system of claim 1 , wherein each state table circuit output of the first and second sets of state table circuit outputs comprises an output value and a state value, and wherein the first and second state machine outputs comprise output values.

3. The system of claim 2 , wherein the state propagator is further configured to select which of respective ones of the second set of state table circuit outputs to route to respective outputs of the state propagator based on state values corresponding to each state table circuit output of the first set of state table circuit outputs.

4. The system of claim 2 , wherein the first output MUX is further configured to select the first state machine output from among the output values that correspond to each state table circuit output of the first set of state table circuit outputs.

5. The system of claim 2 , further comprising:
a state MUX configured to receive the current state and state values corresponding to the second set of state table circuit outputs, and to select a next state of the system.

6. The system of claim 1 , wherein the first table-based state machine includes a first set of state table circuits corresponding to the predetermined states of the set of predetermined states; and
the second table-based state machine includes a second set of state table circuits corresponding to the predetermined states of the set of predetermined states.

7. The system of claim 1 , further comprising:
an additional table-based state machine configured to generate an additional set of state table circuit outputs, each state table circuit output of the additional set generated based on an additional input and a corresponding predetermined state of the set of predetermined states;
an additional state propagator configured to select respective outputs of the additional set of state table circuit outputs as an additional set of state propagator outputs based on the additional set of state table circuit outputs; and
an additional output MUX configured to select an additional state machine output from among the additional set of state propagator outputs based on the current state.

8. A method for processing a stream of inputs in parallel, comprising:
generating a first set of state table circuit outputs, each state table circuit output of the first set generated based on a first input and a corresponding predetermined state of a set of predetermined states;
generating a second set of state table circuit outputs, each state table circuit output of the second set generated based on a second input and a corresponding predetermined state of the set of predetermined states;
selecting a first state machine output from the first set of state table circuit outputs based on a current state;
selecting respective outputs of the second set of state table circuit outputs as a set of state propagator outputs based on the first set of state table circuit outputs; and
selecting a second state machine output from among the set of state propagator outputs based on the current state.

9. The method of claim 8 , wherein each state table circuit output of the first and second sets of state table circuit outputs comprises an output value and a state value, and wherein the first and second state machine outputs comprise output values.

10. The method of claim 9 , wherein said selecting respective outputs comprises:
selecting which of respective ones of the second set of state table circuit outputs to route to respective outputs of a state propagator based on state values corresponding to each state table circuit output of the first set of state table circuit outputs.

11. The method of claim 9 , wherein said selecting a first state machine output comprises:
selecting the first state machine output from among the output values that correspond to each state table circuit output of the first set of state table circuit outputs.

12. The method of claim 9 , further comprising:
receiving the current state and state values corresponding to the second set of state table circuit outputs, and
selecting a next state.

13. The method of claim 8 , wherein the first table-based state machine includes a first set of state table circuits corresponding to the predetermined states of the set of predetermined states; and
the second table-based state machine includes a second set of state table circuits corresponding to the predetermined states of the set of predetermined states.

14. The method of claim 8 , further comprising:
generating an additional set of state table circuit outputs, each state table circuit output of the additional set generated based on an additional input and a corresponding predetermined state of the set of predetermined states;
selecting respective outputs of the additional set of state table circuit outputs as an additional set of state propagator outputs based on the additional set of state table circuit outputs; and
selecting an additional state machine output from among the additional set of state propagator outputs based on the current state.

15. A computer program product comprising a computer-readable memory device having computer program logic recorded thereon that when executed by at least one processor of a computing device causes the at least one processor to perform operations for processing a stream of inputs in parallel, the operations comprising:
generating a first set of state table circuit outputs, each state table circuit output of the first set generated based on a first input and a corresponding predetermined state of a set of predetermined states;
generating a second set of state table circuit outputs, each state table circuit output of the second set generated based on a second input and a corresponding predetermined state of the set of predetermined states;
selecting a first state machine output from the first set of state table circuit outputs based on a current state;
selecting respective outputs of the second set of state table circuit outputs as a set of state propagator outputs based on the first set of state table circuit outputs; and
selecting a second state machine output from among the set of state propagator outputs based on the current state.

16. The computer program product of claim 15 , wherein each state table circuit output of the first and second sets of state table circuit outputs comprises an output value and a state value, and wherein the first and second state machine outputs comprise output values.

Assignees

• Microsoft Technology Licensing Llc

Inventors

• Lo Daniel
• Pelton Blake D

Classifications

• H03K19/09425 Primary

  Multistate logic (H03K19/096 takes precedence) · CPC title

• H03K19/096

  Synchronous circuits, i.e. using clock signals {(H03K19/01728, H03K19/01855 take precedence)} · CPC title

• H03K19/1737

  using multiplexers (H03K19/1738 takes precedence) · CPC title

• H03K19/17728

  Reconfigurable logic blocks, e.g. lookup tables · CPC title

• G06F7/544 Primary

  for evaluating functions by calculation {(G06F7/4824 takes precedence)} · CPC title