US 11,381,241 B2Granted

High-performance table-based state machine

AssigneeMicrosoft Technology Licensing, LLC

InventorsDaniel Lo, Blake D. Pelton

Life of this patent

Estimating the term…

Loading patent…

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.

Claims20

Dependent claims

A state machine configured to process multiple inputs of a stream of inputs in parallel, comprising:

a first set of state table circuits, each state table circuit of the first set corresponding to a predetermined state of a set of predetermined states and configured to generate first state table circuit outputs based on a first input and the corresponding predetermined state, wherein the first state table circuit outputs corresponding to each state table circuit of the first set of state table circuits collectively comprise a first set of state table circuit outputs;
a second set of state table circuits, each state table circuit of the second set corresponding to a predetermined state of the set of predetermined states and configured to generate second state table circuit outputs based on a second input and the corresponding predetermined state, wherein the second state table circuit outputs corresponding to each state table circuit of the second set of state table circuits comprise a second set of state table circuit outputs;
a first output multiplexer (MUX) configured to receive the first set of state table circuit outputs and a current state of the state machine, and to select a first state machine output from among the first set of state table circuit outputs based on the current state;
a state propagator configured to receive the first and second sets of state table circuit outputs and to select which of respective outputs of the second set of state table circuit outputs to route to respective outputs of the state propagator based on the first set of state table circuit outputs, said respective outputs comprising a set of state propagator outputs;
and
a second output MUX configured to receive the set of state propagator outputs and the current state of the state machine, and to select a second state machine output from among the set of state propagator outputs based on the current state.

3 more elements

A method for a state machine configured to process inputs in parallel, comprising:

generating first state table circuit outputs based on a first input and a corresponding predetermined state of a set of predetermined states, wherein the first state table circuit outputs correspond to a first set of state table circuits and collectively comprise a first set of state table circuit outputs;
generating second state table circuit outputs based on a second input and a corresponding predetermined state of the set of predetermined states, wherein the second state table circuit outputs correspond to a second set of state table circuits and collectively comprise a second set of state table circuit outputs;
selecting a first state machine output from among the first set of state table circuit outputs based on a current state of the state machine;
selecting which of respective outputs of the second set of state table circuit outputs to route 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.

3 more elements

A computer program product comprising a computer-readable storage medium 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 implementing a state machine configured to process inputs in parallel, the operations comprising:

generating first state table circuit outputs based on a first input and a corresponding predetermined state of a set of predetermined states, wherein the first state table circuit outputs correspond to a first set of state table circuits and collectively comprise a first set of state table circuit outputs;
generating second state table circuit outputs based on a second input and a corresponding predetermined state of the set of predetermined states, wherein the second state table circuit outputs correspond to a second set of state table circuits and collectively comprise a second set of state table circuit outputs;
selecting a first state machine output from among the first set of state table circuit outputs based on a current state of the state machine;
selecting which of respective outputs of the second set of state table circuit outputs to route as a set of state propagator outputs based on the values of 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.

3 more elements

Dependencies are inferred from the claim text.

Facts

Application: 17/178,017Filed 17 Feb 2021 · us provisional application
Priority: 15 Sep 2020
Published: US 2022/0085815 A117 Mar 2022
Granted: 5 Jul 2022
Term ends: Not estimatedThe source records don’t support an estimate.

Classification7 codes

G06F 7/544
Using non-contact-making devices, e.g. tube, solid state device; using unspecified devices: for evaluating functions by calculation
H03K 19/09425
Using field-effect transistors: multistate logic
H03K 19/096
Using field-effect transistors: synchronous circuits, i.e. using clock signals
H03K 19/1737
Controllable logic circuits: using multiplexers