EFFICIENTLY IMPLEMENTING A PLURALITY OF FINITE STATE MACHINES

• US 20110055510A1
• Filed: 08/25/2009
• Published: 03/03/2011
• Est. Priority Date: 08/25/2009
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Thiele, Daniel, Muller, Andreas, Fritz, Rolf K., Schlipf, Thomas
• Granted Patent: US 8,566,509 B2
• Time in Patent Office: Days
• US Class Current: 711/169
• CPC Class Codes: G06F 7/00 Methods or arrangements for processing data by operating upon the order or content of the data handled logic circuits H03K19/00
• CPC Class Codes: G06F 9/30079 Pipeline control instructions, e.g. multicycle NOP

Abstract

A method and program product for processing data by a pipeline of a single hardware-implemented virtual multiple instance finite state machine (VMI FSM). An input token of multiple input tokens is selected to enter a pipeline of the VMI FSM. The input token includes a reference to an FSM instance. In one embodiment, the reference is an InfiniBand QP number. After being received at the pipeline, a current state and context of the FSM instance are fetched from an array based on the reference and inserted into a field of the input token. A new state of the FSM instance is determined and an output token is generated. The new state and the output token are based on the current state, context, a first input value, and an availability of a resource. The new state of the first FSM instance is written to the array.

Claims

1. A logic circuit-implemented method of processing data by a pipeline of a virtual multiple instance finite state machine (VMI FSM), said method comprising:

receiving a plurality of input tokens referencing a plurality of FSM instances included in said VMI FSM, wherein said VMI FSM is a single hardware implementation;

selecting a first input token of said plurality of input tokens to enter said pipeline of said VMI FSM, wherein said first input token includes a first field that includes a reference to a first set of one or more FSM instances (first FSM instance) of said plurality of FSM instances and a second field that includes a first input value;

receiving said first input token at said pipeline of said VMI FSM;

fetching a current state of said first FSM instance and a context of said first FSM instance from an array based on said reference included in said first field of said first input token;

inserting said current state of said first FSM instance and said context of said first FSM instance into one or more other fields of said first input token;

said VMI FSM switching to said first FSM instance of said plurality of FSM instances included in said VMI FSM by receiving said first input token including said current state of said first FSM instance and said context of said first FSM instance inserted into said one or more other fields of said first input token;

determining a new state of said first FSM instance based on said current state of said first FSM instance, said context of said first FSM instance, said first input value, and a status of an environment;

generating a first output token based on said current state of said first FSM instance, said context of said first FSM instance, said first input value, and said status of said environment;

writing said new state and said context of said first FSM instance to said array; and

subsequent to said pipeline of said VMI FSM receiving said first input token and prior to said determining said new state and said determining said first output token, selecting a second input token of said plurality of input tokens to enter said pipeline of said VMI FSM, wherein said second input token includes a first field that includes a reference to a second set of one or more FSM instances (second FSM instance) of said plurality of FSM instances and a second field that includes a second input value.

2. The method of claim 1, further comprising pipelining said first input token and said second input token in said pipeline of said VMI FSM.

3. The method of claim 1, further comprising:

subsequent to said selecting said second input token, selecting a third input token of said plurality of input tokens to enter said pipeline of said VMI FSM; and

pipelining said first input token, said second input token and said third input token.

4. The method of claim 1, further comprising:

receiving said second input token at said pipeline of said VMI FSM;

fetching a current state of said second FSM instance and a context of said second FSM instance from said array based on said reference included in said first field of said second input token;

inserting said current state of said second FSM instance and said context of said second FSM instance into one or more other fields of said second input token;

said VMI FSM switching to said second FSM instance of said plurality of FSM instances included in said VMI FSM by receiving said current state of said second FSM instance and said context of said second FSM instance in said one or more other fields of said second input token;

determining a new state of said second FSM instance based on said current state of said second FSM instance, said context of said second FSM instance, said second input value, and a second status of said environment;

generating a second output token based on said current state of said second FSM instance, said context of said second FSM instance, said second input value, and said second status of said environment; and

writing said new state of said second FSM instance to said array.

5. The method of claim 1, further comprising said VMI FSM processing said plurality of input tokens by using only one instance of logic executed by a single hardware FSM implementation and by using said array without using a plurality of current state registers.

6. The method of claim 1, wherein said receiving said plurality of input tokens includes receiving a third input token of said plurality of input tokens, wherein said third input token includes a first field that includes a reference to said first FSM instance and a second field that includes a third input value, and wherein said method further comprises:

subsequent to said receiving said first input token at said pipeline, determining said reference to said first FSM instance in said first field of said third input token is identical to said reference to said first FSM instance in said first field of said first input token and determining said first input token is in said pipeline;

