Granted Patent B1

US 7,307,453 · App. 10/961,058 · Granted Dec 11, 2007

Abstract

Claims (57)

1. A method of performing state machine transitions comprising:

combining an input vector containing at least one input bit for each of a plurality of state machines with a current state vector containing at least one current state bit for each of the plurality of state machines to generate a control vector; and

using the control vector, determining in a parallel manner at least one bit representing a next state for each state machine;

wherein determining comprises performing a first parallel table look-up using the control vector to look-up the first respective table output for each of the state machines.

2. The method of claim 1 wherein the respective table output comprises at least one bit representing a next state for each state machine and at least one output bit for each state machine.

3. The method of claim 1 further comprising:

performing at last a second parallel table look-up using the control vector to look-up at least a second respective table output for each of the state machines, wherein the first and the at least a second table outputs for each state machine collectively comprise at least one bit representing the next state and output bits.

4. The method of claim 1 further comprising:

storing a table for use in the parallel table look-up in a first register;

storing the control vector in a second register;

providing the fast register and second register as inputs to a vector permutation operation to implement the parallel table look-up.

5. The method of claim 1 further comprising:

storing a table for use in the parallel table look-up partly in a first register and partly in a second register;

storing the control vector in a third register;

providing the first register, the second register and the third register as inputs to a three input vector permutation operation to implement the parallel table look-up.

6. The method of claim 1 wherein the parallel table look-up is performed using a vperm instruction.

7. The method of claim 1 adapted to implement a plurality of HDLC state machines in parallel, wherein the current state is represented by five bits and the current input is represented by one bit for each state machine.

8. The method of claim 7 comprising:

storing 64 table look-up entries in four 16-element vector registers;

generating the control vector as a 16 element control vector containing five bits of the six bits of current state and current input;

using the control vector to look-up two sets of 16 element parallel outputs;

selecting between two elements in the two parallel outputs for each of 16 state machines on the basis of the remaining bit of the six bits for that state machine.

9. A parallel state machine calculator adapted to implement the method of claim 1 .

10. A method of performing state machine transitions comprising:

combining an input vector containing at least one input bit for each of a plurality of state machines with a current state vector containing at least one current state bit for each of the plurality of state machines to generate a control vector; and

using the control vector, determining in parallel manner at least one bit representing a next state for each state machine;

wherein combining the input vector containing at least one input bit for each of the plurality of state machines with the current state vector containing at least one current state bit for each of the plurality of state machines to generate the control vector comprises:

producing a shifted vector by performing a vector shift operation on one of the input vector and the current state vector such that the bits of each element are shifted by enough bits to store bits of the other of the input vector and the current state vector current state; and

executing a vector bit-wise OR of the shifted vector with the other of the input vector and the current state vector to produce the control input.

11. A computer readable medium having processor executable instructions thereon for implementation by a vector processor, the instructions providing a method of performing state machine transitions comprising:

combining an input vector containing at least one input bit for each of a plurality of state machines with a current state vector containing at least one current state bit for each of the plurality of state machines to generate a control vector; and

using the control vector, determining in a parallel manner at least one bit representing a next state for each state machine;

wherein determining comprises performing a first parallel table look-up using the control vector to look-up the first respective table output for each of the state machines.

12. The computer readable medium of claim 11 wherein the respective table output comprises at least one bit representing a next state for each state machine and at least one output bit for each state machine.

13. The computer readable medium of claim 11 wherein the method further comprises:

performing at least a second parallel table look-up using the control vector to look-up at least a second respective table output for each of the state machines, wherein the first and the at least a second table outputs for each state machine collectively comprise at least one bit representing the next state and output bits.

14. The computer readable medium of claim 11 wherein the method further comprises:

storing a table for use in the parallel table look-up in a first register;

storing the control vector in a second register;

providing the first register and second register as inputs to a vector permutation operation to implement the parallel table look-up.

15. The computer readable medium of claim 11 wherein the method further comprises:

storing a table for use in the parallel table look-up partly in a first register and partly in a second register;

storing the control vector in a third register;

providing the first register, the second register and the third register as inputs to a three input vector permutation operation to implement the parallel table look-up.

16. The computer readable medium of claim 11 wherein the parallel table look-up is performed using a vperm instruction.

17. The computer readable medium of claim 11 adapted to implement a plurality of HDLC state machines in parallel, wherein the current state is represented by five bits and the current input is represented by one bit for each state machine.

18. The computer readable medium of claim 17 wherein the method further comprises:

storing 64 table lookup entries in four 16-element vector registers;

generating the control vector as a 16 element control vector containing five bits of the six bits of current state and current input;

using the control vector to look-tip two sets of 16 element parallel outputs;

selecting between two elements the two parallel outputs for each of 16 state machines on the basis of the remaining bit of the six bits for that state machine.

19. A computer readable medium having processor executable instructions thereon for implementation by a vector processor, the instructions providing a method of performing state machine transitions comprising:

combining an input vector containing at least one input bit for each of a plurality of state machines with a current state vector containing at least one current state bit for each of the plurality of state machines to generate a control vector; and

using the control vector, determining in a parallel manner at least one bit representing a next state for each state machine;

wherein combining the input vector containing at least one input bit for each of the plurality of state machines with the current state vector containing at least one current state bit for each of the plurality of state machines to generate the control vector comprises:

producing a shifted vector by performing a vector shift operation on one of the input vector and the current state vector such that the bits of each element are shifted by enough bits to store bits of the other of the input vector and the current state vector current state; and

executing a vector bit-wise OR of the shifted vector with the other of the input vector and the current state vector to produce the control input.

Assignments (12)