in response to said determining said reference to said first FSM instance in said first field of said third input token is identical to said reference to said first FSM instance in said first field of said first input token and said determining said first input token is in said pipeline, a guard component preventing said third input token from being received at said pipeline while said first input token is in said pipeline;

subsequent to said writing said new state of said first FSM instance, determining said first input token is out of said pipeline;

in response to determining said first input token is out of said pipeline, said guard component allowing said third input token to be received at said pipeline; and

receiving said third input token at said pipeline.

7. The method of claim 1, further comprising processing, by said VMI FSM, a packet header token using an input/output (I/O) protocol on an adapter specified by an InfiniBand architecture, wherein said processing said packet header token includes:

a port receiving a data packet that includes a payload and a packet header;

storing said payload in a payload buffer;

inserting said packet header in a second field of said packet header token, wherein said packet header token is said first input token, and wherein said second field of said packet header token is said second field of said first input token;

extracting a queue pair (QP) number from said packet header, wherein said QP number identifies a QP that specifies a network connection in said InfiniBand architecture;

storing said QP number in a first field of said packet header token, wherein said first field of said packet header token is said first field of said first input token,

wherein said receiving said first input token includes receiving said packet header token from said port and at said VMI FSM.

8. The method of claim 7, further comprising:

determining a transport mode of said network connection specified by said QP is a reliable connect transport mode (RC) or a reliable datagram transport mode (RD);

determining a packet sequence number (PSN) included in said packet header token is equal to an expected PSN (ePSN) included in said fetched context; and

in response to said determining said transport mode of said QP is said RC or said RD and in response to said determining said PSN is equal to said ePSN, sending an acknowledgment to said port.

9. The method of claim 1, further comprising processing, by said VMI FSM, a mode change token using an input/output (I/O) protocol on an adapter specified by an InfiniBand architecture, wherein said processing said mode change token includes:

receiving said mode change token;

identifying a queue pair (QP) number in said mode change token, wherein said QP number identifies a QP that specifies a network connection in said InfiniBand architecture; and

updating said context by changing a transport protocol of said QP.

10. A logic circuit of multiple interconnected electrically conductive elements configured to perform a method of processing data by a pipeline of a virtual multiple instance finite state machine (VMI FSM), said method comprising:

receiving a plurality of input tokens referencing a plurality of FSM instances included in said VMI FSM, wherein said VMI FSM is a single hardware implementation;

selecting a first input token of said plurality of input tokens to enter said pipeline of said VMI FSM, wherein said first input token includes a first field that includes a reference to a first set of one or more FSM instances (first FSM instance) of said plurality of FSM instances and a second field that includes a first input value;

receiving said first input token at said pipeline of said VMI FSM;

fetching a current state of said first FSM instance and a context of said first FSM instance from an array based on said reference included in said first field of said first input token;

inserting said current state of said first FSM instance and said context of said first FSM instance into one or more other fields of said first input token;

said VMI FSM switching to said first FSM instance of said plurality of FSM instances included in said VMI FSM by receiving said first input token including said current state of said first FSM instance and said context of said first FSM instance inserted into said one or more other fields of said first input token;

determining a new state of said first FSM instance based on said current state of said first FSM instance, said context of said first FSM instance, said first input value, and a status of an environment;

generating a first output token based on said current state of said first FSM instance, said context of said first FSM instance, said first input value, and said status of said environment;

writing said new state and said context of said first FSM instance to said array; and

subsequent to said pipeline of said VMI FSM receiving said first input token and prior to said determining said new state and said determining said first output token, selecting a second input token of said plurality of input tokens to enter said pipeline of said VMI FSM, wherein said second input token includes a first field that includes a reference to a second set of one or more FSM instances (second FSM instance) of said plurality of FSM instances and a second field that includes a second input value.

11. The logic circuit of claim 10, wherein said method further comprises pipelining said first input token and said second input token in said pipeline of said VMI FSM.

12. The logic circuit of claim 10, wherein said method further comprises:

subsequent to said selecting said second input token, selecting a third input token of said plurality of input tokens to enter said pipeline of said VMI FSM; and

pipelining said first input token, said second input token and said third input token.

13. The logic circuit of claim 10, wherein said method further comprises:

receiving said second input token at said pipeline of said VMI FSM;

fetching a current state of said second FSM instance and a context of said second FSM instance from said array based on said reference included in said first field of said second input token;

inserting said current state of said second FSM instance and said context of said second FSM instance into one or more other fields of said second input token;

said VMI FSM switching to said second FSM instance of said plurality of FSM instances included in said VMI FSM by receiving said current state of said second FSM instance and said context of said second FSM instance in said one or more other fields of said second input token;

determining a new state of said second FSM instance based on said current state of said second FSM instance, said context of said second FSM instance, said second input value, and a second status of said environment;

generating a second output token based on said current state of said second FSM instance, said context of said second FSM instance, said second input value, and said second status of said environment; and

writing said new state of said second FSM instance to said array.

14. The logic circuit of claim 10, wherein said method further comprises said VMI FSM processing said plurality of input tokens by using only one instance of logic executed by a single hardware FSM implementation and by using said array without using a plurality of current state registers.

15. The logic circuit of claim 10, wherein said receiving said plurality of input tokens includes receiving a third input token of said plurality of input tokens, wherein said third input token includes a first field that includes a reference to said first FSM instance and a second field that includes a third input value, and wherein said method further comprises:

subsequent to said receiving said first input token at said pipeline, determining said reference to said first FSM instance in said first field of said third input token is identical to said reference to said first FSM instance in said first field of said first input token and determining said first input token is in said pipeline;

in response to said determining said reference to said first FSM instance in said first field of said third input token is identical to said reference to said first FSM instance in said first field of said first input token and said determining said first input token is in said pipeline, a guard component preventing said third input token from being received at said pipeline while said first input token is in said pipeline;

subsequent to said writing said new state of said first FSM instance, determining said first input token is out of said pipeline;

in response to determining said first input token is out of said pipeline, said guard component allowing said third input token to be received at said pipeline; and

receiving said third input token at said pipeline.

16. The logic circuit of claim 10, wherein said method further comprises processing, by said VMI FSM, a packet header token using an input/output (I/O) protocol on an adapter specified by an InfiniBand architecture, wherein said processing said packet header token includes:

a port receiving a data packet that includes a payload and a packet header;

storing said payload in a payload buffer;

inserting said packet header in a second field of said packet header token, wherein said packet header token is said first input token, and wherein said second field of said packet header token is said second field of said first input token;

extracting a queue pair (QP) number from said packet header, wherein said QP number identifies a QP that specifies a network connection in said InfiniBand architecture;

storing said QP number in a first field of said packet header token, wherein said first field of said packet header token is said first field of said first input token,

wherein said receiving said first input token includes receiving said packet header token from said port and at said VMI FSM.

17. The logic circuit of claim 16, wherein said method further comprises:

determining a transport mode of said network connection specified by said QP is a reliable connect transport mode (RC) or a reliable datagram transport mode (RD);

determining a packet sequence number (PSN) included in said packet header token is equal to an expected PSN (ePSN) included in said fetched context; and

in response to said determining said transport mode of said QP is said RC or said RD and in response to said determining said PSN is equal to said ePSN, sending an acknowledgment to said port.

18. The logic circuit of claim 10, wherein said method further comprises processing, by said VMI FSM, a mode change token using an input/output (I/O) protocol on an adapter specified by an InfiniBand architecture, wherein said processing said mode change token includes:

receiving said mode change token;

identifying a queue pair (QP) number in said mode change token, wherein said QP number identifies a QP that specifies a network connection in said InfiniBand architecture; and

updating said context by changing a transport protocol of said QP.

19. A computer system comprising a processor that includes the logic circuit of claim 10.

20. A computer system comprising:

a processor; and

a computer-readable storage medium coupled to said processor, wherein said processor includes one or more logic circuits including combinational logic that when executed by said processor implement a method of processing data by a pipeline of a virtual multiple instance finite state machine (VMI FSM), said method comprising;

receiving a plurality of input tokens referencing a plurality of FSM instances included in said VMI FSM, wherein said VMI FSM is a single hardware implementation;

selecting a first input token of said plurality of input tokens to enter said pipeline of said VMI FSM, wherein said first input token includes a first field that includes a reference to a first set of one or more FSM instances (first FSM instance) of said plurality of FSM instances and a second field that includes a first input value;

receiving said first input token at said pipeline of said VMI FSM;

fetching a current state of said first FSM instance and a context of said first FSM instance from an array based on said reference included in said first field of said first input token;

inserting said current state of said first FSM instance and said context of said first FSM instance into one or more other fields of said first input token;

said VMI FSM switching to said first FSM instance of said plurality of FSM instances included in said VMI FSM by receiving said first input token including said current state of said first FSM instance and said context of said first FSM instance inserted into said one or more other fields of said first input token;

determining a new state of said first FSM instance based on said current state of said first FSM instance, said context of said first FSM instance, said first input value, and a status of an environment;

generating a first output token based on said current state of said first FSM instance, said context of said first FSM instance, said first input value, and said status of said environment;

writing said new state and said context of said first FSM instance to said array; and

subsequent to said pipeline of said VMI FSM receiving said first input token and prior to said determining said new state and said determining said first output token, selecting a second input token of said plurality of input tokens to enter said pipeline of said VMI FSM, wherein said second input token includes a first field that includes a reference to a second set of one or more FSM instances (second FSM instance) of said plurality of FSM instances and a second field that includes a second input value.